Coding Interview Workbook

Invariant: after counting, frequency is the source of truth and sorting only decides rank. Test ties, k = 0, one word, and more requested items than unique words.

from collections import Counter


def top_k_frequent_words(words, k):
    counts = Counter(words)
    ranked = sorted(counts, key=lambda word: (-counts[word], word))
    return ranked[:k]

Invariant: the output list is sorted and non-overlapping. The last output interval is the only interval that can overlap the current sorted input. Test touching intervals, nested intervals, unsorted input, empty input, and negative timestamps.

def merge_intervals(intervals):
    if not intervals:
        return []

    intervals = sorted(intervals)
    merged = [intervals[0][:]]
    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged

For metadata, carry an accumulator beside each merged range. Sum counts, take max for peak error rate, and preserve the contributing release IDs for debugging.

Invariant: every node popped from the queue has no remaining prerequisites. If the processed count is less than the course count, the remaining graph contains a cycle. Test no prerequisites, duplicate-looking chains, isolated courses, and a two-node cycle.

from collections import defaultdict, deque


def can_finish(num_courses, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * num_courses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    queue = deque(i for i, degree in enumerate(indegree) if degree == 0)
    seen = 0
    while queue:
        node = queue.popleft()
        seen += 1
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

    return seen == num_courses

Invariant: when formed == required, the current window satisfies all required counts. Shrink from the left until removing one character would break that invariant. The common mistake is checking only unique membership and ignoring duplicate counts.

from collections import Counter, defaultdict


def min_window(s, t):
    if not t or not s:
        return ""

    need = Counter(t)
    required = len(need)
    have = defaultdict(int)
    formed = 0
    left = 0
    best = (float("inf"), 0, 0)

    for right, ch in enumerate(s):
        have[ch] += 1
        if ch in need and have[ch] == need[ch]:
            formed += 1

        while formed == required:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)

            drop = s[left]
            have[drop] -= 1
            if drop in need and have[drop] < need[drop]:
                formed -= 1
            left += 1

    if best[0] == float("inf"):
        return ""
    return s[best[1]:best[2] + 1]

Keep a fixed-size deque of recent partials, compute the common prefix across them, and only emit newly committed text. In production, split on tokens rather than raw characters, track churn rate, and reset state at endpointing boundaries.

Use heaps for earliest deadline or shortest job first, sliding windows for recent arrival rate, queues for fairness per tenant, and binary search over batch size when latency is a monotonic function of batch size. The strong answer also includes metrics: queue age, drop reason, batch fill ratio, deadline miss rate, and cost per successful request.

Group by slice keys with a hash map, aggregate count, mean score, p95 latency, and failure rate, then sort by business-weighted regression. Require minimum sample counts so small noisy slices do not dominate the release decision.