编程算法面试常考题答案汇总
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教师团队微信。期待与同学们继续交流!