🎓 A1Learner
🔍

DSA Advanced Capstone — the Mock Gauntlet

The capstone is one program that solves four hard problems under interview conditions. A printed self-scoring rubric closes the program and the series.

Problem one, the partition search

The kth value across two sorted lists sits at a split of both lists. Binary search moves the split until every left value is at most every right value.

def kth_smallest(a, b, k):
    if len(a) > len(b):
        a, b = b, a
    lo = max(0, k - len(b))
    hi = min(k, len(a))
    while lo <= hi:
        i = (lo + hi) // 2
        j = k - i
        left_a = a[i - 1] if i > 0 else float("-inf")
        right_a = a[i] if i < len(a) else float("inf")
        left_b = b[j - 1] if j > 0 else float("-inf")
        right_b = b[j] if j < len(b) else float("inf")
        if left_a <= right_b and left_b <= right_a:
            return max(left_a, left_b)
        if left_a > right_b:
            hi = i - 1
        else:
            lo = i + 1
    return None

print("4th smallest of [1, 4, 9] and [2, 3, 8]:", kth_smallest([1, 4, 9], [2, 3, 8], 4))

Problem two, merges over ranges

Merging neighbouring piles costs the total weight of the piles merged. Short ranges are priced first, and longer ranges reuse their answers.

def min_merge(piles):
    n = len(piles)
    prefix = [0]
    for p in piles:
        prefix.append(prefix[-1] + p)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            cost = prefix[j + 1] - prefix[i]
            dp[i][j] = min(dp[i][m] + dp[m + 1][j] for m in range(i, j)) + cost
    return dp[0][n - 1]

print("cheapest merge of [4, 2, 3]:", min_merge([4, 2, 3]))

Problem three, one free road

Each town appears twice, once with the coupon unused and once with it spent. Dijkstra over those doubled states finds the cheapest route from A to D.

import heapq

def cheapest_with_coupon(roads, start, goal):
    dist = {(start, False): 0}
    heap = [(0, start, False)]
    while heap:
        cost, node, used = heapq.heappop(heap)
        if cost > dist.get((node, used), float("inf")):
            continue
        if node == goal:
            return cost
        for nxt, w in roads[node]:
            if cost + w < dist.get((nxt, used), float("inf")):
                dist[(nxt, used)] = cost + w
                heapq.heappush(heap, (cost + w, nxt, used))
            if not used and cost < dist.get((nxt, True), float("inf")):
                dist[(nxt, True)] = cost
                heapq.heappush(heap, (cost, nxt, True))
    return None

roads = {
    "A": [("B", 9), ("C", 2)],
    "B": [("D", 2)],
    "C": [("B", 3), ("D", 7)],
    "D": [],
}
print("cheapest A to D with one free road:", cheapest_with_coupon(roads, "A", "D"))

Problem four, a recent event counter

The design holds event times in a queue ordered by arrival. A count first drops every time outside the window, then reads the queue length.

from collections import deque

class RecentCounter:
    def __init__(self, window):
        self.window = window
        self.times = deque()

    def add(self, t):
        self.times.append(t)

    def count(self, t):
        while self.times and self.times[0] <= t - self.window:
            self.times.popleft()
        return len(self.times)

counter = RecentCounter(10)
counter.add(1)
counter.add(5)
print("count at 9:", counter.count(9))
counter.add(12)
print("count at 12:", counter.count(12))
print("count at 30:", counter.count(30))

Example

import heapq
from collections import deque

def kth_smallest(a, b, k):
    if len(a) > len(b):
        a, b = b, a
    lo = max(0, k - len(b))
    hi = min(k, len(a))
    while lo <= hi:
        i = (lo + hi) // 2
        j = k - i
        left_a = a[i - 1] if i > 0 else float("-inf")
        right_a = a[i] if i < len(a) else float("inf")
        left_b = b[j - 1] if j > 0 else float("-inf")
        right_b = b[j] if j < len(b) else float("inf")
        if left_a <= right_b and left_b <= right_a:
            return max(left_a, left_b)
        if left_a > right_b:
            hi = i - 1
        else:
            lo = i + 1
    return None

def min_merge(piles):
    n = len(piles)
    prefix = [0]
    for p in piles:
        prefix.append(prefix[-1] + p)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            cost = prefix[j + 1] - prefix[i]
            dp[i][j] = min(dp[i][m] + dp[m + 1][j] for m in range(i, j)) + cost
    return dp[0][n - 1]

def cheapest_with_coupon(roads, start, goal):
    dist = {(start, False): 0}
    heap = [(0, start, False)]
    while heap:
        cost, node, used = heapq.heappop(heap)
        if cost > dist.get((node, used), float("inf")):
            continue
        if node == goal:
            return cost
        for nxt, w in roads[node]:
            if cost + w < dist.get((nxt, used), float("inf")):
                dist[(nxt, used)] = cost + w
                heapq.heappush(heap, (cost + w, nxt, used))
            if not used and cost < dist.get((nxt, True), float("inf")):
                dist[(nxt, True)] = cost
                heapq.heappush(heap, (cost, nxt, True))
    return None

class RecentCounter:
    def __init__(self, window):
        self.window = window
        self.times = deque()

    def add(self, t):
        self.times.append(t)

    def count(self, t):
        while self.times and self.times[0] <= t - self.window:
            self.times.popleft()
        return len(self.times)

passed = 0
total_cases = 0

def report(family, case, expected, got):
    global passed, total_cases
    total_cases += 1
    ok = got == expected
    if ok:
        passed += 1
    print(family, "case", case, "| expected", expected, "| got", got,
          "|", "PASS" if ok else "FAIL")

for idx, (a, b, k, expected) in enumerate([
        ([1, 4, 9, 12], [2, 3, 8], 5, 8),
        ([5, 6, 7], [1, 2], 2, 2),
        ([], [4, 9], 2, 9)], start=1):
    report("P1 kth across two sorted lists", idx, expected, kth_smallest(a, b, k))

for idx, (piles, expected) in enumerate([
        ([4, 2, 3], 14),
        ([1, 2, 3, 4], 19),
        ([5, 5], 10)], start=1):
    report("P2 cheapest merge of piles", idx, expected, min_merge(piles))

roads_one = {
    "A": [("B", 9), ("C", 2)],
    "B": [("D", 2)],
    "C": [("B", 3), ("D", 7)],
    "D": [],
}
roads_two = {
    "X": [("Y", 4), ("W", 3)],
    "Y": [("Z", 6)],
    "W": [("Z", 9)],
    "Z": [],
}
report("P3 cheapest route, one free road", 1, 2,
       cheapest_with_coupon(roads_one, "A", "D"))
report("P3 cheapest route, one free road", 2, 3,
       cheapest_with_coupon(roads_two, "X", "Z"))

counter = RecentCounter(10)
counter.add(1)
counter.add(5)
results = [counter.count(9)]
counter.add(12)
results.append(counter.count(12))
results.append(counter.count(30))
report("P4 recent event counter", 1, [2, 2, 0], results)

print("SCORECARD:", passed, "of", total_cases, "cases passed")
print("RUBRIC binary search: a strong run states the partition invariant before coding.")
print("RUBRIC interval DP: a strong run fills ranges from short ranges to long ones.")
print("RUBRIC graph composition: a strong run names the doubled state before searching.")
print("RUBRIC design: a strong run states the cost of each operation before coding.")
print("HONESTY: every verdict above came from running this code, not from memory.")
print("COMPLEXITY: kth O(log n), merge O(n^3), coupon search O(E log V), counter O(1) amortised.")

Key points

  • One program solves four hard problems under interview conditions.
  • The first problem finds the kth value across two sorted lists by binary search.
  • Interval DP is dynamic programming whose state is a range of the input.
  • The second problem prices pile merges over ranges with interval DP.
  • A coupon is a token that makes one chosen road free.
  • The third problem runs Dijkstra over towns paired with the coupon state.
  • The fourth problem counts recent events with a queue that drops old timestamps.
  • Every case prints its expected value, its got value, and its verdict.

In this example, the gauntlet runs all four problems as tested functions in one program. The stated budgets were ten minutes for the binary search problem. The interval DP problem had twelve minutes. The graph problem had twelve minutes. The design problem had eight minutes. Problem one found the kth value across two sorted lists three times. Its cases covered a middle value, a value in the shorter list, and an empty list. Problem two priced the cheapest merge for three rows of piles. Problem three ran Dijkstra over doubled states and spent the coupon on the best road each time. Problem four drove the recent event counter through one fixed script of adds and counts. The scorecard printed 9 of 9 cases passed. The rubric then printed one line per family, plus an honesty line and a complexity line. Every technique in this program was taught earlier in this course.

Note

All four problems use original wording and original fixed data.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

In problem three, what extra fact does each search state carry besides the town?