---
# System prepended metadata

title: Coding Interview

---

# Coding Interview

## Data Structure (https://wiki.python.org/moin/TimeComplexity)

- List / Array / Stack
    - `append`: O(1)
    - `pop`: O(1)
    - `insert`: O(N)
    - `remove`: O(N)
    - `index`: O(N)
- Set
    - `add`: O(1) / O(n) in worst case ... Hash collipsion
    - `discard`: O(1) / O(n) in worst case
    - `remove`: O(1) / O(n) in worst case
    - `union` / `s | t`: O(len(s)+len(t))
    - `intersection` / `s & t`: O(min(len(s), len(t)))
- Deque (double-end queue) (`collections.deque`)
    - `append`: O(1)
    - `appendleft`: O(1)
    - `pop`: O(1)
    - `popleft`: O(1)
- Heap (min / max) (`heapq`)
    - `heappush`: O(logn)
    - `heappop`: O(logn)
    - `heappushpop`: faster than `heappush` + `heappop`
- SortedList (`sortedcontainers.SortedList`)
    - `add`: O(logn)
    - `discard` / `remove`: O(logn)
    - `bisect_left`: O(logn)
    - `bisect_right`: O(logn)
- collections
    - defaultdict
    - deque
    - Counter


## Algorithm

- Subarray
    - kadane's algorithm
- Subsequence
- Binary search
    - `bisect.bisect_left()`
    - `bisect.bisect_right()` / `bisect.bisect()`
- String
    - `isalnum()`: Checks if the given character is an alphanumeric character
    - `string.ascii_letters`
    - `string.ascii_lowercase`
    - `string.ascii_uppercase`
- Graph
    - Depth-first search (DFS)
    - Breadth-first search (BFS) / **Bidrectional BFS**
    - Shortest path (https://x-wei.github.io/shortest-path-summary.html)
    - Disjoint set union (DSU)
    - Eulerian path (Hierholzer's algorithm)
        - Directed Graph
            - 起點: indegree + 1 = outdegree
            - 終點: outdegree + 1 = indegree
            - Others: indegree = outdegree
        - Undirected Graph
            - 起終點: 有奇數邊
            - Others: 有偶數邊
    - Eularian circuit (Hierholzer's algorithm)
        - Directed Graph: indegree = outdegree
        - Undirected Graph: 均偶數邊
    - Topological trimming / Topological sorting
- Tree
- Linked List
- Binary search tree
- Dynamic programming
    - Properties
        - Overlapping Subproblems
        - Optimal Substructure
    - 1D / 2D / state reduction
- Math
    - rectangle
- Bit manipulation
    - Obtain the lowest bit equals to 1 (lowbit): `lowerbit(n) = n & -n`
        ![image](https://hackmd.io/_uploads/Hy8bt2mVbg.png)
        - `n > 0 and n == (n & -n)`: n is the power of 2 (e.g., 2^2, 2^5 ...)
    - Remove the right-most 1: `n & (n - 1)`

- Other
    - Backtrack
        - `catalan number`: https://zh.wikipedia.org/zh-tw/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
    - Monotonic Stack / Monotonic Deque
    - Quick select
    - Cycle sort
    - Counting sort


## Template

### Linked List
- Reverse singly linked list
    ```python
    def reverse(head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head
        while curr:
            tmp = curr.next
            curr.next = prev
            prev, curr = curr, tmp
        return prev
    ```
- Find the middle point
    ```python
    """ Use cases
        - [1, 2, (3), 4, 5] ... odd nodes
        - [1, 2, (3), 4] ... even nodes (return the right one)
    """
    def get_middle_node(head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow


    """ Use cases
        - [1, 2, (3), 4, 5] ... odd nodes
        - [1, (2), 3, 4] ... even nodes (return the left one)
    """
    def get_middle_node(head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return head
        slow, fast = head, head.next
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow
    ```
- Merge two sorted linked lists
    ```python
    def merge_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        if list2 is None:
            return list1

        dummy = curr = ListNode(0, None)
        while list1 and list2:
            if list1.val <= list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next

        if list1:
            curr.next = list1
        if list2:
            curr.next = list2

        return dummy.next
    ```
- **[Tortoise and Hare Algorithm](https://web.ntnu.edu.tw/~algo/Function.html)**: Detect cycle / Find the start node of the cycle
    ```python
    def detect_cycle(head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

    def get_cycle_start(head: Optional[ListNode]) -> Optional[ListNode]:
        has_cycle = False

        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                has_cycle = True
                break

        if has_cycle:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
        else:
            return None
    ```


### Shortest Path


| Algorithm | Purpose | Time complexity | Space complexity | Handle negative weights? |
| -------- | -------- | -------- | -------- | -------- |
| Floyd-Warshall | **All-pair** shortest path | O(V^3^) | O(V^2^) | No |
| Dijkstra | **Single source** shortest path | O(ElogV) | O(V+E) | No |
| Bellman-ford | **Single source** shortest path | O(VE) | O(V+E) | Yes |

```python
def get_shortest_path_dijkstra(edges: dict, source: int, end: int) -> int:
    dist = [inf] * n  # n is the number of nodes
    dist[source] = 0
    min_heap = [(0, source)]
    while min_heap:
        curr_dist, curr_node = heapq.heappop(min_heap)
        if curr_node == end:
            break
        if curr_dist > dist[curr_node]:
            continue
        for nei, cost in edges[curr_node]:
            if dist[nei] > curr_dist + cost:
                dist[nei] = curr_dist + cost
                heapq.heappush(min_heap, (dist[nei], nei))

    return -1 if dist[end] == inf else dist[end]


def get_shortest_path_bellman_fold(graph: dict, source: int, end: int) -> int:
    dist = [inf] * n
    dist[source] = 0
    for _ in range(n - 1):
        updated = False
        for u, edges in graph.items():
            for v, w in edges:
                if dist[u] != inf and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    updated = True
        if not updated:
            break

    return -1 if dist[end] == inf else dist[end]
```


### Minimum Spanning Tree

- [Minimum Spanning Tree](https://medium.com/@ralph-tech/%E6%BC%94%E7%AE%97%E6%B3%95%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98-%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A8%B9-minimum-spanning-tree-mst-26c9482419a7)
    ```python
    def find_mst_prim(edges: dict) -> int:
        total_cost = 0
        min_heap = [(0, 0)]  # (cost[0], 0) assume 0 is the start node
        visited = [False] * n  # n is the number of node
        while min_heap:
            cost, source = heapq.heappop(min_heap)
            if visited[source]:
                continue

            visited[source] = True
            total_cost += cost
            for neighbor, cost in edges[source]:
                if not visited[neighbor]:
                    heapq.heappush(min_heap, (cost, neighbor))

        return -1 if not all(visited) else total_cost


    def find_mst_kruskal(n: int, edges: List[List[int]]) -> int:
        # edge element: (u, v, cost)
        sorted_edges = sorted(edges, key=lambda x: x[2])
        dsu = DSU(n)  # n is the number of nodes

        total_cost = 0
        num_groups = n
        for u, v, cost in sorted_edges:
            if dsu.union(u, v):
                total_cost += cost
                num_groups -= 1
                if num_groups == 1:
                    break

        return -1 if num_groups != 1 else total_cost
    ```


### Union Find / Disjoint Set Union

:::info
With union by rank, we always attach the smaller tree under the larger one, so the tree height grows very slowly.
Path compression flattens the tree during each find by directly connecting nodes to the root.

**Together, they guarantee an amortized time complexity of O(α(n)), where α(n) is the inverse Ackermann function, which is practically constant.**
:::

```python
class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x: int) -> int:
        # Path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        # Group by rank (group size)
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False

        if self.size[root_x] < self.size[root_y]:
            root_x, root_y = root_y, root_x

        self.parent[root_y] = root_x
        self.size[root_x] += self.size[root_y]
        return True
```


### Segment Tree

- Implement by the tree structure
    ```python
    class SegmentTreeNode:
        def __init__(self, start: int, end: int, val: int, left = None, right = None):
            self.start = start
            self.end = end
            self.val = val
            self.left = left
            self.right = right


    class SegmentTree:
        @classmethod
        def build(cls, start: int, end: int, nums: List[int]) -> SegmentTreeNode:
            """
                - TC: O(N)
                - SC: O(N)
            """
            if start == end:
                return SegmentTreeNode(start, end, nums[start])

            mid = (start + end) // 2
            left_subtree = cls.build(start, mid, nums)
            right_subtree = cls.build(mid + 1, end, nums)
            return SegmentTreeNode(start, end, left_subtree.val + right_subtree.val, left_subtree, right_subtree)

        @classmethod
        def query(cls, root: SegmentTreeNode, start: int, end: int) -> int:
            """
                - TC: O(logN)
            """
            if root.start == start and root.end == end:
                return root.val

            mid = (root.start + root.end) // 2
            if end <= mid:
                return cls.query(root.left, start, end)
            elif start > mid:
                return cls.query(root.right, start, end)
            else:
                return cls.query(root.left, start, mid) + cls.query(root.right, mid + 1, end)

        @classmethod
        def update(cls, root: SegmentTreeNode, index: int, value: int) -> None:
            """
                - TC: O(logN)
            """
            if root.start == root.end == index:
                root.val = value
                return

            mid = (root.start + root.end) // 2
            if index <= mid:
                cls.update(root.left, index, value)
            else:
                cls.update(root.right, index, value)
            root.val = root.left.val + root.right.val
    ```

- Implement by array (with size 4 * N)
    ```python
    class SegmentTree:
        def __init__(self, nums: List[int], merge_fn = lambda x, y: x + y):
            self.n = len(nums)
            self.merge_fn = merge_fn

            self.tree = [0] * (4 * self.n)
            if self.n > 0:
                self._build(nums, 1, 0, self.n - 1)

        def _build(self, nums: List[int], node: int, start: int, end: int) -> None:
            if start == end:
                self.tree[node] = nums[start]
                return

            mid = (start + end) // 2
            self._build(nums, 2 * node, start, mid)
            self._build(nums, 2 * node + 1, mid + 1, end)
            self.tree[node] = self.merge_fn(self.tree[2 * node], self.tree[2 * node + 1])

        def update(self, index: int, value: int) -> None:
            self._update(1, 0, self.n - 1, index, value)

        def _update(self, node: int, start: int, end: int, index: int, value: int) -> None:
            if start == end == index:
                self.tree[node] = value
                return
            mid = (start + end) // 2
            if index <= mid:
                self._update(node * 2, start, mid, index, value)
            else:
                self._update(node * 2 + 1, mid + 1, end, index, value)
            self.tree[node] = self.merge_fn(self.tree[node * 2], self.tree[node * 2 + 1])

        def query(self, left: int, right: int) -> int:
            return self._query(1, 0, self.n - 1, left, right)

        def _query(self, node: int, start: int, end: int, left: int, right: int) -> int:
            if right < start or left > end:
                return 0  # depends on the merge function: (add: 0) / (max: -inf) / (min: inf)

            if left <= start and end <= right:
                return self.tree[node]

            mid = (start + end) // 2
            res_left = self._query(node * 2, start, mid, left, right)
            res_right = self._query(node * 2 + 1, mid + 1, end, left, right)

            return self.merge_fn(res_left, res_right)
    ```


### Binary Indexed Tree / Fenwick Tree

```python
class BIT:
    def __init__(self, n: int):
        self.sums = [0] * (n + 1)
    
    def update(self, idx: int, delta: int) -> None:
        while idx < len(self.sums):
            self.sums[idx] += delta
            idx += idx & -idx

    def query(self, idx: int) -> int:
        res = 0
        while idx > 0:
            res += self.sums[idx]
            idx -= idx & -idx
        return res
```


## Time / Space Complexity Analyses

The solution space of the following topics
* Permutation: N!
* Combination: C(N, K) = N! / (K! * (N - K)!)
* Subsets: 2 ** N