# 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`
- `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
Sign in with Wallet
Connect another wallet