DS&A

Question 1

Binary Search

How to implement canonical BS?

Answer 1

def search(nums: List[int], target: int) -> int:

        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l+r)//2
            if target < nums[m]:
                r = m - 1
            elif target == nums[m]:
                return m
            else:
                l = m + 1
        
        return -1

• Helps to search sorted array
• O(log(n)) TC, O(1) SC
• We need the l<=r to handle the case len(nums)==1
• If we have l<=r and r=m or l=m then no convergence (time out)

Question 2

DFS

How to implement DFS in a tree? What is it used for?

Answer 2

• DFS can be implemented recursively, then it’s easy to traverse a tree pre-order, in-order or post order
• To reduce the call stack we can implement DFS iteratively using a stack structure; pre-order DFS

def dfs_pre(root: TreeNode):
    logger.info("DFS pre-order")
    stack = deque()
    stack.append(root)
    while stack:
        node = stack.pop()
        logger.info("At node %d", node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)