Programming

Question 1

What are the common ways to represent a graph?

Answer 1

1) Adjacency Matrix
- Common way to represent a graph as a matrix
- Square matrix where the rows and columns represent the vertices of the graph, and the entries (elements) of the matrix indicate whether there is an edge between the corresponding vertices

Example of an undirected graph with 4 vertices (A, B, C, D) and 4 edges (A-B, B-C, C-D, D-A)

A --- B
D --- C

    A  B  C  D
A  0  1   0  1
B  1  0   1  0
C  0  1   0  1
D  1  0   1  0

2) Adjacency List
- In a adjacency list, each vertex is associated with a list of its neighboring vertices directly connected to it

Example of an undirected graph with 4 vertices (A, B, C, D) and four edges

A --- B
C --- D

{
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}

paths = defaultdict(list)
for edge in edges:
    paths[edge[0]].append(edge[1])
    paths[edge[1]].append(edge[0])

|

Question 2

Graph Traversal using DFS

Answer 2

• DFS starts from a selected source node (or a starting point) and explores as deeply as possible along each branch before backtracking
• The algorithm visits nodes in a depth ward motion until it reaches a leaf node with no unexplored neighbors. At that point, it backtracks and explores other unexplored branches

1) Initialize
- Choose a starting node as the source node
- Create a hashset or array for marking the source node as visited

2) Visit the current node
- Process the current node (eg print or perform any other operation you need to do)

3) Recursive approach (Using Recusion)
- For each unvisited neighbor of the current node:
- Recursively call the DFS function with the neighbor as the new current node
- Mark the neighbor as visited

4) Stack-Based Approach (Using an Explicit Stack)
- Push the starting node onto the stack
- While the stack is not empty:
- Pop a node from the stack (current node)
- Process the current node (eg print or perform any other operation)
- For each unvisited neighbor:
Push onto the stack
Mark as visited

5) Backtracking
- If there are no more unvisited neighbors for the current node, backtrack by returning from the recursive function (if recursion) or popping nodes from the stack until a node with unvisited neighbors is found (if using an explicit stack)

6) Termination
- The DFS algorithm terminates when all nodes reachable from the source node have been visited
- This means that all the connected components of the graph have been explored

Question 3

Graph Traversal using Breadth First Search (BFS)

Answer 3

• Explores a graph’s vertices (nodes) level by level
• Starts from a selected node and moves outward to visit all the nodes at the same distance from the source before moving on to nodes at the following distance
• BFS is particularly useful for finding the shortest path in unweighted graphs and for systematically exploring graphs

1) Use a queue
- BFS uses a queue to keep track of the nodes to be visited
- Follows FIFO principle

2) Initialization
- Select a source node to begin the traversal
- Create an empty queue to hold the nodes to be visited
- Mark the source node as visited and enqueue it onto the queue

3) Traversal
- While the queue is not empty:
- Dequeue a node from the from of the queue (let’s call it “current node”)
- Process the current node (print it, perform operation)
- Enqueue all the unvisited neighbors of the current node into the queue
- Mark each enqueued neighbor as visited

4) Termination
- The BFS algorithm continues until the queue becomes empty, meaning all reachable nodes from the source node have been visited

Question 4

BFS Algo for Graphs

Answer 4

https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1372/

https://algo.monster/problems/graph_bfs

Question 5

Implement classic binary search

Answer 5

def binary_search(arr: List[int], target: int) -> int:
    l, r = 0, len(arr) - 1
    index = -1
    
    while l <= r:
        mid = (l + r) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return index

• Time complexity: O(log n)
• Space complexity: O(1)
• A monotonic function is a function that is either non-decreasing or non-increasing. Given x1 and x2 where x1 > x2, we should have f(x1) >= f(x2)

• The precondition for binary search is to find a monotonic function f(x) that returns either True or False
• We will call the function “feasible” to signify whether the element at the current index is feasible (True) or not (False) to meet the problem constraints

def binary_search(arr: List[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    first_true_index = -1
    while left <= right:
        mid = (left + right) // 2
        if feasible(mid):
            first_true_index = mid
            right = mid - 1
        else:
            left = mid + 1

    return first_true_index

Question 6

Recursion

Answer 6

What makes a function properly recursive?
1. Base case/exit.
2. Recursive call. Calling the function with different arguments in order to break the problem down to its fundamental parts

• Function calls push a frame object onto the stack, returning pops them off
• At every step of the return journey, the returned value is computed against the state of each frame!
• each frame has its own state and that that state persists while it waits for the return to occur

Frame: Whenever a function is called, a new frame is opened in which the function performs its computation. Once the computation is finished, the results are returned to the calling function and the frame, along with the function and its contents, is discarded.

Strategy for recursion
- What’s the simplest possible input
- Play around w/ examples and visualize
- Generalize the pattern
- Write code by combining recursive pattern with base case

Question 7

Full, Complete, and Perfect Binary Trees

Answer 7

Full Binary Tree
- Every node has 0 or 2 children

Complete Binary Tree
- All levels are completely filled except possibly the last level and all nodes in the last level are as far left as possible

Perfect binary tree
- All nodes have 2 children and all leaf nodes have the same level

Question 8

Binary Search Tree

Answer 8

A special type of binary tree in which every node follows the ordering property

all left descendants < node < all right descendants

Question 9

Balanced Binary Tree

Answer 9

Every node in a balanced binary tree fulfills the condition:

• The height difference of the left and right subtree of the node is not more than 1

Question 10

Pre-order Traversal

Answer 10

• Visit the current node first
• Then the left subtree
• Finally the right subtree

def preorder(root: Node | None) -> list[int]:
    result = []

    def dfs(node: Node | None) -> None:
        if not node:
            return
        result.append(node.val)
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return result

Question 11

In-order Traversal

Answer 11

• Visit the left subtree
• Then the current node
• Finally the right subtree

def in_order_traversal_bst(tree: Node | None) -> list[int]:
    """
    Given a binary search tree, return the in-order traversal of its nodes' values.
    """
    res = []

    def dfs(tree):
        if not tree:
            return
        dfs(tree.left)
        res.append(tree.val)
        dfs(tree.right)

    dfs(tree)
    return res

Question 12

Post-order Traversal

Answer 12

• Visit the left subtree
• Then the right subtree
• Finally the current node

def postorder(root: Node | None) -> list[int]:
    """
    Processes the root/node after its subtrees
    """
    result = []

    def dfs(node: Node | None) -> None:
        if not node:
            return
        dfs(node.left)
        dfs(node.right)
        result.append(node.val)

    dfs(root)
    return result

Question 13

Implement DFS Fundamental Algorithm for Finding a target within a tree

Answer 13

def dfs(root: Node | None, target):
    # https://algo.monster/problems/dfs_intro
    if root is None:
        return None
    if root.val == target:
        return root
    # return non-null return value from the recursive calls
    left = dfs(root.left, target)
    if left is not None:
        return left
    
    # at this point, we know left is null, and right could be null or non-null
    # we return right child's recursive call result directly because
    # - if it's non-null we should return it
    # - if it's null, then both left and right are null, we want to return null
    return dfs(root.right, target)

    # FYI, can also be simplified to
    #return dfs(root.left, target) or dfs(root.right, target)