编程算法面试常考题答案汇总
Design a Cord
Coding Interview Question: Design a Cord
A cord is a tree that store parts from a large string. It has 2 types of nodes: the leaf node contain the actual string content while he internal, in additional to 2 children, stores the total length of the 2 string represented by its 2 children. You could assume the internal node always has 2 children.
Question 1: Design the data structure in code.
Question 2: Given an index n and a length l, returns a string that represents the substring from [n, n+l) of the original string represented by the Cord tree.
Question 3: Given an index n and a length l, Delete the substring [n, n+l) from the Cord tree.
Solution
# 本代码来自 Techie科技求职，由 Techie Learning,Inc 原创
# - Techielearning.com 是来自硅谷的科技职业发展平台。
# - 本代码所属课程：<< Techie编程算法集训营 >>
# - 12周56+课时精品内容，精讲软件工程师编程算法面试核心知识体系。
# - 120道面试真题详解，27类常考题型剖析，1对1面试辅导与专业答疑。
# - 官方网站：https://www.techielearning.com/
# - 版权所有，禁止转发和分享
class LeafNode:
def __init__(self, string):
self.string = string
self.length = len(string)
class InternalNode:
def __init__(self, left, right):
self.length = 0
self.left = left
if left:
self.length += left.length
self.right = right
if right:
self.length += right.length
def getSlice(root, n, l):
if isinstance(root, LeafNode):
return root.string[n:n + l]
if n + l <= root.left.length:
return getSlice(root.left, n, l)
elsf n >= root.left.length:
return getSlice(root.right, n - root.left.length, l)
else:
left_slice = getSlice(root.left, n, root.left.length - n)
return left_slice + getSlice(root.right, 0, l - len(left_slice))
def deleteSlice(root, n, l):
if isinstance(root, LeftNode):
root.string = root.string[:n] + root.string[n+l:]
root.length = len(root.string)
return
if n + l <= root.left.length:
deleteSlice(root.left, n, l)
root.length = root.left.length + root.right.length
return
if n >= root.left.length:
deleteSlice(root.right, n - root.left.length, l)
root.length = root.left.length + root.right.length
return
original_left_length = root.left.length
deleteSlice(root.left, n, root.left.length - n)
deleted_left_length = original_left_length - root.left.length
deleteSlice(root.right, 0, l - deleted_left_length)
root.length = root.left.length + root.right.length
如果大家对题目代码有任何问题，欢迎扫描下方的二维码或者搜索 TonyCoding20 添加Techie教师团队微信。期待与同学们继续交流！
