DSA A Worked Mock Interview
A mock interview is a practice run of the interview loop under a time budget. This mock runs one medium and one hard problem, mistakes included.
Medium problem, brute force first
A hall rents rooms in time blocks, and overlapping blocks must merge. Counting the overlapping pairs first proves the merge has real work to do.
blocks = [[1, 10], [2, 3], [4, 5], [12, 14]]
overlaps = 0
for i in range(len(blocks)):
for j in range(i + 1, len(blocks)):
if blocks[i][0] < blocks[j][1] and blocks[j][0] < blocks[i][1]:
overlaps += 1
print("overlapping pairs:", overlaps)The first attempt and its bug
The first attempt compares each block with the previous original block. The block [4, 5] slips out of [1, 10], so the merge is wrong.
def merge_attempt(blocks):
blocks = sorted(blocks)
merged = [list(blocks[0])]
prev = blocks[0]
for cur in blocks[1:]:
if cur[0] <= prev[1]:
merged[-1][1] = max(merged[-1][1], cur[1])
else:
merged.append(list(cur))
prev = cur
return merged
print(merge_attempt([[1, 10], [2, 3], [4, 5]]))Hard problem, the wrong first route
The hard problem asks for the cheapest route between two towns. The first route minimises the number of roads, which says nothing about their prices.
from collections import deque
roads = {"A": ["B", "C"], "B": ["D"], "C": ["B", "D"], "D": []}
def fewest_edges(start, goal):
queue = deque([(start, [start])])
seen = {start}
while queue:
node, path = queue.popleft()
if node == goal:
return path
for nxt in roads[node]:
if nxt not in seen:
seen.add(nxt)
queue.append((nxt, path + [nxt]))
return []
print("fewest-edge route:", fewest_edges("A", "D"))Example
import heapq
from collections import deque
def merge_attempt(blocks):
blocks = sorted(blocks)
merged = [list(blocks[0])]
prev = blocks[0]
for cur in blocks[1:]:
if cur[0] <= prev[1]:
merged[-1][1] = max(merged[-1][1], cur[1])
else:
merged.append(list(cur))
prev = cur
return merged
def merge_fixed(blocks):
blocks = sorted(blocks)
merged = [list(blocks[0])]
for cur in blocks[1:]:
if cur[0] <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], cur[1])
else:
merged.append(list(cur))
return merged
medium_cases = [
([[1, 10], [2, 3], [4, 5]], [[1, 10]]),
([[9, 11], [1, 3], [2, 4]], [[1, 4], [9, 11]]),
([[1, 2], [3, 4]], [[1, 2], [3, 4]]),
]
print("medium attempt on case 1:", merge_attempt(medium_cases[0][0]),
"| expected", medium_cases[0][1], "| FAIL")
for blocks, expected in medium_cases:
got = merge_fixed(blocks)
total = sum(e - s for s, e in got)
verdict = "PASS" if got == expected else "FAIL"
print("medium fixed:", blocks, "->", got, "| total minutes", total, "|", verdict)
roads = {
"A": [("B", 9), ("C", 2)],
"B": [("D", 2)],
"C": [("B", 3), ("D", 7)],
"D": [],
}
cost_of = {}
for node, edges in roads.items():
for nxt, w in edges:
cost_of[(node, nxt)] = w
def fewest_edges_route(start, goal):
queue = deque([(start, [start])])
seen = {start}
while queue:
node, path = queue.popleft()
if node == goal:
return path
for nxt, _ in roads[node]:
if nxt not in seen:
seen.add(nxt)
queue.append((nxt, path + [nxt]))
return []
def route_cost(path):
return sum(cost_of[(path[i], path[i + 1])] for i in range(len(path) - 1))
def cheapest_route(start, goal):
dist = {start: 0}
prev = {}
heap = [(0, start)]
relaxations = 0
while heap:
cost, node = heapq.heappop(heap)
if cost > dist.get(node, float("inf")):
continue
if node == goal:
break
for nxt, w in roads[node]:
relaxations += 1
if cost + w < dist.get(nxt, float("inf")):
dist[nxt] = cost + w
prev[nxt] = node
heapq.heappush(heap, (cost + w, nxt))
path = [goal]
while path[-1] != start:
path.append(prev[path[-1]])
path.reverse()
return dist[goal], path, relaxations
attempt_path = fewest_edges_route("A", "D")
print("hard attempt:", attempt_path, "cost", route_cost(attempt_path),
"| expected cost 7 | FAIL")
for start, goal, expected in [("A", "D", 7), ("A", "B", 5), ("C", "D", 5)]:
cost, path, relaxations = cheapest_route(start, goal)
verdict = "PASS" if cost == expected else "FAIL"
print("hard fixed:", start, "->", goal, "cost", cost, "via", path,
"| relaxations", relaxations, "|", verdict)Key points
- A mock interview practises the loop under a time budget.
- A medium problem tests one pattern done cleanly.
- A hard problem tests patterns composed under pressure.
- A failing case is information about the code, not a disaster.
- The fix starts from the failing case, not from a blank page.
- Each problem closes with its complexity stated aloud.
In this example, the closing program is the mock itself, run in two halves. The medium problem had a budget of twenty minutes. Its first attempt compared each block with the previous original block. That attempt left [4, 5] outside [1, 10] and failed its first case. The fix compares each block with the last merged block instead. All three medium cases then passed, with total booked minutes of 9, 5, and 2. The hard problem had a budget of thirty-five minutes. Its first attempt took the route with the fewest roads, A to B to D, costing 11. The expected cost was 7, so that attempt failed too. The corrected route runs Dijkstra over the road prices. It found cost 7 through C and B, plus both smaller checks, in a handful of relaxations. The medium merge costs O(n log n) for its sort and O(n) extra space. The hard search costs O(E log V) time and O(V) space.
Note
The budgets live in the walkthrough, never inside the code.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
The attempt wrongly kept [4, 5] separate from the merged [1, 10]. What comparison caused the bug?