Skip to main content

Advanced Data Structures & Algorithms

Table of Contents​

  1. LRU Cache
  2. Dynamic Programming
  3. Graph Algorithms
  4. Tree & Binary Search Tree
  5. Heap & Priority Queue
  6. Trie (Prefix Tree)
  7. Union-Find (Disjoint Set)
  8. Interview Patterns
  9. Interview Questions
  10. Core Techniques and Patterns
  11. Graphs, Trees and Search
  12. Range Query Structures
  13. Data Structures Behind Backend Systems
  14. Senior / Principal — Real World Algorithm Scenarios

LRU Cache​

Overview​

An LRU (Least Recently Used) Cache is a data structure that discards the least recently used items first when the cache reaches its capacity. It requires O(1) time for both get and put operations.

Implementation Strategy: To achieve O(1) time complexity:

  • Hash Map (Dictionary): Provides O(1) access to items by key.
  • Doubly Linked List: Maintains the order of usage. The "most recently used" is at the head, and "least recently used" is at the tail.
# ============================================
# LRU CACHE IMPLEMENTATION
# ============================================

class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.prev = None
self.next = None

class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # Map key to Node

# Dummy head and tail to avoid null checks
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head

def _remove(self, node):
"""Remove an existing node from the linked list."""
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node

def _add(self, node):
"""Add a new node right after the head (most recently used)."""
next_node = self.head.next
self.head.next = node
node.prev = self.head
node.next = next_node
next_node.prev = node

def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
self._remove(node)
self._add(node)
return node.value
return -1

def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])

new_node = Node(key, value)
self._add(new_node)
self.cache[key] = new_node

if len(self.cache) > self.capacity:
# Remove from tail (least recently used)
lru_node = self.tail.prev
self._remove(lru_node)
del self.cache[lru_node.key]

# Alternatively, using Python's collections.OrderedDict
from collections import OrderedDict

class LRUCacheOrderedDict:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity

def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]

def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)

Interviewer Notes:

  • Why a Doubly Linked List? Because it allows O(1) deletion if you have the node reference.
  • Why a Hash Map? For O(1) lookup.
  • Space Complexity: O(Capacity).

Dynamic Programming​

Overview​

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into overlapping subproblems and storing results to avoid redundant computation.

┌─────────────────────────────────────────────────────────────┐
│ DYNAMIC PROGRAMMING │
├─────────────────────────────────────────────────────────────┤
│ │
│ When to use DP: │
│ • Problem can be broken into subproblems │
│ • Subproblems overlap (share common subproblems) │
│ • Optimal substructure (optimal solution contains │
│ optimal solutions to subproblems) │
│ │
│ Two approaches: │
│ • Top-Down (Memoization) - Recursive + caching │
│ • Bottom-Up (Tabulation) - Iterative + DP table │
│ │
└─────────────────────────────────────────────────────────────┘

Fibonacci Sequence​

# ============================================
# FIBONACCI - Three Approaches
# ============================================

# Naive Recursive (Exponential Time)
def fib_naive(n: int) -> int:
"""O(2^n) time - VERY SLOW"""
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)

# Top-Down with Memoization
def fib_memo(n: int, memo: dict = None) -> int:
"""O(n) time, O(n) space"""
if memo is None:
memo = {}

if n in memo:
return memo[n]
if n <= 1:
return n

memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]

# Bottom-Up Tabulation
def fib_tab(n: int) -> int:
"""O(n) time, O(n) space - Iterative"""
if n <= 1:
return n

dp = [0] * (n + 1)
dp[1] = 1

for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]

return dp[n]

# Space-Optimized
def fib_optimized(n: int) -> int:
"""O(n) time, O(1) space"""
if n <= 1:
return n

prev2, prev1 = 0, 1

for _ in range(2, n + 1):
curr = prev1 + prev2
prev2, prev1 = prev1, curr

return prev1

Classic DP Problems​

# ============================================
# 1. CLIMBING STAIRS
# Problem: Count ways to reach top of n stairs (1 or 2 steps at a time)
# ============================================

def climb_stairs(n: int) -> int:
"""
Approach: dp[i] = number of ways to reach step i
dp[i] = dp[i-1] + dp[i-2]
"""
if n <= 2:
return n

dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2

for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]

return dp[n]

# Space-optimized
def climb_stairs_optimized(n: int) -> int:
if n <= 2:
return n

prev2, prev1 = 1, 2

for _ in range(3, n + 1):
prev2, prev1 = prev1, prev2 + prev1

return prev1


# ============================================
# 2. COIN CHANGE
# Problem: Minimum coins needed to make amount
# ============================================

def coin_change(coins: list[int], amount: int) -> int:
"""
Approach: dp[i] = min coins to make amount i
dp[i] = min(dp[i], dp[i - coin] + 1) for each coin
"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0

for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0:
dp[i] = min(dp[i], dp[i - coin] + 1)

return dp[amount] if dp[amount] != float('inf') else -1

# With path reconstruction
def coin_change_with_path(coins: list[int], amount: int) -> tuple:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
parent = [-1] * (amount + 1)

for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0 and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
parent[i] = coin # coin used to reach amount i

if dp[amount] == float('inf'):
return -1, []

# Reconstruct the coins used
path = []
curr = amount
while curr > 0:
path.append(parent[curr])
curr -= parent[curr]

return dp[amount], path


# ============================================
# 3. LONGEST COMMON SUBSEQUENCE (LCS)
# Problem: Find longest subsequence common to two strings
# ============================================

def lcs(s1: str, s2: str) -> int:
"""
Approach: dp[i][j] = LCS length of s1[:i] and s2[:j]
If chars match: dp[i][j] = dp[i-1][j-1] + 1
Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
"""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

return dp[m][n]

# With path reconstruction
def lcs_with_path(s1: str, s2: str) -> tuple:
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]

# Fill DP table
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

# Reconstruct LCS
lcs_length = dp[m][n]
lcs_string = []
i, j = m, n

while i > 0 and j > 0:
if s1[i - 1] == s2[j - 1]:
lcs_string.append(s1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1

return lcs_length, ''.join(reversed(lcs_string))


# ============================================
# 4. LONGEST INCREASING SUBSEQUENCE (LIS)
# Problem: Find length of longest increasing subsequence
# ============================================

def lis(nums: list[int]) -> int:
"""
Approach: dp[i] = LIS ending at index i
dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
"""
if not nums:
return 0

n = len(nums)
dp = [1] * n

for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)

return max(dp)

# O(n log n) using Binary Search
def lis_binary_search(nums: list[int]) -> int:
"""O(n log n) - patience sorting approach"""
import bisect

if not nums:
return 0

tails = []

for num in nums:
pos = bisect.bisect_left(tails, num)

if pos == len(tails):
tails.append(num)
else:
tails[pos] = num

return len(tails)


# ============================================
# 5. 0/1 KNAPSACK
# Problem: Maximize value with weight constraint
# ============================================

def knapsack(values: list[int], weights: list[int], capacity: int) -> int:
"""
Approach: dp[i][w] = max value using first i items with capacity w
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
"""
n = len(values)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i - 1] <= w:
dp[i][w] = max(
dp[i - 1][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]
)
else:
dp[i][w] = dp[i - 1][w]

return dp[n][capacity]

# Space-optimized
def knapsack_optimized(values: list[int], weights: list[int], capacity: int) -> int:
n = len(values)
dp = [0] * (capacity + 1)

for i in range(n):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

return dp[capacity]


# ============================================
# 6. HOUSE ROBBER
# Problem: Max money without robbing adjacent houses
# ============================================

def rob(houses: list[int]) -> int:
"""
Approach: dp[i] = max money robbing houses[0..i]
dp[i] = max(dp[i-1], dp[i-2] + houses[i])
"""
if not houses:
return 0
if len(houses) == 1:
return houses[0]

prev2, prev1 = 0, houses[0]

for i in range(1, len(houses)):
curr = max(prev1, prev2 + houses[i])
prev2, prev1 = prev1, curr

return prev1


# ============================================
# 7. EDIT DISTANCE
# Problem: Min operations to convert word1 to word2
# ============================================

def min_distance(word1: str, word2: str) -> int:
"""
Operations: Insert, Delete, Replace
dp[i][j] = min operations to convert word1[:i] to word2[:j]
"""
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]

# Initialize: converting to/from empty string
for i in range(m + 1):
dp[i][0] = i # Delete all characters
for j in range(n + 1):
dp[0][j] = j # Insert all characters

for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # Delete
dp[i][j - 1], # Insert
dp[i - 1][j - 1] # Replace
)

return dp[m][n]


# ============================================
# 8. WORD BREAK
# Problem: Can string be segmented into dictionary words
# ============================================

def word_break(s: str, word_dict: list[str]) -> bool:
"""
Approach: dp[i] = True if s[:i] can be segmented
dp[i] = True if exists j < i where dp[j] and s[j:i] in dict
"""
word_set = set(word_dict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True

for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break

return dp[n]


# ============================================
# 9. UNIQUE PATHS
# Problem: Unique paths from top-left to bottom-right
# ============================================

def unique_paths(m: int, n: int) -> int:
"""Number of unique paths (only right and down moves)"""
dp = [[1] * n for _ in range(m)]

for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

return dp[m - 1][n - 1]

def unique_paths_with_obstacles(grid: list[list[int]]) -> int:
"""With obstacles (1 = blocked)"""
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]

for i in range(m):
for j in range(n):
if grid[i][j] == 1:
dp[i][j] = 0
elif i == 0 and j == 0:
dp[i][j] = 1
else:
if i > 0:
dp[i][j] += dp[i - 1][j]
if j > 0:
dp[i][j] += dp[i][j - 1]

return dp[m - 1][n - 1]

DP Patterns Summary​

┌─────────────────────────────────────────────────────────────┐
│ DP PATTERNS │
├─────────────────────────────────────────────────────────────┤
│ │
│ Pattern 1: Min/Max Path Sum │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]│ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ Pattern 2: Subsequence │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ if match: dp[i][j] = dp[i-1][j-1] + 1 │ │
│ │ else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ Pattern 3: String Editing │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ Pattern 4: 0/1 Knapsack │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ dp[w] = max(dp[w], dp[w-weight[i]] + value[i]) │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ Pattern 5: Partition │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ dp[i] = any(dp[j] and can_partition(j+1, i)) │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ Pattern 6: Interval / Partition Cost │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ dp[i] = max/min(dp[i], dp[j] + cost(j, i)) │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘

Graph Algorithms​

Graph Representations​

from collections import defaultdict, deque
import heapq

class Graph:
"""Graph representations"""

# Adjacency List
@staticmethod
def adjacency_list(edges: list[tuple], directed=False) -> dict:
"""Build adjacency list from edge list"""
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
if not directed:
graph[v].append(u)
return dict(graph)

# Adjacency Matrix
@staticmethod
def adjacency_matrix(edges: list[tuple], n: int) -> list[list[int]]:
"""Build adjacency matrix"""
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
matrix[u][v] = 1
return matrix

# Weighted adjacency list
@staticmethod
def weighted_adjacency_list(edges: list[tuple], directed=False) -> dict:
"""Build weighted adjacency list"""
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
if not directed:
graph[v].append((u, w))
return dict(graph)

BFS and DFS​

# ============================================
# BREADTH-FIRST SEARCH (BFS)
# Time: O(V + E), Space: O(V)
# ============================================

def bfs(graph: dict, start: int) -> list[int]:
"""Level-order traversal"""
visited = set([start])
queue = deque([start])
result = []

while queue:
node = queue.popleft()
result.append(node)

for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)

return result

def bfs_shortest_path(graph: dict, start: int, end: int) -> list[int]:
"""BFS to find shortest path in unweighted graph"""
if start == end:
return [start]

visited = {start}
queue = deque([(start, [start])])

while queue:
node, path = queue.popleft()

for neighbor in graph.get(node, []):
if neighbor == end:
return path + [neighbor]

if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))

return []


# ============================================
# DEPTH-FIRST SEARCH (DFS)
# Time: O(V + E), Space: O(V)
# ============================================

def dfs_recursive(graph: dict, node: int, visited: set = None) -> list[int]:
"""Recursive DFS"""
if visited is None:
visited = set()

visited.add(node)
result = [node]

for neighbor in graph.get(node, []):
if neighbor not in visited:
result.extend(dfs_recursive(graph, neighbor, visited))

return result

def dfs_iterative(graph: dict, start: int) -> list[int]:
"""Iterative DFS using stack"""
visited = set([start])
stack = [start]
result = []

while stack:
node = stack.pop()
result.append(node)

for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)

return result

def dfs_topological_sort(graph: dict) -> list[int]:
"""Topological sort using DFS"""
visited = set()
stack = []

def dfs(node):
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs(neighbor)
stack.append(node)

for node in graph:
if node not in visited:
dfs(node)

return stack[::-1]


# ============================================
# DETECT CYCLE IN DIRECTED GRAPH
# ============================================

def has_cycle_directed(graph: dict) -> bool:
"""Detect cycle using DFS with three states"""
WHITE, GRAY, BLACK = 0, 1, 2
color = {node: WHITE for node in graph}

def dfs(node):
color[node] = GRAY
for neighbor in graph.get(node, []):
if color[neighbor] == GRAY:
return True # Back edge = cycle
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[node] = BLACK
return False

for node in graph:
if color[node] == WHITE and dfs(node):
return True
return False


def has_cycle_undirected(graph: dict) -> bool:
"""Detect cycle in undirected graph"""
visited = set()

def dfs(node, parent):
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor == parent:
continue
if neighbor in visited:
return True
if dfs(neighbor, node):
return True
return False

for node in graph:
if node not in visited:
if dfs(node, -1):
return True
return False

Shortest Path Algorithms​

# ============================================
# DIJKSTRA'S ALGORITHM
# Time: O((V + E) log V), Space: O(V)
# ============================================

def dijkstra(graph: dict, start: int) -> dict:
"""
Find shortest path from start to all nodes
Assumes non-negative edge weights
"""
distances = {node: float('inf') for node in graph}
for edges in graph.values(): # include nodes that only appear as neighbors
for neighbor, _ in edges:
distances.setdefault(neighbor, float('inf'))
distances[start] = 0
pq = [(0, start)] # (distance, node)
visited = set()

while pq:
dist, node = heapq.heappop(pq)

if node in visited:
continue
visited.add(node)

for neighbor, weight in graph.get(node, []):
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))

return distances

def dijkstra_with_path(graph: dict, start: int, end: int) -> tuple:
"""Dijkstra with path reconstruction"""
distances = {node: float('inf') for node in graph}
for edges in graph.values(): # include nodes that only appear as neighbors
for neighbor, _ in edges:
distances.setdefault(neighbor, float('inf'))
distances[start] = 0
parent = {start: None}
pq = [(0, start)]

while pq:
dist, node = heapq.heappop(pq)

if dist > distances[node]:
continue

if node == end:
# Reconstruct path
path = []
curr = end
while curr is not None:
path.append(curr)
curr = parent.get(curr)
return dist, path[::-1]

for neighbor, weight in graph.get(node, []):
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
parent[neighbor] = node
heapq.heappush(pq, (new_dist, neighbor))

return -1, []


# ============================================
# BELLMAN-FORD ALGORITHM
# Time: O(V * E), Space: O(V)
# ============================================

def bellman_ford(edges: list[tuple], n: int, start: int) -> tuple:
"""
Find shortest path with negative weights
Also detects negative cycles
Returns: (distances, has_negative_cycle)
"""
distances = [float('inf')] * n
distances[start] = 0

# Relax edges n-1 times
for _ in range(n - 1):
for u, v, w in edges:
if distances[u] != float('inf') and distances[u] + w < distances[v]:
distances[v] = distances[u] + w

# Check for negative cycle
for u, v, w in edges:
if distances[u] != float('inf') and distances[u] + w < distances[v]:
return None, True # Negative cycle exists

return distances, False


# ============================================
# FLOYD-WARSHALL ALGORITHM
# Time: O(V^3), Space: O(V^2)
# ============================================

def floyd_warshall(n: int, edges: list[tuple], directed: bool = True) -> list[list[int]]:
"""
All-pairs shortest path
dist[i][j] = shortest distance from i to j
"""
INF = float('inf')
dist = [[INF] * n for _ in range(n)]

# Initialize distances
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w) # keep the cheapest parallel edge
if not directed:
dist[v][u] = min(dist[v][u], w)

# Floyd-Warshall
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]

return dist


# ============================================
# BFS FOR SHORTEST PATH (UNWEIGHTED)
# ============================================

def shortest_path_unweighted(graph: dict, start: int, end: int) -> int:
"""Shortest path in unweighted graph"""
if start == end:
return 0

visited = {start}
queue = deque([(start, 0)])

while queue:
node, dist = queue.popleft()

for neighbor in graph.get(node, []):
if neighbor == end:
return dist + 1
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))

return -1

Minimum Spanning Tree​

# ============================================
# PRIM'S ALGORITHM
# Time: O(E log V), Space: O(V)
# ============================================

def prim_mst(graph: dict) -> tuple:
"""
Find MST using Prim's algorithm
Returns: (total_weight, mst_edges)
"""
if not graph:
return 0, []

visited = set()
min_edges = [(0, 0, -1)] # (weight, to_node, from_node)
mst_edges = []
total_weight = 0

while min_edges and len(visited) < len(graph):
weight, node, parent = heapq.heappop(min_edges)

if node in visited:
continue

visited.add(node)
total_weight += weight

if parent != -1:
mst_edges.append((parent, node, weight))

for neighbor, w in graph.get(node, []):
if neighbor not in visited:
heapq.heappush(min_edges, (w, neighbor, node))

return total_weight, mst_edges


# ============================================
# KRUSKAL'S ALGORITHM
# Time: O(E log E), Space: O(V)
# ============================================

class UnionFind:
"""Union-Find (Disjoint Set Union)"""

def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n

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

def union(self, x: int, y: int) -> bool:
"""Return True if union was performed (no cycle)"""
px, py = self.find(x), self.find(y)
if px == py:
return False # Same set = cycle

# Union by rank
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True

def kruskal_mst(n: int, edges: list[tuple]) -> tuple:
"""
Find MST using Kruskal's algorithm
edges: [(u, v, weight), ...]
"""
# Sort edges by weight
edges.sort(key=lambda x: x[2])

uf = UnionFind(n)
mst_edges = []
total_weight = 0

for u, v, w in edges:
if uf.union(u, v):
mst_edges.append((u, v, w))
total_weight += w

return total_weight, mst_edges

Graph Algorithms Summary​

┌─────────────────────────────────────────────────────────────┐
│ GRAPH ALGORITHMS CHEAT SHEET │
├─────────────────────────────────────────────────────────────┤
│ │
│ BFS/DFS │
│ ├── BFS: Shortest path (unweighted), Level order │
│ └── DFS: Topological sort, Cycle detection, Path finding │
│ │
│ Shortest Path │
│ ├── Dijkstra: Non-negative weights, O(E log V) │
│ ├── Bellman-Ford: Any weights, O(VE), detects negative │
│ │ cycles │
│ └── Floyd-Warshall: All-pairs, O(V³) │
│ │
│ Minimum Spanning Tree │
│ ├── Prim: Dense graphs, O(V²) or O(E log V) │
│ └── Kruskal: Sparse graphs, O(E log E) │
│ │
│ Topological Sort │
│ ├── DFS-based: O(V + E) │
│ └── Kahn's: BFS-based, O(V + E) │
│ │
│ Union-Find │
│ ├── With path compression: Almost O(1) │
│ └── With union by rank: Almost O(1) │
│ │
└─────────────────────────────────────────────────────────────┘

Tree & Binary Search Tree​

BST Implementation​

class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None

class BST:
"""Binary Search Tree implementation"""

def __init__(self):
self.root = None

def insert(self, val):
self.root = self._insert(self.root, val)

def _insert(self, node, val):
if not node:
return TreeNode(val)
if val < node.val:
node.left = self._insert(node.left, val)
else:
node.right = self._insert(node.right, val)
return node

def search(self, val) -> bool:
return self._search(self.root, val)

def _search(self, node, val) -> bool:
if not node:
return False
if val == node.val:
return True
elif val < node.val:
return self._search(node.left, val)
else:
return self._search(node.right, val)

def delete(self, val):
self.root = self._delete(self.root, val)

def _delete(self, node, val):
if not node:
return None
if val < node.val:
node.left = self._delete(node.left, val)
elif val > node.val:
node.right = self._delete(node.right, val)
else:
# Node with only one child or no child
if not node.left:
return node.right
if not node.right:
return node.left
# Node with two children: get inorder successor
successor = self._min_node(node.right)
node.val = successor.val
node.right = self._delete(node.right, successor.val)
return node

def _min_node(self, node):
while node.left:
node = node.left
return node

def inorder(self):
result = []
self._inorder(self.root, result)
return result

def _inorder(self, node, result):
if node:
self._inorder(node.left, result)
result.append(node.val)
self._inorder(node.right, result)

def is_balanced(self) -> bool:
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1:
return -1
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1
return max(left, right) + 1
return check(self.root) != -1

Tree Traversals​

def inorder_recursive(root: TreeNode) -> list:
"""Left, Root, Right"""
result = []
def traverse(node):
if not node:
return
traverse(node.left)
result.append(node.val)
traverse(node.right)
traverse(root)
return result

def preorder_recursive(root: TreeNode) -> list:
"""Root, Left, Right"""
result = []
def traverse(node):
if not node:
return
result.append(node.val)
traverse(node.left)
traverse(node.right)
traverse(root)
return result

def postorder_recursive(root: TreeNode) -> list:
"""Left, Right, Root"""
result = []
def traverse(node):
if not node:
return
traverse(node.left)
traverse(node.right)
result.append(node.val)
traverse(root)
return result

def level_order(root: TreeNode) -> list[list]:
"""BFS - Level by level"""
if not root:
return []
result = []
queue = deque([root])

while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)

return result

def zigzag_level_order(root: TreeNode) -> list[list]:
"""Zigzag traversal"""
if not root:
return []
result = []
queue = deque([root])
left_to_right = True

while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level if left_to_right else level[::-1])
left_to_right = not left_to_right

return result

def inorder_iterative(root: TreeNode) -> list:
"""Iterative inorder using stack"""
result = []
stack = []
current = root

while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right

return result

def morris_inorder(root: TreeNode) -> list:
"""O(1) space inorder traversal"""
result = []
current = root

while current:
if not current.left:
result.append(current.val)
current = current.right
else:
# Find inorder predecessor
pre = current.left
while pre.right and pre.right != current:
pre = pre.right

if not pre.right:
pre.right = current
current = current.left
else:
pre.right = None
result.append(current.val)
current = current.right

return result

Heap & Priority Queue​

import heapq
from typing import TypeVar

T = TypeVar('T')

class MinHeap:
"""Min Heap implementation"""

def __init__(self):
self.heap = []

def push(self, item):
heapq.heappush(self.heap, item)

def pop(self):
return heapq.heappop(self.heap)

def peek(self):
return self.heap[0] if self.heap else None

def __len__(self):
return len(self.heap)

class MaxHeap:
"""Max Heap implementation"""

def __init__(self):
self.heap = []

def push(self, item):
heapq.heappush(self.heap, -item) # Negate for max

def pop(self):
return -heapq.heappop(self.heap)

def peek(self):
return -self.heap[0] if self.heap else None

class MedianFinder:
"""295. Find Median from Data Stream"""

def __init__(self):
self.small = [] # Max heap (negatives)
self.large = [] # Min heap

def add_num(self, num: int):
# Add to max heap
heapq.heappush(self.small, -num)

# Balance: largest of small <= smallest of large
if self.small and self.large and -self.small[0] > self.large[0]:
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)

# Ensure size balance
if len(self.small) > len(self.large) + 1:
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
elif len(self.large) > len(self.small):
val = -heapq.heappop(self.large)
heapq.heappush(self.small, val)

def find_median(self) -> float:
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2

def k_closest_points(points: list[tuple], k: int) -> list[tuple]:
"""Find k closest points to origin using heap"""
heap = []

for point in points:
dist = point[0] ** 2 + point[1] ** 2
heapq.heappush(heap, (dist, point))

return [heapq.heappop(heap)[1] for _ in range(k)]

def top_k_frequent(nums: list[int], k: int) -> list[int]:
"""Top K Frequent Elements"""
counter = {}
for num in nums:
counter[num] = counter.get(num, 0) + 1

# Min heap of size k
heap = []
for num, freq in counter.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap)

return [num for _, num in heap]

Trie (Prefix Tree)​

class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0

class Trie:
"""Prefix Tree for efficient string operations"""

def __init__(self):
self.root = TrieNode()

def insert(self, word: str):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.count += 1
node.is_end = True

def search(self, word: str) -> bool:
node = self._find_node(word)
return node is not None and node.is_end

def starts_with(self, prefix: str) -> bool:
return self._find_node(prefix) is not None

def _find_node(self, prefix: str) -> TrieNode:
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return node

def longest_common_prefix(self, words: list[str]) -> str:
if not words:
return ""

trie = Trie()
for word in words:
trie.insert(word)

result = []
node = trie.root

while len(node.children) == 1 and not node.is_end:
char = list(node.children.keys())[0]
result.append(char)
node = node.children[char]

return ''.join(result)

def autocomplete(self, prefix: str) -> list[str]:
node = self._find_node(prefix)
if not node:
return []

results = []
self._dfs(node, prefix, results)
return results

def _dfs(self, node, path, results):
if node.is_end:
results.append(path)
for char, child in node.children.items():
self._dfs(child, path + char, results)

Union-Find (Disjoint Set)​

class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
self.count = n # Number of components

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:
"""Union by rank"""
px, py = self.find(x), self.find(y)
if px == py:
return False

if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.count -= 1
return True

def connected(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)

def count_components(self) -> int:
return self.count

# Number of Islands problem
def num_islands(grid: list[list[str]]) -> int:
if not grid:
return 0

m, n = len(grid), len(grid[0])
uf = UnionFind(m * n)

for i in range(m):
for j in range(n):
if grid[i][j] == '1':
idx = i * n + j
# Connect to right neighbor
if j + 1 < n and grid[i][j + 1] == '1':
uf.union(idx, i * n + j + 1)
# Connect to bottom neighbor
if i + 1 < m and grid[i + 1][j] == '1':
uf.union(idx, (i + 1) * n + j)

# Count unique roots for islands
islands = set()
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
islands.add(uf.find(i * n + j))

return len(islands)

Interview Patterns​

┌─────────────────────────────────────────────────────────────┐
│ ALGORITHM INTERVIEW PATTERNS │
├─────────────────────────────────────────────────────────────┤
│ │
│ TWO POINTERS │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ • Sorted array pairs (Two Sum II) │ │
│ │ • Container with most water │ │
│ │ • Remove duplicates │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ SLIDING WINDOW │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ • Maximum sum subarray of size k │ │
│ │ • Longest substring without repeating chars │ │
│ │ • Minimum window substring │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ FAST & SLOW POINTERS │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ • Linked list cycle detection │ │
│ │ • Middle of linked list │ │
│ │ • Palindrome linked list │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ MERGE INTERVALS │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ • Meeting rooms │ │
│ │ • Insert interval │ │
│ │ • Non-overlapping intervals │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ CYCLIC SORT │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ • Find missing number │ │
│ │ • Find duplicate │ │
│ │ • Find all duplicates │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ REVERSING LINKED LIST │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ • Reverse in groups │ │
│ │ • Rotate list │ │
│ │ • Reorder list │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ BFS │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ • Level order traversal │ │
│ │ • Shortest path in binary matrix │ │
│ │ • Minimum Knight moves │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ DFS │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ • Path sum │ │
│ │ • Number of islands │ │
│ │ • Word search │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ BACKTRACKING │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ • N-Queens │ │
│ │ • Sudoku solver │ │
│ │ • Permutations/Combinations │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ DYNAMIC PROGRAMMING │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ • 0/1 Knapsack │ │
│ │ • Longest common subsequence │ │
│ │ • House robber │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘

Interview Questions​

Q1: What is the time complexity of Binary Search and when is it valid?​

Binary search is O(log n). Valid only on a sorted array (or monotonic predicate). Each step halves the search space by comparing the middle element. Variants: find first/last occurrence, search in rotated array, and binary search on the answer (minimize/maximize over a predicate).

Q2: How does memoization differ from tabulation (DP)?​

Both solve overlapping subproblems. Memoization (top-down): recursive with a cache — easier to write, may hit recursion depth. Tabulation (bottom-up): iterative filling a table — avoids recursion, often more efficient and easier to optimize to O(1) space. Choose memoization for complex state transitions, tabulation for simple index-based DP.

Q3: Explain BFS vs DFS and when each is preferred?​

BFS: level-order via queue, shortest path in unweighted graphs, O(V+E). DFS: depth-first via stack/recursion, good for connectivity, topological sort, cycles, backtracking. BFS when distance matters (maze, shortest path); DFS for path existence, island count, tree traversals.

Q4: What is a sliding window and when do you use it?​

Sliding window maintains a subarray/substring range with two pointers, expanding/shrinking to satisfy a condition, giving O(n) instead of O(n²) brute force. Use for: longest substring without repeating chars, max sum of k-sized window, min window containing chars.

Q5: How does the Two Pointers technique work?​

Two pointers (left/right or fast/slow) traverse the array from opposite ends or different speeds to find pairs or detect cycles. Use for: two-sum in sorted array, palindrome checks, removing duplicates in-place, detecting cycles in linked lists (Floyd's tortoise-hare).

Q6: What is the time and space complexity of Merge Sort?​

Merge Sort: O(n log n) time, O(n) space (auxiliary array for merging). Stable, divide-and-conquer: split into halves, sort recursively, merge. Use when stable sorting with guaranteed worst-case matters. Quick Sort averages O(n log n) with O(log n) stack, but worst-case O(n²) without good pivot.

Q7: What is a Trie and what problems does it solve?​

Trie (prefix tree) stores strings with shared prefixes as nodes, enabling O(L) lookup/insert for word of length L. Solves: autocomplete, prefix matching, spell checking, word search in dictionaries. Trade-off: more memory than hash maps for random data, but prefix operations are natural.

Q8: What is the Union-Find (Disjoint Set) and its complexity?​

Union-Find tracks connected components with two ops: find (with path compression) and union (with union by rank). Nearly O(α(n)) ≈ O(1) amortized. Solves: connected components in graphs, detecting cycles in undirected graphs (Kruskal), number of islands, friend circles.

Q9: How does a hash map achieve O(1) and what breaks it?​

Keys are hashed into buckets, giving O(1) average lookups. Lookups degrade towards O(n) when many keys collide (a weak hash function or adversarial keys, i.e. hash flooding). Resizing is not the problem for lookups: a single insert that triggers a resize costs O(n), but inserts stay O(1) amortized. Python dicts use open addressing and resize at about 2/3 load, and Python randomizes string hashes per process to resist hash flooding. Java 8+ turns long collision chains into balanced trees, capping a bucket at O(log n). Mitigations: a good (ideally keyed) hash function, sensible capacity planning, and limiting the number of keys accepted from untrusted input.

Q10: What is the difference between a stack and a queue?​

Stack: LIFO (push/pop on top) — function calls, undo, bracket matching. Queue: FIFO (enqueue/dequeue) — task scheduling, BFS, buffering. Python: list as stack (append/pop), collections.deque as queue.

Q11: How do you detect a cycle in a linked list?​

Floyd's tortoise-hare: slow moves 1 step, fast moves 2. If they meet → cycle exists; O(n) time, O(1) space. To find cycle start, reset one pointer to head and advance both one step until they meet. Hash set also works but O(n) space.

Q12: What is the complexity of heap operations?​

Push/pop: O(log n). Peek: O(1). Build-heap: O(n). Heaps give efficient min/max extraction — used for priority queues, top-K problems (heap of size K), Dijkstra, and merging K sorted lists.

Q13: What is the difference between greedy and dynamic programming?​

Greedy: make locally optimal choice at each step, never reconsider — O(n) or O(n log n), but only correct when the greedy choice property holds (e.g., coin change with standard denominations, activity selection). DP: explores all substructure states and combines — correct when overlapping subproblems + optimal substructure. Use DP when greedy fails (non-standard coins, 0/1 knapsack).

Q14: What is the difference between a binary search tree and a heap?​

BST: ordered — in-order traversal gives sorted output; balanced BST gives O(log n) search/insert. Heap: partially ordered — only min/max at root; O(log n) insert/extract, but no search, no sorted traversal. BST for ordered operations; heap for priority extraction.

Q15: What is topological sort and how does it work?​

Linear ordering of DAG nodes such that every edge u→v has u before v. Implemented via DFS post-order reversal or Kahn's algorithm (indegree counting + queue). Used for: task scheduling with dependencies, build order, course prerequisites, package managers.

Q16: What is Kadane's algorithm?​

Finds the maximum subarray sum in O(n): iterate, keep current = max(num, current+num), track best = max(best, current). Classic: [-2,1,-3,4,-1,2,1,-5,4] → 6 ([4,-1,2,1]). Extend to 2D (max submatrix) with column prefix sums.

Q17: What is the difference between an array and a linked list?​

Array: O(1) index access, contiguous memory, O(n) insert/delete in middle (shift), cache-friendly. Linked list: O(1) insert/delete at known node (O(n) to find), no contiguity, worse cache locality, extra pointer memory. Choose by access vs modification pattern.

Q18: What is the complexity of Dijkstra vs Bellman-Ford?​

Dijkstra: O((V+E) log V) with heap, works only with non-negative weights — greedy, no revisit if shortest found. Bellman-Ford: O(V·E), handles negative weights and detects negative cycles — used in routing protocols (RIP), currency arbitrage detection.

Q19: What is a graph adjacency list vs matrix?​

Adjacency list: O(V+E) space, fast neighbors iteration — preferred for sparse graphs, most algorithm work. Matrix: O(V²) space, O(1) edge existence check — good for dense graphs or tiny V. Choose by density and operation type.

Q20: How do you find the K most frequent elements?​

Approach: hash map count O(n), then heap of size K O(n log K) or bucket sort O(n). This is the standard "top K" pattern — combining hash counting with a heap or buckets avoids full sort O(n log n).


Core Techniques and Patterns​

Q21: How do you analyze time and space complexity, including amortized cost?​

Complexity describes how cost grows with input size, ignoring constant factors:

  • Big-O is an upper bound, Big-Omega a lower bound, Big-Theta a tight bound. In interviews "O(n)" usually means the tight worst-case bound.
  • Worst vs average case: hash table lookup is O(1) on average but O(n) in the worst case; quicksort is O(n log n) on average but O(n²) in the worst case.
  • Amortized cost is the average cost per operation over a worst-case sequence of operations. Appending to a Python list is amortized O(1): occasionally the list reallocates and copies everything (O(n)), but capacity grows proportionally, so the total copy work over n appends is O(n).
  • Space includes auxiliary data structures and the recursion stack (a recursive DFS on a path-shaped graph uses O(n) stack).

Practical rule of thumb for interview constraints (assuming roughly 10^7–10^8 simple operations per second in a compiled language, fewer in Python):

Input size nTypically acceptable
n ≤ 20O(2^n), O(n!) for n ≤ ~10
n ≤ 500O(n³)
n ≤ 5,000O(n²)
n ≤ 10^6O(n log n) or O(n)
largerO(n), O(log n), or O(1) per query
import sys


def count_reallocations(n: int) -> int:
"""Count how often list capacity changes during n appends."""
items: list[int] = []
last_size = sys.getsizeof(items)
changes = 0
for i in range(n):
items.append(i)
size = sys.getsizeof(items)
if size != last_size:
changes += 1
last_size = size
return changes


for n in (1_000, 10_000, 100_000, 1_000_000):
print(n, count_reallocations(n))
# Reallocations grow roughly logarithmically with n, so the total copying
# work stays O(n) and each append is amortized O(1).

Interviewer Notes:

  • Strong candidates state complexity in terms of all relevant inputs (for example O(V + E), or O(n · L) for n strings of length L) instead of a single n.
  • Hidden costs in Python: slicing copies (O(k)), x in list is O(n), string concatenation in a loop can be O(n²), and list.pop(0) is O(n) (use collections.deque).

Common Mistakes:

  • Forgetting the recursion stack in space complexity.
  • Calling an operation "O(1)" when it is only amortized O(1) in a latency-sensitive context where the occasional O(n) spike matters.

Q22: Minimum Window Substring: how do you implement a variable-size sliding window correctly?​

Given strings s and t, find the shortest substring of s containing every character of t (with multiplicity). The variable-size window pattern is:

  1. Expand right one step at a time, updating window state.
  2. While the window is valid, record the answer and shrink from left.
  3. Each index enters and leaves the window at most once, so the total work is O(n).

The trick that keeps validity checks O(1) is a single missing counter instead of comparing two frequency maps on every step.

from collections import Counter


def min_window(s: str, t: str) -> str:
if not s or not t:
return ""
need = Counter(t) # how many of each char the window still needs (can go negative)
missing = len(t) # total chars still needed
left = 0
best_start, best_len = 0, float("inf")

for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1

while missing == 0: # window [left, right] is valid
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
left_ch = s[left]
need[left_ch] += 1
if need[left_ch] > 0: # we just removed a required char
missing += 1
left += 1

return "" if best_len == float("inf") else s[best_start:best_start + int(best_len)]


def longest_with_k_distinct(s: str, k: int) -> int:
"""Same template: longest substring with at most k distinct chars."""
counts: Counter[str] = Counter()
left = best = 0
for right, ch in enumerate(s):
counts[ch] += 1
while len(counts) > k: # invalid -> shrink
counts[s[left]] -= 1
if counts[s[left]] == 0:
del counts[s[left]]
left += 1
best = max(best, right - left + 1)
return best


print(min_window("ADOBECODEBANC", "ABC")) # BANC
print(min_window("a", "aa")) # "" (not enough a's)
print(longest_with_k_distinct("eceba", 2)) # 3 ("ece")

Complexity: O(|s| + |t|) time, O(alphabet) space.

Interviewer Notes:

  • Ask the candidate to state the window invariant out loud. Most bugs come from shrinking while invalid instead of while valid (or vice versa).
  • Sliding window needs the condition to be monotonic: growing the window never makes a "valid" window invalid in the opposite direction. With negative numbers in sum problems this breaks; use prefix sums instead (Q24).

Common Mistakes:

  • Rebuilding a Counter for each window (O(n · alphabet) or worse).
  • Deleting zero counts from need in min_window, which loses the "required" information.

Q23: How do you solve 3Sum in O(n²), and how do you avoid duplicate triplets?​

Sort the array, fix the first element i, then use two pointers on the remainder to find pairs summing to -nums[i]. Sorting makes the two-pointer move rule correct (sum too small → move lo right; too large → move hi left) and puts duplicates next to each other so they can be skipped.

def three_sum(nums: list[int]) -> list[tuple[int, int, int]]:
nums = sorted(nums)
result: list[tuple[int, int, int]] = []
n = len(nums)
for i in range(n - 2):
if nums[i] > 0:
break # smallest value positive -> no more zero sums
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate anchors
lo, hi = i + 1, n - 1
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
result.append((nums[i], nums[lo], nums[hi]))
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1 # skip duplicate second elements
return result


print(three_sum([-1, 0, 1, 2, -1, -4])) # [(-1, -1, 2), (-1, 0, 1)]
print(three_sum([0, 0, 0, 0])) # [(0, 0, 0)]

Complexity: O(n²) time, O(n) extra space for the sorted copy (O(1) extra if sorting in place is allowed, excluding output).

Interviewer Notes:

  • Generalization: k-Sum reduces to (k−1)-Sum recursively, bottoming out at 2-Sum with two pointers, giving O(n^(k−1)).
  • Ask why a hash-set approach is harder: it works for existence, but deduplicating triplets cleanly is much easier with sorted order.

Common Mistakes:

  • Deduplicating by putting results in a set after generating duplicates (works, but hides a weak understanding and wastes time).
  • Skipping duplicates of nums[i] by comparing with nums[i + 1], which skips valid triplets like (-1, -1, 2).

Q24: Subarray Sum Equals K: why does sliding window fail, and how do prefix sums fix it?​

Count contiguous subarrays whose sum equals k. With negative numbers, sliding window fails: extending the window can decrease the sum, so there is no monotonic rule for when to move left.

Prefix sums fix it. Let prefix[j] be the sum of the first j elements. The sum of nums[i:j] is prefix[j] - prefix[i]. So for each position we ask: "how many earlier prefixes equal current - k?" A hash map of prefix-sum counts answers that in O(1).

from collections import defaultdict
from itertools import accumulate


def subarray_sum_count(nums: list[int], k: int) -> int:
seen: dict[int, int] = defaultdict(int)
seen[0] = 1 # the empty prefix, so subarrays starting at index 0 count
current = count = 0
for x in nums:
current += x
count += seen[current - k]
seen[current] += 1
return count


class RangeSum:
"""Static array, many queries: O(n) build, O(1) per query."""

def __init__(self, nums: list[int]) -> None:
self.prefix = [0, *accumulate(nums)]

def query(self, left: int, right: int) -> int:
"""Sum of nums[left..right], inclusive."""
return self.prefix[right + 1] - self.prefix[left]


print(subarray_sum_count([1, 1, 1], 2)) # 2
print(subarray_sum_count([3, 4, -7, 1, 3, 3], 7)) # 3: [3,4], [3,4,-7,1,3,3], [1,3,3]

rs = RangeSum([5, -2, 8, 1, 4])
print(rs.query(1, 3)) # 7

Complexity: O(n) time, O(n) space.

Interviewer Notes:

  • Variants: longest subarray with sum k (store the first index of each prefix), subarray sum divisible by k (key by prefix % k), and equal numbers of 0s and 1s (map 0 → −1, then find sum 0).
  • If the array changes between queries, prefix sums need O(n) per update; that is when you move to a Fenwick tree or segment tree (Q36, Q37).

Common Mistakes:

  • Forgetting seen[0] = 1, which misses subarrays that start at index 0.
  • Updating seen[current] before reading seen[current - k], which counts the empty subarray when k == 0.

When the answer lies in a numeric range and a predicate feasible(x) is monotonic (once true, it stays true for all larger x), you can binary search over the answer space instead of over an array. Classic examples: minimum ship capacity to deliver packages in D days, minimum eating speed, smallest maximum partition sum, minimum time for N machines to finish a workload.

A reliable template: search for the first x in [lo, hi] where feasible(x) is true, maintaining the invariant "answer is in [lo, hi]", and loop while lo < hi.

from bisect import bisect_left, bisect_right
from collections.abc import Callable


def first_true(lo: int, hi: int, feasible: Callable[[int], bool]) -> int:
"""Smallest x in [lo, hi] with feasible(x) True. Assumes feasible(hi) is True."""
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid # mid might be the answer; keep it
else:
lo = mid + 1 # mid is definitely not the answer
return lo


def ship_within_days(weights: list[int], days: int) -> int:
def feasible(capacity: int) -> bool:
used_days, load = 1, 0
for w in weights:
if load + w > capacity:
used_days += 1
load = 0
load += w
return used_days <= days

# capacity must be at least the heaviest package, at most everything in one day
return first_true(max(weights), sum(weights), feasible)


print(ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)) # 15
print(ship_within_days([3, 2, 2, 4, 1, 4], 3)) # 6

# On sorted arrays, prefer the standard library:
scores = [10, 20, 20, 20, 30]
print(bisect_left(scores, 20), bisect_right(scores, 20)) # 1 4 -> 20 occurs 3 times

Complexity: O(n · log(sum − max)) for the shipping problem: log of the answer range times an O(n) feasibility check.

Interviewer Notes:

  • The interviewer is looking for two things: a proof that the predicate is monotonic, and correct bounds (the low bound must be feasible-or-not in a meaningful way, the high bound must be feasible).
  • In languages with fixed-width integers, (lo + hi) / 2 can overflow; use lo + (hi - lo) / 2. Python integers do not overflow, but mentioning it shows awareness.

Common Mistakes:

  • Mixing templates (while lo <= hi with hi = mid), which causes infinite loops.
  • Choosing lo = 1 instead of max(weights) and then writing a feasibility check that silently mishandles packages heavier than the capacity.

Q26: What is a monotonic stack, and how does it solve "next greater element" problems in O(n)?​

A monotonic stack keeps elements (usually indices) in increasing or decreasing order. When a new element breaks the order, you pop elements, and the new element is the answer for each popped one (their next greater / next smaller element). Every index is pushed and popped at most once, so the total is O(n) even though there is a loop inside a loop.

Typical problems: daily temperatures (days until a warmer day), next greater element, stock span, largest rectangle in a histogram, trapping rain water.

def daily_temperatures(temps: list[int]) -> list[int]:
"""For each day, how many days until a warmer temperature (0 if never)."""
answer = [0] * len(temps)
stack: list[int] = [] # indices with strictly decreasing temperatures
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answer


def largest_rectangle(heights: list[int]) -> int:
"""Largest rectangle area in a histogram."""
stack: list[int] = [] # indices with increasing heights
best = 0
for i, h in enumerate([*heights, 0]): # sentinel 0 flushes the stack at the end
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0 # first bar that can extend left
best = max(best, height * (i - left))
stack.append(i)
return best


print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73])) # [1, 1, 4, 2, 1, 1, 0, 0]
print(largest_rectangle([2, 1, 5, 6, 2, 3])) # 10

Complexity: O(n) time, O(n) space.

Interviewer Notes:

  • Ask which direction of monotonicity is needed: "next greater" keeps a decreasing stack; "next smaller" keeps an increasing stack.
  • Storing indices rather than values is almost always needed, because answers are distances or widths.

Common Mistakes:

  • Forgetting to process elements still on the stack at the end (the sentinel trick avoids a second loop).
  • Using <= vs < inconsistently, which double counts or misses equal heights.

Q27: How do you compute the maximum of every sliding window of size k in O(n)?​

A heap gives O(n log k) but needs lazy deletion of expired elements. A monotonic deque does it in O(n): keep indices whose values are in decreasing order. The front is always the current maximum. When a new value arrives, pop smaller values from the back (they can never be a maximum again while the new value is in the window), and pop the front if it has left the window.

from collections import deque


def max_sliding_window(nums: list[int], k: int) -> list[int]:
if k <= 0:
raise ValueError("k must be positive")
window: deque[int] = deque() # indices; nums[window] is decreasing
result: list[int] = []
for i, x in enumerate(nums):
while window and nums[window[-1]] <= x:
window.pop() # dominated: smaller and older
window.append(i)
if window[0] <= i - k:
window.popleft() # expired from the window
if i >= k - 1:
result.append(nums[window[0]])
return result


print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3)) # [3, 3, 5, 5, 6, 7]

# Backend use: peak requests-per-second over any 3-second window
rps = [120, 340, 290, 310, 800, 150, 160]
print(max_sliding_window(rps, 3)) # [340, 340, 800, 800, 800]

Complexity: O(n) time (each index enters and leaves the deque once), O(k) space.

Interviewer Notes:

  • The same deque technique optimizes some DP transitions of the form dp[i] = max(dp[j]) + cost over a sliding range of j.

Common Mistakes:

  • Storing values instead of indices, which makes it impossible to tell when the front has expired.
  • Using list.pop(0) for the front, which is O(k) per call.

Q28: How do you merge overlapping intervals and find the minimum number of meeting rooms?​

Merge intervals: sort by start; walk through, extending the last merged interval while the next one overlaps.

Minimum meeting rooms (the maximum number of overlapping intervals): sort by start and keep a min-heap of end times of meetings in progress. Before placing a meeting, free the room whose meeting ended earliest if it ends at or before the new start. The heap size peak is the answer. An equivalent sweep line sorts all start and end events.

import heapq


def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
merged: list[tuple[int, int]] = []
for start, end in sorted(intervals):
if merged and start <= merged[-1][1]: # overlaps (touching counts as overlap here)
merged[-1] = (merged[-1][0], max(merged[-1][1], end))
else:
merged.append((start, end))
return merged


def min_meeting_rooms(meetings: list[tuple[int, int]]) -> int:
ends: list[int] = [] # min-heap of end times for rooms in use
rooms = 0
for start, end in sorted(meetings):
if ends and ends[0] <= start:
heapq.heapreplace(ends, end) # reuse the room that freed up earliest
else:
heapq.heappush(ends, end)
rooms = max(rooms, len(ends))
return rooms


def max_concurrency_sweep(intervals: list[tuple[int, int]]) -> int:
"""Same answer with a sweep line; ends sort before starts at the same time."""
events = sorted([(s, 1) for s, _ in intervals] + [(e, -1) for _, e in intervals])
current = best = 0
for _, delta in events:
current += delta
best = max(best, current)
return best


print(merge_intervals([(1, 3), (8, 10), (2, 6), (15, 18)])) # [(1, 6), (8, 10), (15, 18)]
meetings = [(0, 30), (5, 10), (15, 20), (10, 15)]
print(min_meeting_rooms(meetings), max_concurrency_sweep(meetings)) # 2 2

Complexity: O(n log n) for sorting, plus O(n log n) heap operations; O(n) space.

Interviewer Notes:

  • Clarify whether [1, 2] and [2, 3] overlap. For meetings they usually do not (one ends as the next begins); for merging numeric ranges they often should. The tie-break in the sweep line (-1 sorts before +1) encodes "touching does not overlap".
  • Backend uses: peak concurrent sessions, capacity planning from call logs, merging maintenance windows, and computing free/busy calendars.

Common Mistakes:

  • Not sorting first, or sorting by end time when the algorithm assumes start time.
  • Mutating the caller's list with intervals.sort() without saying so.

Q29: How does Kahn's algorithm work, and how does it detect cycles in a dependency graph?​

Kahn's algorithm is BFS-based topological sorting:

  1. Compute the in-degree (number of prerequisites) of every node.
  2. Start a queue with all nodes of in-degree 0.
  3. Pop a node, append it to the order, and decrement the in-degree of its dependents; enqueue any that reach 0.
  4. If the order contains fewer nodes than the graph, the remaining nodes are part of (or blocked by) a cycle.

Compared with DFS-based topological sort, Kahn's naturally reports cycles, is iterative (no recursion limit), and can produce levels (batches that can run in parallel) or a deterministic order (use a heap instead of a queue).

from collections import deque


def topo_sort(deps: dict[str, list[str]]) -> list[str]:
"""deps maps task -> list of tasks it depends on."""
nodes = set(deps) | {d for ds in deps.values() for d in ds}
dependents: dict[str, list[str]] = {n: [] for n in nodes}
indegree = {n: 0 for n in nodes}
for task, requirements in deps.items():
for req in requirements:
dependents[req].append(task)
indegree[task] += 1

queue = deque(sorted(n for n in nodes if indegree[n] == 0))
order: list[str] = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in dependents[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)

if len(order) != len(nodes):
stuck = sorted(n for n in nodes if indegree[n] > 0)
raise ValueError(f"cycle detected among: {stuck}")
return order


build = {
"app": ["lib", "config"],
"lib": ["utils"],
"tests": ["app"],
"config": [],
"utils": [],
}
print(topo_sort(build)) # ['config', 'utils', 'lib', 'app', 'tests']

try:
topo_sort({"a": ["b"], "b": ["c"], "c": ["a"], "d": []})
except ValueError as exc:
print(exc) # cycle detected among: ['a', 'b', 'c']

Complexity: O(V + E) time and space.

Interviewer Notes:

  • Real uses: build systems, package managers, database migration ordering, workflow engines (DAG schedulers), and course prerequisites.
  • Python ships graphlib.TopologicalSorter (3.9+), which raises graphlib.CycleError and supports parallel processing with get_ready() / done().

Common Mistakes:

  • Building edges in the wrong direction (prerequisite → dependent vs the reverse), which yields a reversed order.
  • Forgetting nodes that appear only as dependencies, not as keys.

Q30: What is multi-source BFS, and when do you use it?​

When you need the distance from the nearest of several sources to every cell or node, start BFS with all sources in the queue at distance 0. BFS then expands in waves, and the first time a node is reached is from its closest source. This is one O(V + E) pass instead of one BFS per source.

Examples: rotting oranges (minutes until all are rotten), distance to nearest exit/server/warehouse, walls and gates, and spreading processes such as infection or fire.

from collections import deque


def minutes_until_all_rotten(grid: list[list[int]]) -> int:
"""0 = empty, 1 = fresh, 2 = rotten. Returns -1 if some orange never rots."""
rows, cols = len(grid), len(grid[0])
grid = [row[:] for row in grid] # do not mutate the caller's grid
queue: deque[tuple[int, int, int]] = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0)) # every source starts at minute 0
elif grid[r][c] == 1:
fresh += 1

minutes = 0
while queue:
r, c, t = queue.popleft()
minutes = max(minutes, t)
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2 # mark when enqueued, not when dequeued
fresh -= 1
queue.append((nr, nc, t + 1))

return minutes if fresh == 0 else -1


print(minutes_until_all_rotten([[2, 1, 1], [1, 1, 0], [0, 1, 1]])) # 4
print(minutes_until_all_rotten([[2, 1, 1], [0, 1, 1], [1, 0, 1]])) # -1

Complexity: O(rows · cols) time and space.

Interviewer Notes:

  • Related variant: 0-1 BFS for graphs whose edge weights are only 0 or 1: use a deque, push 0-weight neighbors to the front and 1-weight neighbors to the back. It gives Dijkstra's result in O(V + E).

Common Mistakes:

  • Marking nodes visited when dequeued instead of when enqueued, which lets the same node be enqueued many times.
  • Running a separate BFS from each source (O(k · (V + E))).

Q31: How do you structure a backtracking solution, and how do you prune it?​

Backtracking explores a decision tree depth-first: choose an option, recurse, then undo the choice. It enumerates subsets, permutations, combinations, and constraint-satisfaction solutions (N-Queens, Sudoku). The output itself is often exponential, so the goal is to avoid exploring branches that cannot lead to valid answers (pruning).

Template:

backtrack(state):
if state is a complete solution: record a copy; return
for choice in candidates(state):
if choice violates a constraint: skip (prune)
apply choice
backtrack(state)
undo choice
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
"""Each number may be reused; combinations are unique (order does not matter)."""
candidates = sorted(candidates)
results: list[list[int]] = []
path: list[int] = []

def backtrack(start: int, remaining: int) -> None:
if remaining == 0:
results.append(path.copy()) # copy: path keeps changing
return
for i in range(start, len(candidates)):
value = candidates[i]
if value > remaining:
break # sorted -> every later value is too big as well (pruning)
path.append(value)
backtrack(i, remaining - value) # i, not i + 1: reuse allowed
path.pop()

backtrack(0, target)
return results


def permutations(items: list[str]) -> list[list[str]]:
results: list[list[str]] = []
used = [False] * len(items)
path: list[str] = []

def backtrack() -> None:
if len(path) == len(items):
results.append(path.copy())
return
for i, item in enumerate(items):
if used[i]:
continue
used[i] = True
path.append(item)
backtrack()
path.pop()
used[i] = False

backtrack()
return results


print(combination_sum([2, 3, 6, 7], 7)) # [[2, 2, 3], [7]]
print(len(permutations(["a", "b", "c"]))) # 6

Complexity: exponential in general; for permutations O(n · n!) including copying each result.

Interviewer Notes:

  • Ask how to avoid duplicate combinations when the input has duplicates: sort and skip candidates[i] == candidates[i - 1] when i > start.
  • In production code, prefer itertools.permutations / combinations / product when you just need enumeration; write backtracking when you need pruning.

Common Mistakes:

  • Appending path itself instead of a copy, so every result ends up as the same (empty) list.
  • Starting the loop at 0 in combination problems, which produces permutations of the same combination.

Q32: How do you validate a binary search tree, and why is checking each node against its children not enough?​

A BST requires every node in the left subtree to be smaller than the node, and every node in the right subtree to be larger, not just the direct children. A tree like 5 → left 4 → right 6 passes the parent/child check at every node but is invalid because 6 sits in 5's left subtree.

Correct approaches: pass down an allowed (low, high) range, or do an in-order traversal and check that values are strictly increasing.

from dataclasses import dataclass


@dataclass
class Node:
val: int
left: "Node | None" = None
right: "Node | None" = None


def is_valid_bst(root: Node | None) -> bool:
"""Iterative range check: no recursion limit issues on deep trees."""
stack: list[tuple[Node | None, float, float]] = [(root, float("-inf"), float("inf"))]
while stack:
node, low, high = stack.pop()
if node is None:
continue
if not low < node.val < high:
return False
stack.append((node.left, low, node.val))
stack.append((node.right, node.val, high))
return True


def naive_check(node: Node | None) -> bool:
"""WRONG: only compares with direct children."""
if node is None:
return True
if node.left and node.left.val >= node.val:
return False
if node.right and node.right.val <= node.val:
return False
return naive_check(node.left) and naive_check(node.right)


tricky = Node(5, left=Node(4, right=Node(6)), right=Node(7))
print(naive_check(tricky), is_valid_bst(tricky)) # True False

good = Node(8, Node(3, Node(1), Node(6)), Node(10, right=Node(14)))
print(is_valid_bst(good)) # True

Complexity: O(n) time, O(h) space where h is the height.

Interviewer Notes:

  • Clarify the duplicates policy: strict < rejects duplicates; some definitions allow duplicates on one side.
  • Follow-up: "Find the k-th smallest element" uses the same in-order idea and can stop after k nodes.

Common Mistakes:

  • Using 0 or a large sentinel integer as initial bounds, which breaks for real values outside that range.

Q33: Which bit manipulation tricks come up most often, and where are they useful in backend code?​

Core identities (for non-negative integers):

ExpressionMeaning
x & 1lowest bit (odd/even)
x & (x - 1)clears the lowest set bit; == 0 means power of two (x > 0)
x & -xisolates the lowest set bit (used by Fenwick trees, Q36)
a ^ a == 0, a ^ 0 == aXOR cancels pairs
mask >> i & 1tests bit i
mask & ~(1 << i)clears bit i

Setting bit i is mask | (1 << i).

Backend uses: permission and feature-flag bitsets, compact sets of small integers, bitmask DP over subsets, Bloom filters (Q39), and hashing.

from enum import IntFlag


def single_number(nums: list[int]) -> int:
"""Every value appears twice except one: XOR cancels the pairs."""
result = 0
for x in nums:
result ^= x
return result


def is_power_of_two(x: int) -> bool:
return x > 0 and x & (x - 1) == 0


def count_bits_upto(n: int) -> list[int]:
"""bits[i] = number of 1 bits in i, using bits[i >> 1] + (i & 1)."""
bits = [0] * (n + 1)
for i in range(1, n + 1):
bits[i] = bits[i >> 1] + (i & 1)
return bits


def subsets(items: list[str]) -> list[list[str]]:
"""Each mask from 0 to 2^n - 1 selects one subset."""
n = len(items)
return [[items[i] for i in range(n) if mask >> i & 1] for mask in range(1 << n)]


class Permission(IntFlag):
READ = 1
WRITE = 2
DELETE = 4
ADMIN = READ | WRITE | DELETE


print(single_number([4, 1, 2, 1, 2])) # 4
print(is_power_of_two(1024), is_power_of_two(1000)) # True False
print(count_bits_upto(5)) # [0, 1, 1, 2, 1, 2]
print(len(subsets(["a", "b", "c"]))) # 8
granted = Permission.READ | Permission.WRITE
print(Permission.WRITE in granted, Permission.DELETE in granted) # True False
print((5).bit_count()) # 2 (int.bit_count, Python 3.10+)

Interviewer Notes:

  • Python integers are arbitrary precision, so there is no 32-bit overflow; problems that assume 32-bit two's complement need explicit masking (x & 0xFFFFFFFF).
  • Storing permissions as a bitmask is compact and fast, but makes queries like "who has DELETE?" harder in SQL than a join table; mention the trade-off.

Common Mistakes:

  • Operator precedence differs between languages. In C, Java, and JavaScript, x & 1 == 0 parses as x & (1 == 0); Python binds & tighter than ==, but +/- bind tighter than shifts, so 1 << n - 1 means 1 << (n - 1). Parenthesize bit expressions.

Q34: How do you find the k-th largest element, and when is Quickselect better than a heap?​

Three options:

ApproachTimeSpaceNotes
SortO(n log n)O(n)Simplest; fine for small n
Min-heap of size kO(n log k)O(k)Works on streams; good when k ≪ n
QuickselectO(n) average, O(n²) worstO(1) extra with in-place partitioning; the list-based version below uses O(n)Needs all data in memory; a random pivot makes the worst case unlikely

Quickselect is quicksort that only recurses into the side containing the answer.

import heapq
import random


def kth_largest_heap(nums: list[int], k: int) -> int:
heap: list[int] = []
for x in nums:
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]:
heapq.heapreplace(heap, x) # pop smallest + push, in one O(log k) step
return heap[0]


def kth_largest_quickselect(nums: list[int], k: int) -> int:
"""Three-way partition handles many duplicates well."""
if not 1 <= k <= len(nums):
raise ValueError("k out of range")
items = nums
while True:
pivot = random.choice(items)
larger = [x for x in items if x > pivot]
equal_count = sum(1 for x in items if x == pivot)
if k <= len(larger):
items = larger
elif k <= len(larger) + equal_count:
return pivot
else:
k -= len(larger) + equal_count
items = [x for x in items if x < pivot]


data = [3, 2, 1, 5, 6, 4]
print(kth_largest_heap(data, 2), kth_largest_quickselect(data, 2)) # 5 5
print(heapq.nlargest(2, data)) # [6, 5] - stdlib helper

Interviewer Notes:

  • For latency percentiles over large datasets, exact selection is often replaced by sketches (t-digest, HDR histograms) because they merge across machines and use bounded memory.

Common Mistakes:

  • Using a max-heap of all n elements and popping k times (O(n + k log n), and O(n) memory) when a size-k min-heap was intended.
  • Deterministic first-element pivots on already-sorted input, which triggers the O(n²) case.

Q35: How do you merge k sorted lists or streams efficiently?​

Keep a min-heap containing the current head of each list. Pop the smallest, emit it, and push the next element from the same list. The heap never holds more than k items.

Backend uses: merging sorted log files or time-ordered event streams from many shards, the merge phase of external sorting (see Q50), and merging sorted results from database partitions.

import heapq
from collections.abc import Iterable, Iterator


def merge_k_sorted(streams: list[Iterable[int]]) -> Iterator[int]:
iterators = [iter(s) for s in streams]
heap: list[tuple[int, int]] = [] # (value, stream index) - index breaks ties
for idx, it in enumerate(iterators):
first = next(it, None)
if first is not None:
heap.append((first, idx))
heapq.heapify(heap)

while heap:
value, idx = heap[0]
yield value
nxt = next(iterators[idx], None)
if nxt is None:
heapq.heappop(heap)
else:
heapq.heapreplace(heap, (nxt, idx))


shards = [[1, 4, 9], [2, 3, 10, 11], [], [0, 5]]
print(list(merge_k_sorted(shards))) # [0, 1, 2, 3, 4, 5, 9, 10, 11]

# The standard library already does this lazily:
log_a = [("10:00:01", "api"), ("10:00:05", "api")]
log_b = [("10:00:02", "worker"), ("10:00:03", "worker")]
print([src for _, src in heapq.merge(log_a, log_b)]) # ['api', 'worker', 'worker', 'api']

Complexity: O(N log k) time for N total elements, O(k) space; works on streams because it is lazy.

Interviewer Notes:

  • The tie-breaker (stream index) matters when values are not comparable beyond the key, for example dicts or objects; otherwise equal keys make Python compare the payloads and raise TypeError.
  • Using None as an end-of-stream sentinel only works if None is not a valid value; a dedicated sentinel object is safer for general data.

Common Mistakes:

  • Concatenating everything and sorting (O(N log N) and needs everything in memory).
  • Merging lists pairwise sequentially (O(N · k)); pairwise merging in a balanced tree is also O(N log k).

Range Query Structures​

Q36: What is a Fenwick tree (Binary Indexed Tree), and when do you use it?​

A Fenwick tree supports two operations on an array of numbers in O(log n) each:

  • update(i, delta): add delta to element i.
  • prefix_sum(i): sum of elements 1..i.

Range sums follow from prefix sums: sum(l..r) = prefix_sum(r) - prefix_sum(l - 1). It is much simpler than a segment tree and uses a single array of size n + 1, but it only works directly for operations with an inverse (sum, XOR, counts), not for min/max over arbitrary ranges.

The structure is 1-indexed. Index i stores the sum of a block of length i & -i (the lowest set bit of i) ending at i. Updates climb with i += i & -i; queries descend with i -= i & -i.

class FenwickTree:
def __init__(self, size: int) -> None:
self.n = size
self.tree = [0] * (size + 1) # 1-indexed

@classmethod
def from_list(cls, values: list[int]) -> "FenwickTree":
"""O(n) build: push each node's total to its parent once."""
ft = cls(len(values))
for i, v in enumerate(values, start=1):
ft.tree[i] += v
parent = i + (i & -i)
if parent <= ft.n:
ft.tree[parent] += ft.tree[i]
return ft

def update(self, i: int, delta: int) -> None:
while i <= self.n:
self.tree[i] += delta
i += i & -i

def prefix_sum(self, i: int) -> int:
total = 0
while i > 0:
total += self.tree[i]
i -= i & -i
return total

def range_sum(self, left: int, right: int) -> int:
return self.prefix_sum(right) - self.prefix_sum(left - 1)


ft = FenwickTree.from_list([5, 2, 9, -3, 6])
print(ft.range_sum(2, 4)) # 2 + 9 - 3 = 8
ft.update(3, 1) # element 3 becomes 10
print(ft.range_sum(1, 5)) # 20


# Use case: live leaderboard rank with bounded integer scores (0..1000)
MAX_SCORE = 1000
counts = FenwickTree(MAX_SCORE + 1) # score s is stored at index s + 1


def add_score(score: int) -> None:
counts.update(score + 1, 1)


def players_above(score: int) -> int:
return counts.prefix_sum(MAX_SCORE + 1) - counts.prefix_sum(score + 1)


for s in (700, 950, 300, 950, 820):
add_score(s)
print(players_above(800)) # 3 (820, 950, 950)

Complexity: O(log n) per update and query, O(n) space, O(n) build.

Interviewer Notes:

  • Typical uses: counting inversions, rank queries over bounded values (often after coordinate compression), frequency tables with live updates, and 2D variants for grid sums.
  • Compare: prefix sums are O(1) query but O(n) update; Fenwick is O(log n) for both.

Common Mistakes:

  • Using index 0: 0 & -0 == 0, so update(0, x) loops forever.

Q37: How does a segment tree work, and when do you need it instead of a Fenwick tree?​

A segment tree stores an aggregate (sum, min, max, gcd, or any associative operation with an identity) for segments of the array in a binary tree. Leaves are elements; each internal node combines its two children. Point updates and range queries are O(log n).

Choose a segment tree over a Fenwick tree when:

  • The operation has no inverse (range min/max cannot be derived from two prefix results).
  • You need range updates ("add 5 to every element in [l, r]") with range queries; this uses lazy propagation.
  • You need to search the tree, for example "first index where the prefix sum exceeds X".

The iterative bottom-up version below stores leaves at tree[n:2n] and parents at tree[i] = combine(tree[2i], tree[2i+1]).

from collections.abc import Callable


class SegmentTree[T]:
def __init__(self, values: list[T], combine: Callable[[T, T], T], identity: T) -> None:
self.n = len(values)
self.combine = combine
self.identity = identity
self.tree: list[T] = [identity] * self.n + values
for i in range(self.n - 1, 0, -1):
self.tree[i] = combine(self.tree[2 * i], self.tree[2 * i + 1])

def update(self, index: int, value: T) -> None:
i = index + self.n
self.tree[i] = value
while i > 1:
i //= 2
self.tree[i] = self.combine(self.tree[2 * i], self.tree[2 * i + 1])

def query(self, left: int, right: int) -> T:
"""Aggregate over the half-open range [left, right)."""
left_acc = self.identity
right_acc = self.identity
lo, hi = left + self.n, right + self.n
while lo < hi:
if lo & 1:
left_acc = self.combine(left_acc, self.tree[lo])
lo += 1
if hi & 1:
hi -= 1
right_acc = self.combine(self.tree[hi], right_acc)
lo //= 2
hi //= 2
return self.combine(left_acc, right_acc) # keeps order for non-commutative ops


latencies_ms = [120, 85, 300, 95, 60, 210, 75]
range_min = SegmentTree(latencies_ms, min, float("inf"))
range_max = SegmentTree(latencies_ms, max, float("-inf"))
print(range_min.query(1, 5), range_max.query(1, 5)) # 60 300

range_max.update(2, 90) # the 300 ms sample is corrected to 90
print(range_max.query(0, 7)) # 210

sums = SegmentTree([1, 2, 3, 4, 5], lambda a, b: a + b, 0)
print(sums.query(1, 4)) # 9

Complexity: O(n) build, O(log n) update and query, O(n) space (2n here).

Interviewer Notes:

  • Decision ladder: static data → prefix sums (sum) or sparse table (min/max, O(1) query); point updates + sums → Fenwick; anything else → segment tree; range updates → segment tree with lazy propagation.
  • In real backends, these structures appear inside databases and time-series engines more than in application code; the interview tests whether you can reason about update/query trade-offs.

Common Mistakes:

  • Mixing inclusive and half-open ranges between query callers and the implementation.
  • Using an identity that is not neutral for the operation (for example 0 for min).

Data Structures Behind Backend Systems​

Q38: How does consistent hashing work, and why are virtual nodes needed?​

With node = hash(key) % N, changing N (adding or removing a cache server) remaps almost every key, causing a cache-miss storm. Consistent hashing places nodes and keys on the same hash ring; a key belongs to the first node clockwise from its position. Adding a node only moves the keys between the new node and its predecessor, roughly 1/N of all keys.

With one point per node, ranges are uneven and a removed node dumps its whole range onto a single neighbor. Virtual nodes (many points per physical node) smooth the distribution and spread a failed node's load across many peers. Weighting is done by giving bigger machines more virtual nodes.

import bisect
import hashlib
from collections import Counter


def stable_hash(value: str) -> int:
# Python's built-in hash() for str is randomized per process; use a stable digest.
return int.from_bytes(hashlib.sha256(value.encode()).digest()[:8], "big")


class ConsistentHashRing:
def __init__(self, nodes: list[str], vnodes: int = 100) -> None:
self.vnodes = vnodes
self._ring: list[tuple[int, str]] = []
for node in nodes:
self.add(node)

def add(self, node: str) -> None:
for i in range(self.vnodes):
bisect.insort(self._ring, (stable_hash(f"{node}#{i}"), node))

def remove(self, node: str) -> None:
self._ring = [(h, n) for h, n in self._ring if n != node]

def get(self, key: str) -> str:
if not self._ring:
raise LookupError("empty ring")
idx = bisect.bisect_right(self._ring, (stable_hash(key), chr(0x10FFFF)))
return self._ring[idx % len(self._ring)][1] # wrap around the ring


keys = [f"user:{i}" for i in range(20_000)]
ring = ConsistentHashRing(["cache-a", "cache-b", "cache-c"])
before = {k: ring.get(k) for k in keys}
print(Counter(before.values())) # roughly even thanks to virtual nodes

ring.add("cache-d")
moved = sum(1 for k in keys if ring.get(k) != before[k])
print(f"consistent hashing moved {moved / len(keys):.0%} of keys") # about 25%

mod_before = {k: stable_hash(k) % 3 for k in keys}
mod_moved = sum(1 for k in keys if stable_hash(k) % 4 != mod_before[k])
print(f"hash mod N moved {mod_moved / len(keys):.0%} of keys") # about 75%

Complexity: O(log(N · V)) per lookup with binary search over N nodes × V virtual nodes; O(N · V) memory.

Interviewer Notes:

  • Real systems using the idea: Amazon's Dynamo paper, Cassandra token rings, many memcached client libraries (ketama-style hashing), and load balancers that need session affinity.
  • Alternatives worth naming: rendezvous (highest random weight) hashing, which needs no ring (see Q46), and jump consistent hash for numbered buckets.

Common Mistakes:

  • Using Python's hash() for placement; it differs between processes for strings unless PYTHONHASHSEED is fixed.
  • Forgetting the wrap-around from the last ring position to the first.

Q39: What is a Bloom filter, and how do you size it?​

A Bloom filter is a bit array of size m with k hash functions. To add an item, set the k bits it hashes to. To query, check those k bits: if any is 0 the item was definitely never added; if all are 1 it was probably added. There are no false negatives, but there are false positives, and standard Bloom filters cannot delete items (counting Bloom filters or cuckoo filters can).

Sizing for n expected items and target false-positive rate p:

  • bits: m = -n · ln(p) / (ln 2)²
  • hash functions: k = (m / n) · ln 2
  • false-positive rate after n inserts: approximately (1 - e^(-k·n/m))^k

For p = 1% this works out to about 9.6 bits per item and k ≈ 7, independent of item size.

import hashlib
import math


class BloomFilter:
def __init__(self, expected_items: int, fp_rate: float) -> None:
self.m = math.ceil(-expected_items * math.log(fp_rate) / math.log(2) ** 2)
self.k = max(1, round(self.m / expected_items * math.log(2)))
self.bits = bytearray((self.m + 7) // 8)

def _positions(self, item: str) -> list[int]:
# Double hashing (Kirsch-Mitzenmacher): g_i(x) = h1(x) + i * h2(x)
digest = hashlib.sha256(item.encode()).digest()
h1 = int.from_bytes(digest[:8], "big")
h2 = int.from_bytes(digest[8:16], "big") | 1
return [(h1 + i * h2) % self.m for i in range(self.k)]

def add(self, item: str) -> None:
for pos in self._positions(item):
self.bits[pos // 8] |= 1 << (pos % 8)

def might_contain(self, item: str) -> bool:
return all(self.bits[pos // 8] >> (pos % 8) & 1 for pos in self._positions(item))


bf = BloomFilter(expected_items=10_000, fp_rate=0.01)
print(bf.m, bf.k, f"{len(bf.bits) / 1024:.1f} KiB") # 95851 7 11.7 KiB

for i in range(10_000):
bf.add(f"compromised-password-{i}")

print(all(bf.might_contain(f"compromised-password-{i}") for i in range(10_000))) # True
false_positives = sum(bf.might_contain(f"other-{i}") for i in range(100_000))
print(f"observed FP rate: {false_positives / 100_000:.2%}") # close to 1%

Interviewer Notes:

  • Backend uses: skipping disk reads for keys that are not in an SSTable (LSM-tree databases such as Cassandra and RocksDB), "have we seen this URL/event ID" checks before an expensive lookup, and checking passwords against breached-password lists.
  • The filter is a pre-check: on "probably yes" you still verify with the source of truth.

Common Mistakes:

  • Inserting far more than the planned n; the false-positive rate climbs quickly once the filter fills up.
  • Using a Bloom filter where a false positive is unacceptable without a follow-up exact check.

Q40: Compare rate-limiting algorithms: fixed window, sliding log, sliding window counter, token bucket, and leaky bucket.​

AlgorithmMemory per clientBurst behaviorNotes
Fixed window counterO(1)Up to 2× limit across a window boundarySimplest; one INCR + expiry in Redis
Sliding window logO(limit)ExactStores every timestamp; expensive at high limits
Sliding window counterO(1)Approximate, smooths the boundary problemWeights the previous window's count
Token bucketO(1)Allows bursts up to bucket capacity, then a steady rateMost common for APIs
Leaky bucket (queue)O(queue)Smooths output to a constant rateGood for protecting downstream systems
import time
from collections.abc import Callable
from dataclasses import dataclass, field


@dataclass
class TokenBucket:
capacity: float # maximum burst
refill_per_second: float # sustained rate
clock: Callable[[], float] = time.monotonic
tokens: float = field(init=False)
updated_at: float = field(init=False)

def __post_init__(self) -> None:
self.tokens = self.capacity
self.updated_at = self.clock()

def allow(self, cost: float = 1.0) -> bool:
now = self.clock()
elapsed = now - self.updated_at
self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_per_second)
self.updated_at = now
if self.tokens >= cost:
self.tokens -= cost
return True
return False


@dataclass
class SlidingWindowCounter:
limit: int
window_seconds: float
clock: Callable[[], float] = time.monotonic
current_window: int = 0
current_count: int = 0
previous_count: int = 0

def allow(self) -> bool:
now = self.clock()
window = int(now // self.window_seconds)
if window != self.current_window:
# if more than one window passed, the previous window is empty
self.previous_count = self.current_count if window == self.current_window + 1 else 0
self.current_count = 0
self.current_window = window
elapsed_fraction = (now % self.window_seconds) / self.window_seconds
estimated = self.previous_count * (1 - elapsed_fraction) + self.current_count
if estimated < self.limit:
self.current_count += 1
return True
return False


class FakeClock:
def __init__(self) -> None:
self.now = 1000.0

def __call__(self) -> float:
return self.now


clock = FakeClock()
bucket = TokenBucket(capacity=5, refill_per_second=1, clock=clock)
print([bucket.allow() for _ in range(7)]) # 5 x True (burst), then False, False
clock.now += 2
print(bucket.allow(), bucket.allow(), bucket.allow()) # True True False

clock2 = FakeClock()
limiter = SlidingWindowCounter(limit=10, window_seconds=60, clock=clock2)
clock2.now = 60 * 100 + 59 # last second of a window
print(sum(limiter.allow() for _ in range(10))) # 10
clock2.now = 60 * 101 + 1 # 2 seconds later, new window
print(sum(limiter.allow() for _ in range(10))) # 1 - previous window still weighs 59/60; a fixed window would allow 10

Interviewer Notes:

  • In a distributed system the state must be shared (usually Redis) and updated atomically: a Lua script or a single atomic command, not separate GET and SET calls, or concurrent requests race past the limit.
  • Use a monotonic clock in-process; across machines, prefer the Redis server's time over each client's clock.
  • Return 429 Too Many Requests with a Retry-After header so well-behaved clients back off.

Common Mistakes:

  • Implementing the token bucket with a background thread that adds tokens on a timer instead of computing refill lazily on each request.
  • Rate limiting per server instance and multiplying the effective limit by the number of replicas.

Senior / Principal — Real World Algorithm Scenarios​

Q41: An export endpoint gets slower every month: accidentally quadratic code​

Level: Senior

Scenario: A CSV export of a customer's contacts took 2 seconds at launch. Months later, large customers hit 60-second gateway timeouts. Nobody changed the code; the data simply grew. Profiling shows almost all time inside a deduplication helper.

Impact: Exports fail for the most valuable (largest) customers, and the retries keep a worker pegged at 100% CPU.

Root Cause: The helper deduplicated with if email not in seen_list: seen_list.append(email). Each in on a list is O(n), so the loop is O(n²): doubling the data quadruples the time. Similar traps: building a string with += in a loop, list.pop(0) in a loop, nested loops to "join" two lists, and repeated sorted() inside a loop.

Fix:

  1. Replace membership on lists with a set (or dict.fromkeys to keep first-seen order).
  2. Build strings with "".join(...) or write rows directly to the output stream.
  3. Add a performance test with growing input sizes that asserts roughly linear scaling, so regressions are caught before customers find them.
import time
from collections.abc import Callable


def dedupe_quadratic(emails: list[str]) -> list[str]:
seen: list[str] = []
for e in emails:
if e not in seen: # O(n) scan each time
seen.append(e)
return seen


def dedupe_linear(emails: list[str]) -> list[str]:
return list(dict.fromkeys(emails)) # O(n), keeps first-seen order


def timed(fn: Callable[[list[str]], list[str]], data: list[str]) -> float:
start = time.perf_counter()
fn(data)
return time.perf_counter() - start


for n in (2_000, 4_000, 8_000):
data = [f"user{i % (n // 2)}@example.com" for i in range(n)]
assert dedupe_quadratic(data) == dedupe_linear(data)
print(f"n={n:>5} quadratic={timed(dedupe_quadratic, data):.4f}s "
f"linear={timed(dedupe_linear, data):.5f}s")
# The quadratic column roughly quadruples per doubling; the linear one roughly doubles.

Workflow Diagram:

rows ──▶ for each row ──▶ "email in seen_list?" ──▶ scans up to n items => O(n²)
rows ──▶ for each row ──▶ "email in seen_set?" ──▶ one hash lookup => O(n)

time
▲ quadratic
│ /
│ /
│ / linear
│ / ───────────────────
└──────────────────────────▶ rows

Interviewer Notes:

  • Senior candidates reach for a profiler (cProfile, py-spy) before guessing, and they test with production-sized data.
  • The scaling test is the key long-term fix: measure time at n and 2n and alert if the ratio approaches 4.

Red Flags:

  • "Increase the gateway timeout" or "add more workers".
  • Caching the export result without fixing the algorithm.

Q42: Deep pages of an activity feed time out: OFFSET pagination is O(offset)​

Level: Senior

Scenario: A public API paginates with ?page=N using ORDER BY created_at DESC LIMIT 50 OFFSET (N-1)*50. Page 1 is fast, but page 2,000 takes seconds, and a partner's sync job that walks every page overloads the primary database. Users also report seeing the same item twice or missing items while scrolling.

Impact: Database CPU saturation from a single integration, slow responses for everyone, and inconsistent data for clients.

Root Cause: The database cannot jump to row 100,000; it must produce and discard all skipped rows, so each request costs O(offset + limit) and walking all pages is O(n²) in total. Rows inserted or deleted between requests shift the offsets, causing duplicates and gaps.

Fix: Keyset (cursor) pagination: remember the sort key of the last row returned and ask for rows "after" it, using an index on the sort key plus a unique tiebreaker. Each page is then an O(log n) index seek plus limit rows, and concurrent inserts do not shift results. Encode the cursor opaquely so clients cannot depend on its format.

import base64
import json
import sqlite3

conn = sqlite3.connect(":memory:")
conn.execute("CREATE TABLE events (id INTEGER PRIMARY KEY, created_at INTEGER, payload TEXT)")
conn.execute("CREATE INDEX idx_events_created ON events (created_at DESC, id DESC)")
conn.executemany(
"INSERT INTO events (created_at, payload) VALUES (?, ?)",
[(1_700_000_000 + i // 3, f"event-{i}") for i in range(10_000)], # duplicate timestamps
)


def encode_cursor(created_at: int, row_id: int) -> str:
return base64.urlsafe_b64encode(json.dumps([created_at, row_id]).encode()).decode()


def decode_cursor(cursor: str) -> tuple[int, int]:
created_at, row_id = json.loads(base64.urlsafe_b64decode(cursor))
return int(created_at), int(row_id)


def page_keyset(limit: int, cursor: str | None = None) -> tuple[list[int], str | None]:
if cursor is None:
rows = conn.execute(
"SELECT id, created_at FROM events ORDER BY created_at DESC, id DESC LIMIT ?",
(limit,),
).fetchall()
else:
created_at, row_id = decode_cursor(cursor)
rows = conn.execute(
"SELECT id, created_at FROM events "
"WHERE (created_at, id) < (?, ?) " # row-value comparison
"ORDER BY created_at DESC, id DESC LIMIT ?",
(created_at, row_id, limit),
).fetchall()
next_cursor = encode_cursor(rows[-1][1], rows[-1][0]) if len(rows) == limit else None
return [r[0] for r in rows], next_cursor


def page_offset(limit: int, page: int) -> list[int]:
return [r[0] for r in conn.execute(
"SELECT id FROM events ORDER BY created_at DESC, id DESC LIMIT ? OFFSET ?",
(limit, (page - 1) * limit),
)]


# Walk all pages with cursors and confirm we see each row exactly once
seen: list[int] = []
cursor: str | None = None
while True:
ids, cursor = page_keyset(500, cursor)
seen.extend(ids)
if cursor is None:
break
print(len(seen), len(set(seen))) # 10000 10000
print(page_offset(500, 3) == seen[1000:1500]) # True - same rows, different cost

Workflow Diagram:

OFFSET pagination Keyset pagination
page 2000: scan 99,950 rows ─▶ discard page N: index seek to (created_at, id) < cursor
return 50 rows read 50 rows ─▶ return + next cursor
cost grows with page number cost constant per page

client ──GET /events?cursor=abc──▶ API ──▶ WHERE (created_at, id) < (…) LIMIT 50
◀── items + next_cursor ────┘

Interviewer Notes:

  • The unique tiebreaker (id) is essential when the sort key has duplicates; without it, rows sharing a timestamp at a page boundary get skipped or repeated.
  • Trade-off: keyset pagination cannot jump to an arbitrary page number. Product discussions usually accept "next/previous" plus filters, or offer a capped page count.
  • Row-value comparisons (a, b) < (x, y) are supported by PostgreSQL, MySQL, and SQLite; otherwise expand to a < x OR (a = x AND b < y).

Red Flags:

  • Using created_at alone as the cursor.
  • Running COUNT(*) on every page request to show "page X of Y" on a huge table.

Q43: One request pins a CPU core for minutes: catastrophic regex backtracking (ReDoS)​

Level: Senior

Scenario: A signup service validates usernames and email-like identifiers with a regex. A single request with a long crafted string pins a worker at 100% CPU for minutes. A handful of such requests take the whole service down.

Impact: Denial of service from a few small requests; health checks fail and the orchestrator restarts healthy pods in a loop.

Root Cause: Python's re module is a backtracking engine. Patterns with nested or overlapping quantifiers, like ^(a+)+$ or ^([a-z0-9]+\.?)+@, can match the same text in exponentially many ways. When the overall match finally fails (for example because of a trailing !), the engine tries every way before giving up, which takes O(2^n) time.

Fix:

  1. Rewrite the pattern so that each character can be matched in only one way (remove nested quantifiers).
  2. Since Python 3.11, use atomic groups (?>...) or possessive quantifiers (++, *+) to forbid backtracking into a sub-match.
  3. Limit input length before running the regex.
  4. For user-supplied or complex patterns, use a linear-time engine (RE2, available through third-party bindings) or run matching with a timeout in a separate process.
import re
import time

evil = re.compile(r"^(a+)+$") # nested quantifier
safe = re.compile(r"^a+$") # same language, one way to match
atomic = re.compile(r"^(?>a+)+$") # atomic group (Python 3.11+)

for n in (16, 18, 20, 22):
payload = "a" * n + "!"
start = time.perf_counter()
evil.match(payload)
print(f"n={n}: {time.perf_counter() - start:.3f}s") # roughly doubles per extra char

payload = "a" * 50_000 + "!"
for name, pattern in (("safe", safe), ("atomic", atomic)):
start = time.perf_counter()
result = pattern.match(payload)
print(name, result, f"{time.perf_counter() - start:.4f}s") # None, fast


MAX_USERNAME = 32
USERNAME = re.compile(r"[a-z0-9](?:[a-z0-9_-]{0,30}[a-z0-9])?")


def valid_username(value: str) -> bool:
return len(value) <= MAX_USERNAME and USERNAME.fullmatch(value) is not None


print(valid_username("deploy-bot_01"), valid_username("-bad")) # True False

Workflow Diagram:

input "aaaa…a!" ──▶ ^(a+)+$
│ split "aaaa" as a|aaa, aa|aa, a|a|aa, ... (2^(n-1) ways)
▼ every split fails at "!" ──▶ exponential time

FIX: length check ──▶ pattern with one way to match ──▶ linear time
└─▶ or RE2 / atomic groups / timeout in a worker process

Interviewer Notes:

  • Strong candidates know the problem is the engine, not the regex language: the same expression is linear in an automaton-based engine like RE2.
  • Mention testing: fuzz validators with long near-miss inputs (valid prefix + invalid last character) and assert a time budget.

Red Flags:

  • "Regexes are always O(n)."
  • Accepting arbitrary user-provided regex patterns and running them with re on the request thread.

Q44: Find the top 100 most-requested URLs from billions of log lines with bounded memory​

Level: Principal

Scenario: The CDN emits billions of request log lines per day across thousands of edge nodes. Product wants a near-real-time "top 100 URLs" dashboard. A first attempt keeps an exact dict[url, count] per node and merges them centrally; it runs out of memory because the long tail contains hundreds of millions of distinct URLs (query strings, cache busters, bots).

Impact: The analytics job is repeatedly OOM-killed; the dashboard is hours stale; scaling the exact approach would need a large cluster just for counting.

Root Cause: Exact counting needs memory proportional to the number of distinct keys, which is unbounded in a long-tailed stream. But the question only asks about the heavy hitters, which can be answered approximately in fixed memory.

Fix:

  1. Use a Count-Min Sketch (CMS): a depth × width table of counters with one hash function per row. Each event increments one counter per row; the estimate is the minimum across rows. Estimates never undercount, and with width = ⌈e/ε⌉ and depth = ⌈ln(1/δ)⌉, the overestimate is at most ε · N with probability at least 1 − δ (N = total events).
  2. Keep a small candidate set of the current top-k by estimated count.
  3. Sketches with the same dimensions and hash functions merge by adding tables cell by cell, so each edge node can build one locally and the central job sums them.
  4. Optionally verify the final top-k with an exact count restricted to just those candidates.
import hashlib
import math
import random
from collections import Counter


class CountMinSketch:
def __init__(self, epsilon: float, delta: float) -> None:
self.width = math.ceil(math.e / epsilon)
self.depth = math.ceil(math.log(1 / delta))
self.table = [[0] * self.width for _ in range(self.depth)]
self.total = 0

def _columns(self, item: str) -> list[int]:
digest = hashlib.sha256(item.encode()).digest()
h1 = int.from_bytes(digest[:8], "big")
h2 = int.from_bytes(digest[8:16], "big") | 1
return [(h1 + row * h2) % self.width for row in range(self.depth)]

def add(self, item: str, count: int = 1) -> int:
self.total += count
estimate = math.inf
for row, col in enumerate(self._columns(item)):
self.table[row][col] += count
estimate = min(estimate, self.table[row][col])
return int(estimate)

def estimate(self, item: str) -> int:
return min(self.table[row][col] for row, col in enumerate(self._columns(item)))

def merge(self, other: "CountMinSketch") -> None:
assert (self.width, self.depth) == (other.width, other.depth)
for row in range(self.depth):
for col in range(self.width):
self.table[row][col] += other.table[row][col]
self.total += other.total


class HeavyHitters:
def __init__(self, k: int, epsilon: float = 0.001, delta: float = 0.01) -> None:
self.k = k
self.cms = CountMinSketch(epsilon, delta)
self.top: dict[str, int] = {}

def add(self, item: str) -> None:
estimate = self.cms.add(item)
if item in self.top or len(self.top) < self.k:
self.top[item] = estimate
return
weakest = min(self.top, key=self.top.__getitem__) # O(k); fine for small k
if estimate > self.top[weakest]:
del self.top[weakest]
self.top[item] = estimate

def result(self) -> list[tuple[str, int]]:
return sorted(self.top.items(), key=lambda kv: -kv[1])


random.seed(7)
popular = [f"/product/{i}" for i in range(20)]
events = [random.choice(popular[:5]) if random.random() < 0.3 else
random.choice(popular) if random.random() < 0.5 else
f"/search?q={random.randrange(1_000_000)}" for _ in range(60_000)]

hh = HeavyHitters(k=5)
for url in events:
hh.add(url)

exact_top5 = {url for url, _ in Counter(events).most_common(5)}
print(f"sketch: {hh.cms.depth}x{hh.cms.width} counters for {len(set(events))} distinct URLs")
print({url for url, _ in hh.result()} == exact_top5) # True on this skewed data

Workflow Diagram:

edge node 1 ──▶ CMS₁ ┐
edge node 2 ──▶ CMS₂ ├──▶ merge (cell-wise sum) ──▶ global CMS ──▶ top-k candidates
edge node N ──▶ CMSₙ ┘ fixed size per node │
▼
optional exact recount of the k candidates

Interviewer Notes:

  • Principal candidates state the accuracy contract precisely (one-sided error, bounded by ε·N with probability 1−δ) and pick ε relative to the smallest count they care about: a URL with 0.01% of traffic needs ε well below 0.0001.
  • Alternatives: the Misra-Gries / Space-Saving algorithms keep k counters directly and are often simpler for pure top-k; stream processors and analytics databases ship built-in approximate top-k functions.
  • Windowing: for "top URLs in the last 5 minutes", keep one sketch per minute and merge the last five.

Red Flags:

  • Sampling 1% of logs and claiming the top-k is exact.
  • Ignoring that bot traffic and cache-busting query strings should be normalized before counting.

Q45: Counting daily unique visitors across 200 servers without storing every visitor ID​

Level: Principal

Scenario: The analytics team computes daily and monthly unique visitors by collecting every visitor ID into a set per server, shipping the sets to a central job, and unioning them. With hundreds of millions of IDs, the job needs tens of gigabytes of memory, and monthly uniques (which cannot be summed from daily uniques) take hours.

Impact: Expensive infrastructure, slow reports, and product teams cannot slice uniques by page or campaign because each slice would need its own set.

Root Cause: Exact distinct counting requires memory proportional to the number of distinct items, and unique counts are not additive (|A ∪ B| ≠ |A| + |B|), so you must keep mergeable state rather than numbers.

Fix: Use HyperLogLog (HLL). Hash each ID; use the first p bits to choose one of m = 2^p registers and store the maximum "position of the first 1-bit" seen in the remaining bits. Rare long runs of leading zeros indicate many distinct items. The estimate is a bias-corrected harmonic mean over registers. With m registers the standard error is about 1.04 / √m; Redis's HLL uses 16,384 registers (about 0.81% standard error) in roughly 12 KB per key. HLLs merge by taking the register-wise maximum, so daily HLLs combine into a monthly one exactly as if all IDs had been added to one HLL.

import hashlib
import math


class HyperLogLog:
def __init__(self, precision: int = 14) -> None:
if not 4 <= precision <= 16:
raise ValueError("precision must be between 4 and 16")
self.p = precision
self.m = 1 << precision
self.registers = bytearray(self.m)
self.alpha = 0.7213 / (1 + 1.079 / self.m) # valid for m >= 128

def add(self, item: str) -> None:
x = int.from_bytes(hashlib.blake2b(item.encode(), digest_size=8).digest(), "big")
index = x >> (64 - self.p) # first p bits pick the register
rest = x & ((1 << (64 - self.p)) - 1) # remaining 64 - p bits
rank = (64 - self.p) - rest.bit_length() + 1 # position of the first 1-bit
if rank > self.registers[index]:
self.registers[index] = rank

def count(self) -> int:
raw = self.alpha * self.m * self.m / sum(2.0 ** -r for r in self.registers)
zeros = self.registers.count(0)
if raw <= 2.5 * self.m and zeros: # small-range correction
return round(self.m * math.log(self.m / zeros))
return round(raw)

def merge(self, other: "HyperLogLog") -> "HyperLogLog":
assert self.p == other.p
merged = HyperLogLog(self.p)
merged.registers = bytearray(max(a, b) for a, b in zip(self.registers, other.registers))
return merged


monday, tuesday = HyperLogLog(), HyperLogLog()
for i in range(120_000):
monday.add(f"visitor-{i}")
for i in range(80_000, 200_000): # 40,000 visitors came back on Tuesday
tuesday.add(f"visitor-{i}")

both_days = monday.merge(tuesday)
for label, hll, truth in (("monday", monday, 120_000), ("tuesday", tuesday, 120_000),
("union", both_days, 200_000)):
est = hll.count()
print(f"{label:8} estimate={est:>7} true={truth:>7} error={abs(est - truth) / truth:.2%}")
print("memory per HLL:", len(monday.registers), "bytes") # 16384 (one byte per register here)

Workflow Diagram:

visitor id ──hash──▶ 64 bits: [ p bits → register index | rest → count leading zeros ]
│
registers[index] = max(registers[index], zeros + 1)

server HLLs (daily) ──register-wise max──▶ daily HLL ──max over 30 days──▶ monthly HLL
cardinality estimate = bias-corrected harmonic mean of 2^register

Interviewer Notes:

  • Principal-level points: HLL is mergeable (union) but intersections are only approximate via inclusion–exclusion and get noisy when the intersection is small; precision is a memory/accuracy dial; and estimates should be reported with their error bars.
  • Many databases and warehouses offer HLL-based APPROX_COUNT_DISTINCT-style functions and storable sketches; Redis provides PFADD, PFCOUNT, and PFMERGE.

Red Flags:

  • Summing daily unique counts to get monthly uniques.
  • Using HLL where exact counts are legally or financially required (billing per unique user).

Q46: Adding one cache node during a traffic spike took the database down: modulo sharding​

Level: Principal

Scenario: A product catalog is cached across 8 Redis nodes, with the node chosen by crc32(key) % 8. During a sale, the team adds a ninth node to relieve memory pressure. Within a minute the cache hit rate collapses from about 95% to under 20%, the database receives several times its normal read load, and the site goes down.

Impact: A full outage during the highest-revenue hour of the quarter, caused by a capacity change meant to help.

Root Cause: With hash % N, a key stays on the same node only if hash % 8 == hash % 9, which holds for roughly 1 in 9 keys. Changing N remapped about 89% of keys at once; every remapped key became a cache miss, and the misses all went to the database simultaneously (a thundering herd).

Fix:

  1. Use a placement scheme that moves only about 1/N of keys when membership changes: a consistent hash ring with virtual nodes (Q38) or rendezvous (highest random weight) hashing, shown below, which needs no ring: each key scores every node and picks the highest score.
  2. Make capacity changes gradual: add nodes off-peak, warm them, or migrate traffic in steps.
  3. Protect the database independently of the cache: request coalescing ("single flight") so only one request per key rebuilds a missing entry, and load shedding when the database is saturated.
import hashlib


def score(node: str, key: str) -> int:
return int.from_bytes(hashlib.sha256(f"{node}|{key}".encode()).digest()[:8], "big")


def rendezvous_node(key: str, nodes: list[str]) -> str:
return max(nodes, key=lambda node: score(node, key))


def modulo_node(key: str, nodes: list[str]) -> str:
h = int.from_bytes(hashlib.sha256(key.encode()).digest()[:8], "big")
return nodes[h % len(nodes)]


keys = [f"product:{i}" for i in range(20_000)]
eight = [f"redis-{i}" for i in range(8)]
nine = eight + ["redis-8"]

for name, place in (("modulo", modulo_node), ("rendezvous", rendezvous_node)):
moved = sum(place(k, eight) != place(k, nine) for k in keys)
print(f"{name:10} remapped {moved / len(keys):.0%} of keys")
# modulo remaps ~89%; rendezvous remaps ~11% (only keys the new node now wins)

# Removing a node only moves that node's keys, spread over all survivors
survivors = [n for n in eight if n != "redis-3"]
moved_keys = [k for k in keys if rendezvous_node(k, eight) == "redis-3"]
print(all(rendezvous_node(k, survivors) != "redis-3" for k in moved_keys),
sum(rendezvous_node(k, eight) != rendezvous_node(k, survivors) for k in keys) == len(moved_keys))

Workflow Diagram:

hash % N (8 → 9 nodes) rendezvous / consistent hashing
┌──────────────────────────────┐ ┌──────────────────────────────┐
│ ~89% keys change node │ │ ~1/9 keys move to new node │
│ ──▶ mass cache miss │ │ others stay where they are │
│ ──▶ DB read storm ──▶ outage │ │ ──▶ hit rate dips slightly │
└──────────────────────────────┘ └──────────────────────────────┘
plus: single-flight rebuilds + gradual rollout + DB load shedding

Interviewer Notes:

  • Rendezvous hashing is O(N) per lookup (score every node), which is fine for tens of nodes; rings with binary search are O(log(N·V)) for large clusters. Weighted variants of both exist for heterogeneous nodes.
  • Managed systems often solve this for you (Redis Cluster uses 16,384 hash slots that are moved between nodes explicitly), but you must still plan slot migrations and cache warm-up.

Red Flags:

  • Treating the cache as if it were the database's capacity plan ("the DB never sees that load").
  • Scaling a cache tier during peak traffic without a rollback plan.

Q47: Platform deploys fail because services start before their dependencies: ordering 60 services safely​

Level: Senior

Scenario: A release pipeline deploys about 60 services and database migrations in an order kept by hand in a YAML list. Someone adds a new dependency (the orders service now needs a column created by the billing migration) without updating the list. The release half-applies: orders starts, crashes on the missing column, and the rollback is messy. Deploys are also slow because everything runs sequentially.

Impact: Failed releases, partial outages during deploys, and long deploy windows.

Root Cause: The order is a derived property of the dependency graph, but it was maintained manually. Nothing checked that the order respected the dependencies, nothing detected cycles, and the sequential list ignored that independent services could deploy in parallel.

Fix:

  1. Each service declares its own dependencies next to its code.
  2. The pipeline computes a topological order and groups it into waves: every node in a wave has all its dependencies in earlier waves, so a wave can deploy in parallel.
  3. CI fails on cycles and prints the cycle path, so the owning teams can break it (for example, by making one dependency asynchronous or backward-compatible).
from graphlib import CycleError, TopologicalSorter


def deployment_waves(depends_on: dict[str, set[str]]) -> list[list[str]]:
sorter = TopologicalSorter(depends_on)
sorter.prepare() # raises CycleError if the graph has a cycle
waves: list[list[str]] = []
while sorter.is_active():
ready = sorted(sorter.get_ready()) # everything whose dependencies are done
waves.append(ready)
sorter.done(*ready) # in a real pipeline: after health checks pass
return waves


services = {
"billing-migration": set(),
"users-migration": set(),
"billing": {"billing-migration"},
"users": {"users-migration"},
"orders": {"billing-migration", "users"},
"gateway": {"orders", "billing", "users"},
}
for i, wave in enumerate(deployment_waves(services), start=1):
print(f"wave {i}: {wave}")

try:
deployment_waves({"orders": {"billing"}, "billing": {"payments"}, "payments": {"orders"}})
except CycleError as exc:
# each node must come before the next; first and last node are the same
print("cycle:", " -> ".join(exc.args[1]))

Workflow Diagram:

wave 1: billing-migration, users-migration (parallel)
│ │
wave 2: billing users (parallel)
│ ╲ │
wave 3: │ ╲──────▶ orders
│ │
wave 4: gateway ◀──────────┘
cycle in CI ──▶ fail build, print "orders -> payments -> billing -> orders"

Interviewer Notes:

  • Ask about failure handling: if a wave fails, stop scheduling dependents (they never become ready) while independent branches may continue.
  • The deeper fix for deploy coupling is backward-compatible changes (expand/contract migrations) so that order matters less; the graph is a safety net.

Red Flags:

  • Adding sleep 60 between deploys "to let things settle".
  • Resolving cycles by deploying "a few times until it works".

Q48: A retry scheduler's memory grows forever: cancelled timers never leave the heap​

Level: Senior

Scenario: A webhook delivery service schedules retries in an in-memory min-heap of (due_time, seq, job). When a delivery succeeds through another path, the pending retry is cancelled by setting job.cancelled = True. Retries are scheduled up to 24 hours out. Memory grows steadily and the process is OOM-killed every few days, even though the number of active retries is small.

Impact: Periodic crashes lose all in-memory retries, so some webhooks are never delivered.

Root Cause: Lazy deletion without cleanup. Removing an arbitrary element from a binary heap is awkward, so cancelled entries are left in place and skipped when popped. But entries far in the future are not popped for hours, and with high cancellation rates the heap is mostly garbage. The heap size tracks scheduled entries, not live entries.

Fix:

  1. Keep lazy deletion (it is O(1) per cancel) but track the number of cancelled entries.
  2. When cancelled entries exceed a fraction of the heap (for example half), compact: filter them out and heapify in O(n). Amortized over the cancellations that triggered it, the cost is O(1) per cancel.
  3. Export heap size and live count as metrics; alert when they diverge.
  4. For durability, keep retries in a persistent store (database table or broker with delayed delivery) rather than only in process memory.
import heapq
import itertools
from dataclasses import dataclass, field


@dataclass(order=True)
class Timer:
due: float
seq: int
job_id: str = field(compare=False)
cancelled: bool = field(default=False, compare=False)


class TimerQueue:
def __init__(self, compact_ratio: float = 0.5, min_size: int = 64) -> None:
self._heap: list[Timer] = []
self._by_job: dict[str, Timer] = {}
self._cancelled = 0
self._seq = itertools.count()
self.compact_ratio = compact_ratio
self.min_size = min_size

def schedule(self, job_id: str, due: float) -> None:
self.cancel(job_id) # one pending timer per job
timer = Timer(due, next(self._seq), job_id)
self._by_job[job_id] = timer
heapq.heappush(self._heap, timer)

def cancel(self, job_id: str) -> None:
timer = self._by_job.pop(job_id, None)
if timer is not None and not timer.cancelled:
timer.cancelled = True
self._cancelled += 1
self._maybe_compact()

def pop_due(self, now: float) -> list[str]:
due: list[str] = []
while self._heap and self._heap[0].due <= now:
timer = heapq.heappop(self._heap)
if timer.cancelled:
self._cancelled -= 1
continue
del self._by_job[timer.job_id]
due.append(timer.job_id)
return due

def _maybe_compact(self) -> None:
size = len(self._heap)
if size >= self.min_size and self._cancelled > size * self.compact_ratio:
self._heap = [t for t in self._heap if not t.cancelled]
heapq.heapify(self._heap)
self._cancelled = 0

def stats(self) -> tuple[int, int]:
return len(self._heap), len(self._by_job) # (heap size, live timers)


q = TimerQueue()
for i in range(100_000):
q.schedule(f"webhook-{i}", due=86_400 + i) # retries a day out
if i % 10 != 0:
q.cancel(f"webhook-{i}") # 90% succeed before their retry
heap_size, live = q.stats()
print(heap_size, live) # heap stays within ~2x the live count
print(q.pop_due(now=86_400 + 25)) # ['webhook-0', 'webhook-10', 'webhook-20']

Workflow Diagram:

schedule ──▶ push (due, seq, job) ──▶ heap
cancel ──▶ mark cancelled, cancelled += 1
│
▼ cancelled > 50% of heap?
yes ──▶ rebuild heap without cancelled entries (O(n), amortized O(1))
pop_due ──▶ pop while heap[0].due <= now, skip cancelled
metrics: heap_size vs live_count ──▶ alert if they diverge

Interviewer Notes:

  • The seq tiebreaker keeps ordering stable and prevents comparisons from falling through to non-comparable payloads.
  • Python's asyncio event loop applies a similar idea to its scheduled timer handles: cancelled handles are removed in bulk once they make up a large enough share of the scheduled set.
  • Alternatives: a hierarchical timing wheel (O(1) insert/cancel, used in network stacks and some schedulers) when there are millions of timers with coarse resolution.

Red Flags:

  • Removing an item with heap.remove(x) followed by heapify on every cancel (O(n) each).
  • Not having any metric that distinguishes scheduled entries from live ones.

Q49: A comment thread page returns 500: recursion depth exceeded on deep reply chains​

Level: Senior

Scenario: A discussion platform renders nested comment threads with a recursive function. A spam bot posts thousands of replies, each replying to the previous one. Loading that thread returns 500 with RecursionError: maximum recursion depth exceeded, and a background job that exports threads crashes on the same data.

Impact: The thread is unreadable, moderation tools that use the same code path cannot load it to delete the spam, and the export job keeps failing.

Root Cause: Recursive DFS uses one Python stack frame per level, and CPython caps Python recursion depth (the default value of sys.getrecursionlimit() is 1000). The code assumed threads are shallow, but depth is user-controlled input.

Fix:

  1. Replace recursion with an explicit stack (iterative DFS) so depth is limited only by heap memory.
  2. Enforce a product-level maximum nesting depth when replies are created (deeper replies attach at the maximum level), which also fixes the UI.
  3. Do not "fix" it by raising sys.setrecursionlimit() to a huge value: the next, deeper input fails again, memory use grows with depth, and depending on the Python version and whether the recursion passes through C code, very deep recursion can overflow the native stack and crash the whole process instead of raising a catchable exception.
from dataclasses import dataclass, field


@dataclass
class Comment:
id: int
text: str
replies: list["Comment"] = field(default_factory=list)


def render_recursive(comment: Comment, depth: int = 0) -> list[str]:
lines = [f"{' ' * depth}{comment.text}"]
for reply in comment.replies:
lines.extend(render_recursive(reply, depth + 1))
return lines


def render_iterative(root: Comment, max_indent: int = 10) -> list[str]:
"""Same pre-order output, no recursion; indentation is capped for display."""
lines: list[str] = []
stack: list[tuple[Comment, int]] = [(root, 0)]
while stack:
comment, depth = stack.pop()
lines.append(f"{' ' * min(depth, max_indent)}{comment.text}")
for reply in reversed(comment.replies): # reversed keeps original order
stack.append((reply, depth + 1))
return lines


# Normal thread: both versions agree
thread = Comment(1, "root", [Comment(2, "a", [Comment(4, "a1")]), Comment(3, "b")])
assert render_recursive(thread) == render_iterative(thread)
print(render_iterative(thread))

# Bot-generated chain 5,000 levels deep
root = node = Comment(0, "spam-0")
for i in range(1, 5_000):
child = Comment(i, f"spam-{i}")
node.replies.append(child)
node = child

try:
render_recursive(root)
except RecursionError:
print("recursive version: RecursionError")
print("iterative version rendered", len(render_iterative(root)), "lines")

Workflow Diagram:

recursive: render(c0) → render(c1) → … → render(c999) ✗ RecursionError (call stack)

iterative: stack = [(c0, 0)]
loop: pop (c, d) ─▶ emit line ─▶ push replies reversed with d + 1
depth limited by heap memory, not by the interpreter call stack

Interviewer Notes:

  • The general lesson: any recursion whose depth depends on user data (nested JSON, comment trees, org charts, file trees, linked records) needs either an explicit stack or an enforced depth limit.
  • Nested JSON payloads are a related denial-of-service vector: deeply nested input can make recursive parsers or validators fail, so cap request size and nesting depth at the edge.

Red Flags:

  • sys.setrecursionlimit(10**6) as the fix.
  • Catching RecursionError and returning an empty thread.

Q50: Sort a 50 GB log file by timestamp on a machine with 4 GB of RAM​

Level: Principal

Scenario: An incident investigation needs a single, time-ordered view of 50 GB of logs gathered from many hosts (each host's file is roughly ordered, but the combined data is not). A quick script that calls sorted(open(path)) is OOM-killed. The data must be sorted on one machine with 4 GB of memory, today.

Impact: The incident timeline cannot be reconstructed; the team is debugging blind.

Root Cause: In-memory sorting needs the whole dataset (plus Python object overhead, often several times the raw size) in RAM. The data is an order of magnitude larger than available memory.

Fix: External merge sort:

  1. Run generation: read a chunk that fits comfortably in memory, sort it, and write it to a temporary file (a "run"). 50 GB in roughly 500 MB chunks gives about 100 runs.
  2. K-way merge: open all runs and merge them with a min-heap (Q35), streaming the output. Memory is O(k · buffer size), independent of total size.
  3. If there are too many runs to open at once (file descriptor limits or too little buffer per file), merge in multiple passes.
  4. Before writing code, consider existing tools: GNU sort performs external sorting with temporary files and supports options such as -S (buffer size), -T (temp directory) and --parallel; analytics engines like DuckDB or Spark can also sort out of core.
import heapq
import os
import random
import tempfile
from collections.abc import Iterator
from itertools import islice


def _write_run(lines: list[str], directory: str) -> str:
lines.sort()
fd, path = tempfile.mkstemp(dir=directory, suffix=".run")
with os.fdopen(fd, "w") as f:
f.writelines(lines)
return path


def external_sort(input_path: str, output_path: str, max_lines_in_memory: int) -> int:
"""Sort lines lexicographically (ISO-8601 timestamps sort correctly as text)."""
with tempfile.TemporaryDirectory() as tmp:
runs: list[str] = []
with open(input_path) as src:
while chunk := list(islice(src, max_lines_in_memory)):
runs.append(_write_run(chunk, tmp))

files = [open(path) for path in runs]
try:
with open(output_path, "w") as out:
merged: Iterator[str] = heapq.merge(*files) # lazy k-way merge
out.writelines(merged)
finally:
for f in files:
f.close()
return len(runs)


# Demo with a small file; the same code streams arbitrarily large inputs.
random.seed(1)
work = tempfile.mkdtemp()
src_path = os.path.join(work, "combined.log")
dst_path = os.path.join(work, "sorted.log")
with open(src_path, "w") as f:
for _ in range(25_000):
sec = random.randrange(86_400)
f.write(f"2025-03-01T{sec // 3600:02d}:{sec // 60 % 60:02d}:{sec % 60:02d}Z "
f"host-{random.randrange(40)} request handled\n")

runs = external_sort(src_path, dst_path, max_lines_in_memory=2_000)
with open(dst_path) as f:
result = f.readlines()
with open(src_path) as f:
original = f.readlines()
print(runs, "runs;", len(result), "lines; sorted:", result == sorted(original))

Workflow Diagram:

50 GB input
│ read 500 MB ──▶ sort in RAM ──▶ run_001.tmp
│ read 500 MB ──▶ sort in RAM ──▶ run_002.tmp (phase 1: ~100 sorted runs)
│ ...
▼
run_001 ┐
run_002 ├──▶ min-heap of current line from each run ──▶ sorted output (streamed)
run_100 ┘ (phase 2: k-way merge)
memory ≈ chunk size in phase 1, ≈ k read buffers in phase 2

Interviewer Notes:

  • Principal-level details: total I/O is about two reads and two writes of the data per merge pass, so disk throughput dominates; use fast local disk for temp files, compress runs if CPU is cheaper than I/O, and exploit existing order (presorted per-host files can skip run generation and go straight to the merge).
  • Sorting by a parsed key instead of raw text: use heapq.merge(..., key=...) and the same key when sorting each run.
  • This is the same algorithm databases use when an ORDER BY or index build does not fit in working memory ("spilling to disk").

Red Flags:

  • "Get a machine with 64 GB of RAM" as the only answer (sometimes pragmatic, but it does not scale and does not show understanding).
  • Loading everything into pandas without considering memory overhead.