Compare coding contracts, return values and complexity
Which implementation are you looking at?
The course has complete standalone problem bundles and an older shared helper module. Similar names do not guarantee identical behavior. For example, a longest-window helper returns a length, while the standalone problem returns positions so a UI can highlight the original text.
Use this page to compare contracts and costs after your attempt. Follow a standalone problem’s own reference when checking its exact output and rejection behavior. The tables below describe shared variants explicitly.
A pattern is useful when you can explain its invariant and recognize when it stops applying. Recent reports support studying maps/prefix sums, windows, graphs, caches, and practical implementation. They do not establish a global frequency ranking. Evidence.
Work a problem before opening the solution
For each exercise: restate the contract → show a small example → propose the simple approach → identify repeated work → state the invariant → code → test → analyze complexity → handle a changed constraint.
Use Python reference implementations (download file, source below) and TypeScript implementations (download file, source below) after attempting the task. These are original teaching exercises, not copies of proprietary interview packets.
Read the supplied code · algorithms.py
"""Reference solutions. Try the exercises in README.md before opening this file."""
from collections import Counter, OrderedDict, deque
from heapq import heappop, heappush, nlargest
def two_sum(nums, target):
visited = {}
for j, value in enumerate(nums):
complement = target - value
if complement in visited:
return visited[complement], j
visited.setdefault(value, j)
return None
def longest_unique(text):
left = best = 0
last_seen = {}
for right, char in enumerate(text):
left = max(left, last_seen.get(char, -1) + 1)
best = max(best, right - left + 1)
last_seen[char] = right
return best
def subarray_sum(nums, target):
prefix_counts = {0: 1}
prefix = result = 0
for value in nums:
prefix += value
result += prefix_counts.get(prefix - target, 0)
prefix_counts[prefix] = prefix_counts.get(prefix, 0) + 1
return result
def lower_bound(nums, target):
lo, hi = 0, len(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def merge_intervals(intervals):
"""Closed intervals; touching endpoints merge. Does not mutate input."""
out = []
for start, end in sorted(intervals):
if start > end:
raise ValueError('reversed interval')
if out and start <= out[-1][1]:
out[-1][1] = max(out[-1][1], end)
else:
out.append([start, end])
return out
def top_k_frequent(nums, k):
if k < 0:
raise ValueError('k must be nonnegative')
counts = Counter(nums)
# Higher count wins; smaller value breaks ties deterministically.
return nlargest(k, counts, key=lambda value: (counts[value], -value))
def islands(grid):
"""Rectangular list of lists of '0'/'1'; input remains unchanged."""
if not grid:
return 0
cols = len(grid[0])
if any(len(row) != cols or any(x not in ('0', '1') for x in row) for row in grid):
raise ValueError('expected rectangular binary grid')
seen = set()
count = 0
for r, row in enumerate(grid):
for c, value in enumerate(row):
if value != '1' or (r, c) in seen:
continue
count += 1
seen.add((r, c))
queue = deque([(r, c)])
while queue:
x, y = queue.popleft()
for a, b in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
if 0 <= a < len(grid) and 0 <= b < cols and grid[a][b] == '1' and (a, b) not in seen:
seen.add((a, b)) # Mark on enqueue, not dequeue.
queue.append((a, b))
return count
def course_order(n, prerequisites):
"""Each pair is (course, prerequisite); [] means a cycle or no courses."""
if n < 0:
raise ValueError('negative course count')
adjacency = [set() for _ in range(n)]
degree = [0] * n
for course, prerequisite in prerequisites:
if not 0 <= course < n or not 0 <= prerequisite < n:
raise ValueError('course outside graph')
if course not in adjacency[prerequisite]:
adjacency[prerequisite].add(course)
degree[course] += 1
queue = deque(i for i, d in enumerate(degree) if d == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in adjacency[node]:
degree[neighbor] -= 1
if degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == n else []
def shortest_paths(n, edges, source):
"""Directed nonnegative weighted graph; unreachable distances are infinity."""
if not 0 <= source < n:
raise ValueError('invalid source')
graph = [[] for _ in range(n)]
for u, v, weight in edges:
if not 0 <= u < n or not 0 <= v < n or weight < 0:
raise ValueError('invalid edge')
graph[u].append((v, weight))
distance = [float('inf')] * n
distance[source] = 0
heap = [(0, source)]
while heap:
cost, node = heappop(heap)
if cost != distance[node]:
continue
for neighbor, weight in graph[node]:
candidate = cost + weight
if candidate < distance[neighbor]:
distance[neighbor] = candidate
heappush(heap, (candidate, neighbor))
return distance
class LRU:
"""Capacity in entries; None denotes a miss. Not thread-safe."""
def __init__(self, capacity):
if capacity < 0:
raise ValueError('negative capacity')
self.capacity = capacity
self.data = OrderedDict()
def get(self, key):
if key not in self.data:
return None
self.data.move_to_end(key)
return self.data[key]
def put(self, key, value):
if self.capacity == 0:
return
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False)
def min_coins(coins, amount):
if amount < 0 or any(c <= 0 for c in coins):
raise ValueError('nonnegative amount and positive coins required')
dp = [0] + [amount + 1] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total:
dp[total] = min(dp[total], dp[total-coin] + 1)
return -1 if dp[amount] > amount else dp[amount]
def daily_temperatures(temperatures):
answer = [0] * len(temperatures)
stack = []
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
previous = stack.pop()
answer[previous] = i - previous
stack.append(i)
return answer
def word_exists(board, word):
"""4-neighbor word search; do not reuse a cell or mutate the board."""
if not word:
return True
if not board:
return False
cols = len(board[0])
if any(len(row) != cols for row in board):
raise ValueError('ragged board')
def visit(r, c, index, used):
if not (0 <= r < len(board) and 0 <= c < cols) or (r, c) in used or board[r][c] != word[index]:
return False
if index == len(word) - 1:
return True
used.add((r, c))
found = any(visit(a, b, index+1, used) for a, b in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)))
used.remove((r, c))
return found
return any(visit(r, c, 0, set()) for r in range(len(board)) for c in range(cols))
class Trie:
END = object()
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.END] = True
def contains(self, word):
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return self.END in node
Read the supplied code · typescript.ts
/** Bounded workers: preserve input order; drain started work and report errors per item. */
export async function mapLimit<T, R>(items: readonly T[], limit: number, fn: (item: T, index: number) => Promise<R>): Promise<PromiseSettledResult<R>[]> {
if (!Number.isInteger(limit) || limit < 1) throw new RangeError('positive integer limit required');
const out: PromiseSettledResult<R>[] = new Array(items.length);
let next = 0;
async function worker() {
while (next < items.length) {
const index = next++; // No await between reading and claiming the index.
try { out[index] = { status: 'fulfilled', value: await fn(items[index], index) }; }
catch (reason) { out[index] = { status: 'rejected', reason }; }
}
}
await Promise.all(Array.from({ length: Math.min(limit, items.length) }, worker));
return out;
}
/** Aborting old work saves resources where supported. The generation guard protects correctness. */
export function latestOnly<T>(load: (query: string, signal: AbortSignal) => Promise<T>, render: (value: T) => void) {
let generation = 0;
let active: AbortController | undefined;
return async (query: string): Promise<boolean> => {
const own = ++generation;
active?.abort();
const controller = new AbortController();
active = controller;
try {
const value = await load(query, controller.signal);
if (own !== generation) return false;
render(value);
return true;
} catch (error) {
if (own !== generation) return false;
throw error; // Current request failure must be visible to the caller/UI.
}
};
}
export class LRU<K, V> {
private readonly values = new Map<K, V>();
private readonly capacity: number;
constructor(capacity: number) {
if (!Number.isInteger(capacity) || capacity < 0) throw new RangeError('nonnegative integer capacity required');
this.capacity = capacity;
}
get(key: K): V | undefined {
if (!this.values.has(key)) return undefined;
const value = this.values.get(key) as V;
this.values.delete(key);
this.values.set(key, value);
return value;
}
put(key: K, value: V) {
if (this.capacity === 0) return;
this.values.delete(key);
this.values.set(key, value);
if (this.values.size > this.capacity) this.values.delete(this.values.keys().next().value as K);
}
}
export type Bookmark = { id: string; title: string; version: number };
/** Apply a server response only if no newer local/server version is known. */
export function reconcile(current: Bookmark, incoming: Bookmark): Bookmark {
if (current.id !== incoming.id) throw new Error('different entity');
return incoming.version >= current.version ? incoming : current;
}
Read why each pattern works for the invariants, pitfalls, and language-specific costs.
Shared variants are not the 42 standalone bundles
The standalone registry (download file, source below) identifies each bundle's own brief, implementation and isolated tests. This page describes the separate shared helpers; passing their tests does not validate the bundles.
Read the supplied code · problem-bank.json
[
{
"number": 1,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/01-two-sum/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/01-two-sum",
"title": "Two sum: remember the useful past"
},
{
"number": 2,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/02-valid-anagram/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/02-valid-anagram",
"title": "Valid anagram: equality of multiplicities"
},
{
"number": 3,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/03-group-anagrams/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/03-group-anagrams",
"title": "Group anagrams: canonical keys"
},
{
"number": 4,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/04-longest-unique-window/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/04-longest-unique-window",
"title": "Longest unique window: move the boundary forward"
},
{
"number": 5,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/05-minimum-covering-window/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/05-minimum-covering-window",
"title": "Minimum covering window: track unmet demand"
},
{
"number": 6,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/06-subarray-sum-count/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/06-subarray-sum-count",
"title": "Count target-sum subarrays: differences of prefixes"
},
{
"number": 7,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/07-product-except-self/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/07-product-except-self",
"title": "Product except self: combine independent summaries"
},
{
"number": 8,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/08-longest-consecutive/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/08-longest-consecutive",
"title": "Longest consecutive run: expand only from starts"
},
{
"number": 9,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/09-merge-intervals/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/09-merge-intervals",
"title": "Merge intervals: preserve the covered set"
},
{
"number": 10,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/10-meeting-room-capacity/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/10-meeting-room-capacity",
"title": "Meeting room capacity: count simultaneous demand"
},
{
"number": 11,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/11-binary-search-boundary/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/11-binary-search-boundary",
"title": "Binary search boundary: find the first true position"
},
{
"number": 12,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/12-rotated-array-search/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/12-rotated-array-search",
"title": "Rotated array search: identify the ordered half"
},
{
"number": 13,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/13-shipping-capacity/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/13-shipping-capacity",
"title": "Shipping capacity: search a feasible answer"
},
{
"number": 14,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/14-reverse-linked-list/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/14-reverse-linked-list",
"title": "Reverse a linked list: keep the unprocessed suffix reachable"
},
{
"number": 15,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/15-linked-list-cycle-entry/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/15-linked-list-cycle-entry",
"title": "Cycle entry: relative motion and identity"
},
{
"number": 16,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/16-merge-sorted-lists/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/16-merge-sorted-lists",
"title": "Merge sorted lists: splice only a safe frontier"
},
{
"number": 17,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/17-tree-level-order/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/17-tree-level-order",
"title": "Tree level order: keep the next frontier separate"
},
{
"number": 18,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/18-validate-bst/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/18-validate-bst",
"title": "Validate a BST: carry every ancestor constraint"
},
{
"number": 19,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/19-lowest-common-ancestor/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/19-lowest-common-ancestor",
"title": "Lowest common ancestor: return presence as well as a candidate"
},
{
"number": 20,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/20-tree-diameter/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/20-tree-diameter",
"title": "Tree diameter: return one branch, combine two locally"
},
{
"number": 21,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/21-dependency-order/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/21-dependency-order",
"title": "Dependency order"
},
{
"number": 22,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/22-word-ladder/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/22-word-ladder",
"title": "Word ladder"
},
{
"number": 23,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/23-disjoint-set-connectivity/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/23-disjoint-set-connectivity",
"title": "Connectivity under added links"
},
{
"number": 24,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/24-grid-shortest-path/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/24-grid-shortest-path",
"title": "Shortest path through a grid"
},
{
"number": 25,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/25-weighted-shortest-path/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/25-weighted-shortest-path",
"title": "Cheapest route with nonnegative costs"
},
{
"number": 26,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/26-top-k-stream/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/26-top-k-stream",
"title": "Top k observations in a stream"
},
{
"number": 27,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/27-merge-k-streams/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/27-merge-k-streams",
"title": "Merge k sorted streams"
},
{
"number": 28,
"path": "curriculum/04-scale-and-evolution/01-data-at-scale/problems/28-manual-lru-cache/README.md",
"directory": "curriculum/04-scale-and-evolution/01-data-at-scale/problems/28-manual-lru-cache",
"title": "Implement LRU without an ordered-map helper"
},
{
"number": 29,
"path": "curriculum/04-scale-and-evolution/01-data-at-scale/problems/29-expiring-key-value-store/README.md",
"directory": "curriculum/04-scale-and-evolution/01-data-at-scale/problems/29-expiring-key-value-store",
"title": "Expiring key-value store"
},
{
"number": 30,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/30-trie-autocomplete/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/30-trie-autocomplete",
"title": "Prefix autocomplete"
},
{
"number": 31,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/31-combination-search/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/31-combination-search",
"title": "Search for unique combinations"
},
{
"number": 32,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/32-word-search/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/32-word-search",
"title": "Find a word without reusing a cell"
},
{
"number": 33,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/33-coin-change/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/33-coin-change",
"title": "Minimum coins with a witness"
},
{
"number": 34,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/34-longest-increasing-subsequence/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/34-longest-increasing-subsequence",
"title": "Longest increasing subsequence"
},
{
"number": 35,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/35-edit-distance/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/35-edit-distance",
"title": "Edit distance"
},
{
"number": 36,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/36-decode-ways/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/36-decode-ways",
"title": "Count valid digit decodings"
},
{
"number": 37,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/37-daily-temperatures/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/37-daily-temperatures",
"title": "Days until a warmer temperature"
},
{
"number": 38,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/38-largest-histogram-rectangle/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/38-largest-histogram-rectangle",
"title": "Largest rectangle in a histogram"
},
{
"number": 39,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/39-policy-expression-evaluator/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/39-policy-expression-evaluator",
"title": "Parse and evaluate a policy expression"
},
{
"number": 40,
"path": "curriculum/04-scale-and-evolution/01-data-at-scale/problems/40-event-time-windows/README.md",
"directory": "curriculum/04-scale-and-evolution/01-data-at-scale/problems/40-event-time-windows",
"title": "Count event-time windows with late arrivals"
},
{
"number": 41,
"path": "curriculum/01-code/02-data-structures-algorithms/problems/41-streaming-median/README.md",
"directory": "curriculum/01-code/02-data-structures-algorithms/problems/41-streaming-median",
"title": "Maintain an exact streaming median"
},
{
"number": 42,
"path": "curriculum/02-applications/01-backend/problems/42-bounded-blocking-queue/README.md",
"directory": "curriculum/02-applications/01-backend/problems/42-bounded-blocking-queue",
"title": "Bounded blocking queue with shutdown"
}
]
| Shared helper | Standalone contract |
|---|---|
longest_unique returns a length |
Problem 04 returns a window/slice |
LRU uses None for a miss |
The manual LRU bundle raises KeyError |
lower_bound assumes sorted input |
Problem 11 validates ordering first: O(n) overall |
Read each bundle's input, empty and invalid-case contract. Python accepting extra values does not itself prove an algorithm wrong; promised rejection behavior must still be implemented and tested.
Python problem set
Hash operations below are expected average O(1). Space includes copied input and working structures, excluding only the caller's original input. n is input length; u unique items; V/E graph vertices/edges; A target amount; m coin count; L word length.
| Problem / function | Contract and example | Baseline → implementation | Time / auxiliary space | Follow-up |
|---|---|---|---|---|
Two sum · two_sum |
Two distinct indices for target; [3,3],6 → (0,1); no pair → None |
All pairs → complement map | O(n) / O(n) | Return all pairs without duplicates |
Longest unique substring · longest_unique |
abba → 2; empty → 0 |
Enumerate substrings → last-seen window | O(n) / O(u) | User-visible graphemes instead of Python code points |
Subarray sum K · subarray_sum |
[1,-1,1],1 → 3; contiguous and nonempty |
Running sum per start → prefix-frequency map | O(n) / O(n) | Stream input; zeros and negative numbers |
First element ≥ target · lower_bound |
Sorted array [1,2,2,5],2 → 1; absent returns insertion index |
Scan → half-open binary search | O(log n) / O(1) | Search answer space using a monotone feasibility test |
Merge intervals · merge_intervals |
Closed intervals; [1,3],[3,4] → [1,4] |
Repeated comparisons → sort and scan | O(n log n) / O(n) including sorted copy | Half-open calendar events should not merge merely touching endpoints |
Top K frequent · top_k_frequent |
Return at most K distinct values; smaller value breaks equal-frequency ties | Sort counts → bounded heap via nlargest |
O(n + u log(k+1)) when 0<k<u; O(n+u log u) when k≥u / O(u+k) | Buckets use O(n+u) space; streaming needs a memory policy |
Islands · islands |
Count 4-connected '1' cells; rectangular grid unchanged | Revisit cells → visited-set BFS | O(rows×cols) / O(rows×cols) | In-place marking changes the contract; diagonal connectivity changes the graph |
Course order · course_order |
Pair (course, prerequisite); one valid order; [] on cycle |
Try permutations → indegree queue | O(V+E) / O(V+E) | Capacity per semester is a different optimization problem |
Weighted shortest paths · shortest_paths |
Directed nonnegative edges; unreachable → infinity | Repeated relaxation → Dijkstra | O(V + E log(E+1)) / O(V+E), lazy heap may hold O(E) entries | Negative edges invalidate this algorithm |
LRU · LRU |
Get refreshes recency; capacity 0 stores nothing; None is miss | Scan recency → OrderedDict | Expected O(1) get/put / O(capacity) | Bytes instead of entries, TTL, synchronization |
Coin change · min_coins |
Minimum coins, unlimited reuse; [1,3,4],6 → 2; impossible → -1 |
Enumerate choices → bottom-up DP | O(A×m) / O(A) | Why greedy chooses the wrong result for this example |
Warmer day · daily_temperatures |
Distance to next strictly warmer day; none → 0 | Forward scan for every day → monotonic stack | O(n) / O(n) | Equal temperatures must stay unresolved |
Word search · word_exists |
4-neighbor traversal; cannot reuse a cell; empty word → true | Enumerate paths with backtracking and undo | O(rows×cols×4^L) conservative bound / O(L) | Multiple words can share trie prefixes |
Exact word lookup · Trie |
Insert/search; a prefix is not automatically a word | Scan dictionary → prefix tree | O(L) per operation / O(total stored characters) | Autocomplete ranking and Unicode normalization |
Inputs are ordinary finite integers/strings; array elements are not runtime-type-validated. Graph endpoints, malformed grids, capacities, and coin domains have explicit checks in code. Python arbitrary-precision integer costs are simplified to unit-cost arithmetic for interview analysis; say so if inputs are huge.
Worked lesson 1 · prefix sums
Without a memory of earlier prefixes, we repeatedly sum the same elements. Define prefix[j] as the sum before index j. A subarray i..j-1 sums to K exactly when prefix[i] = prefix[j] - K. Store the number of previous occurrences, not just a set. Two equal earlier prefixes represent two different starts.
For [1,-1,1], K=1:
| Read | Prefix | Earlier prefix needed | New matches | Map after insertion |
|---|---|---|---|---|
| Start | 0 | — | 0 | {0:1} |
| 1 | 1 | 0 | 1 | {0:1,1:1} |
| -1 | 0 | -1 | 0 | {0:2,1:1} |
| 1 | 1 | 0 | 2 | {0:2,1:2} |
counts = {0: 1}
prefix = answer = 0
for value in nums:
prefix += value
answer += counts.get(prefix - target, 0)
counts[prefix] = counts.get(prefix, 0) + 1
Look up before insertion so target 0 does not count an empty range. Initial {0:1} accounts for ranges starting at index 0. Sliding windows that shrink based only on exceeding a target do not generally work with negative values. Remove the initial zero or reverse lookup/insertion and find the smallest failing input.
Worked lesson 2 · sliding windows
The invariant is that text[left:right+1] contains no repeated character. On a repeated character, move left just past its last occurrence—but never backwards. With abba, after the second b, left is 2; the last a at index 0 must not move it back to 1. That is why the implementation uses max(left, last[char]+1).
Each right pointer position is visited once. Even though the substring may contain many characters, we do not rescan it. Explain why O(n) time does not imply O(1) space here.
Worked lesson 3 · graphs and dependencies
BFS explores equal-cost edges by distance layers. Mark on enqueue to avoid repeated frontier entries. Dijkstra uses the smallest tentative distance, so it can process a later-discovered cheap route before an earlier expensive one. A stale heap entry is discarded when it no longer matches the best distance.
For 0→1, 0→2, 1→3, 2→3, initial indegrees are [0,1,1,2]. Removing 0 releases 1 and 2; 3 stays blocked until both complete. If the processed count is less than V, a cycle prevents a complete ordering.
A capacity-constrained “minimum semesters” follow-up is not solved merely by adding a heap. A heuristic that prioritizes longest downstream chains needs proof; for small n, model completed courses as a bitmask and search eligible subsets. State the exponential cost rather than claiming greedy is always optimal. This distinction is motivated by an explicitly uncertain candidate report, not adopted from its proposed solution.
Worked lesson 4 · LRU and interfaces
A hash map locates an item. A recency list tracks eviction order. Get and put both move an item to the most-recent end; eviction removes the least-recent item. Python's OrderedDict exposes these operations; be ready to implement a doubly linked list if the interviewer disallows helpers.
Trace capacity 2: put A, put B, get A, put C. B must be evicted. Updating A must not consume an extra slot. Byte capacity introduces an item-size function and potentially several evictions per write; one insertion is no longer necessarily O(1).
TypeScript's Map preserves insertion order, so delete+set refreshes recency. ECMAScript requires average sublinear access, not a blanket formal O(1) guarantee; expected O(1) hash-map reasoning is the usual implementation model. Distinguish a missing value from a legitimately stored undefined if your API allows it.
TypeScript and practical rounds
Practical exercises teach bounded concurrency, cancellation, debugging, API integration, and AI review. Full stack connects those snippets to an application.
Primary references checked 2026-09-22: Python heapq, collections, ECMAScript Map.