DSA for AI Engineer Interviews
Not a general DSA list. This is scoped to what actually gets asked in AI/ML engineering loops — including the implementation questions no general list covers, and an explicit list of what you can skip.
72 nodes across 5 sections.
The single most common tool in a screening round. Most 'medium' problems are a hashmap in disguise.
Walk the input once, accumulate counts in a map, then answer questions from the map instead of the original data. The whole pattern is trading memory for a second pass you no longer need.
O(n) time, O(k) space where k is the number of distinct keys.
Reaching for a sort when you only need the most frequent item. Sorting is O(n log n); a counting pass plus a single max scan is O(n). If the interviewer asks for top-k rather than top-1, that's the cue to bring in a heap — not to sort the whole map.
Top K Frequent Elements
Valid Anagram
First Unique Character in a String
Building a vocabulary from a corpus is exactly this: count every token, then keep the ones above a threshold.
Keep a set of what you've already processed and skip repeats. Trivial when the key is the value itself; the interesting version is when you have to construct the key — a normalized form, a hash, a tuple of fields.
O(n) time, O(n) space worst case.
Choosing the wrong key. Deduping user records by exact string match misses 'a@b.com' vs 'A@B.com '. Interviewers often plant near-duplicates specifically to see whether you normalize before hashing.
Contains Duplicate
Find the Duplicate Number
Longest Consecutive Sequence
Corpus dedup before embedding. Exact-match dedup is cheap and catches a surprising amount; near-duplicate detection needs MinHash or embeddings, and knowing where the cheap method stops is the useful judgement.
Map each item to a key, then collect items sharing that key into buckets. The art is entirely in choosing the key function — the grouping itself is one pass.
O(n · k) where k is the cost of computing the key.
Computing an expensive key when a cheap canonical one exists. Grouping anagrams by sorting each word is O(n · m log m); using a 26-length character count is O(n · m). Interviewers watch for whether you notice.
Group Anagrams
Group Shifted Strings
Bucketing training samples by sequence length so batches pad efficiently — group by length bucket, not exact length.
Maintain a bidirectional map between items and integer positions. One direction for lookup, the other for reconstruction.
O(1) lookup each way, O(n) space.
Building only one direction and then needing the other. Also: forgetting to handle the unseen key at lookup time — in interview code that's a crash, in production it's the classic out-of-vocabulary bug.
Design HashMap
Encode and Decode Strings
Token-to-ID and ID-to-token maps. The unknown-token fallback is precisely the missing-key case you'd be asked to handle.
For each element, ask whether the value you need to pair with it has already been seen. One pass, storing what you've passed, checking for the complement as you go.
O(n) time, O(n) space.
Checking the map before inserting the current element matters — insert first and an element can pair with itself. The generalization to three-sum is where people stall: sort, fix one element, then two-pointer the remainder.
Two Sum
3Sum
Subarray Sum Equals K
Directly adjacent to retrieval. If you're interviewing for anything touching search or RAG, expect this.
Maintain a heap of size k while scanning n items. For the k largest, use a min-heap and evict the smallest whenever the heap exceeds k — the root is then your cutoff.
O(n log k) time, O(k) space. Beats O(n log n) sorting when k is small.
Using a max-heap for the k largest. It feels right and it's wrong — you need cheap access to the *smallest* of your current best k so you know what to evict. Getting this backwards is the single most common heap mistake in interviews.
Kth Largest Element in an Array
Top K Frequent Words
Sort Characters By Frequency
This is the final step of every vector search. ANN narrows the candidates; a bounded heap picks the winners.
Top-k with a distance function instead of a raw value. Structurally identical — the only change is what you compare on.
O(n log k) with a heap; O(n) average with quickselect.
Computing square roots. If you're only ranking, squared distance orders identically and skips n square-root operations. Mentioning this unprompted reads as someone who has actually optimized a hot loop.
K Closest Points to Origin
Find K Closest Elements
Brute-force nearest-neighbour search. The natural follow-up is 'now do it over ten million vectors' — which is where ANN enters.
Same bounded heap, but the input arrives as a stream you can't re-read and can't fully hold. The heap never exceeds k regardless of how much data flows through.
O(n log k) time, O(k) space — and the space bound is the point.
Materializing the stream. If you write `sorted(stream)[:k]`, you've defeated the entire premise. The interviewer is testing whether you noticed the constraint.
Kth Largest Element in a Stream
Design a Leaderboard
Scoring a corpus too large for memory: stream the chunks, score each one, keep only the running top-k.
Merge k already-sorted sequences by keeping one heap entry per sequence — the current head of each. Pop the smallest, emit it, and push that sequence's next element.
O(n log k) for n total elements across k lists.
Concatenating everything and sorting. That's O(n log n) and throws away the fact that the inputs were already sorted. Also: the heap must store which list each element came from, or you can't advance the right pointer.
Merge k Sorted Lists
Smallest Range Covering Elements from K Lists
Merging ranked results from multiple index shards, where each shard returns its own sorted list.
Keep a max-heap of the lower half and a min-heap of the upper half, rebalancing so their sizes differ by at most one. The median is then at one or both roots.
O(log n) per insertion, O(1) to read the median.
Letting the heaps drift out of balance. Rebalance after every insert, not occasionally. The even-count case needs the average of both roots — forgetting that returns a value that's merely near the median.
Find Median from Data Stream
Sliding Window Median
Cheap to learn, shows up constantly, and maps onto chunking work.
A window of constant width slides one position at a time. Instead of recomputing the window's value from scratch, add the entering element and subtract the leaving one.
O(n) time, O(1) extra space.
Recomputing the whole window each step, which quietly makes it O(n · k). Also the off-by-one at initialization — build the first full window before you start sliding.
Maximum Average Subarray I
Sliding Window Maximum
Fixed-size chunking with stride. Chunk 512 tokens, step 128 — that's a fixed window with an overlap of 384.
Expand the right edge greedily; when the window violates a constraint, contract the left edge until it's valid again. Each pointer only ever moves forward, which is why it stays linear despite the nested loop.
O(n) time — each element is added once and removed once.
Contracting with an `if` rather than a `while`. One expansion can make the window invalid by more than one element, and a single contraction step won't restore validity. This bug passes small test cases and fails larger ones.
Longest Substring Without Repeating Characters
Minimum Window Substring
Longest Repeating Character Replacement
Packing as much context as fits under a token budget: expand until you exceed the limit, then drop from the front.
Start a pointer at each end and move them toward each other, deciding at each step which side to advance based on a comparison. Requires the input to be sorted, or to have some monotonic property.
O(n) after sorting.
Applying it to unsorted input. The technique depends on knowing that moving one pointer can only change the result in one direction. If you sorted first, remember to say the sort dominates at O(n log n).
Container With Most Water
Valid Palindrome
Trapping Rain Water
Two pointers moving at different speeds through a sequence. If a cycle exists, the fast one eventually laps the slow one; if not, it reaches the end first.
O(n) time, O(1) space — the space bound is the whole reason to use it.
Null-checking only one step ahead. The fast pointer moves two, so you must confirm both `fast` and `fast.next` exist before advancing. Finding the cycle's start (rather than just detecting one) needs a second phase most people forget.
Linked List Cycle
Linked List Cycle II
Find the Duplicate Number
Especially binary search on the answer — the version most people haven't practised.
Halve the search range each step by comparing against the midpoint. The classic form, and the one everyone half-remembers.
O(log n).
The boundary conditions. `while (lo < hi)` and `while (lo <= hi)` need different update rules, and mixing them gives an infinite loop or an off-by-one. Pick one form and use it every time rather than deriving it fresh under pressure.
Binary Search
Search in Rotated Sorted Array
Find First and Last Position
You're not searching an array — you're searching the range of possible answers. It applies when a candidate answer can be checked as feasible or not, and feasibility is monotonic: if x works, everything above (or below) x works too.
O(log(range) · cost of the feasibility check).
Not verifying monotonicity before reaching for it. Binary search on a non-monotonic predicate returns a confident, wrong answer. State the monotonicity out loud — interviewers are listening for exactly that.
Koko Eating Bananas
Capacity To Ship Packages Within D Days
Split Array Largest Sum
Finding the largest batch size that fits in memory, or the similarity threshold that yields at most N results.
Rather than finding an element, find where it *would* go. Returns the index of the first element not less than the target, which is also the correct insertion point.
O(log n) to find, O(n) to actually insert into an array.
Forgetting that insertion itself is linear. Maintaining a sorted list by repeated bisect-and-insert is O(n²) overall — if that's the bottleneck, you want a different structure.
Search Insert Position
Longest Increasing Subsequence (the O(n log n) version)
Rarely the whole question, almost always part of it.
Sorting by something you compute rather than the value itself. In most languages this is a key function; the complexity is in defining a total order that behaves at the edges.
O(n log n) comparisons, plus n key computations.
Computing the key inside the comparator instead of once per element. That turns n key computations into n log n. Use the key-function form of your language's sort, not the comparator form, when the key is expensive.
Sort Colors
Largest Number
Custom Sort String
Ranking retrieval results by a blended score — similarity, recency, and an authority weight combined into one key.
A stable sort preserves the relative order of elements that compare equal. It's what lets you sort by one key, then another, and have the first act as a tie-breaker.
Same as the underlying sort; stability is a property, not a cost tier.
Assuming your language's sort is stable when it isn't. Python's `sorted` is; C++'s `std::sort` is not (`stable_sort` is). Getting this wrong produces results that are correct on average and wrong on ties — which is exactly the bug nobody notices until a user does.
Sort an array by two keys using two passes and stability
Reranking a result list must not scramble items the reranker scored equally. An unstable sort silently reorders them.
Quickselect partitions around a pivot like quicksort, but recurses into only the side containing the target rank. You get the k-th element, and everything before it, without ordering the rest.
O(n) average, O(n²) worst case with bad pivots.
Not mentioning the worst case. Random pivot selection or median-of-medians fixes it, and interviewers expect you to know the naive version degrades. Also: quickselect gives you the top k unordered — if the output must be sorted, you still pay O(k log k).
Kth Largest Element in an Array (via quickselect, not heap)
Shows up more than you'd expect via chunk-overlap and span problems.
Sort by start, then sweep left to right, extending the current interval whenever the next one starts before the current one ends.
O(n log n), dominated by the sort.
Sorting by end instead of start. It works for some interval problems and breaks merging. Also: deciding whether touching intervals ([1,2] and [2,3]) count as overlapping — ask, don't assume.
Merge Intervals
Insert Interval
Non-overlapping Intervals
Merging overlapping text spans after chunking, so the same sentence isn't stored twice.
Insert one interval into an already-sorted, non-overlapping list, merging with anything it touches. Three phases: everything strictly before, the merged middle, everything strictly after.
O(n) — no sort needed since the input is already ordered.
Sorting again. The input's sortedness is the gift; using it is the point of the problem.
Insert Interval
Count how many intervals overlap at the busiest moment. Either sweep start and end events in time order, or keep a min-heap of end times.
O(n log n).
Treating an end at time t and a start at time t as simultaneous. If a meeting ends when another begins, one room suffices — process ends before starts at equal timestamps.
Meeting Rooms II
Car Pooling
Sizing a worker pool for concurrent inference requests — the peak overlap is how many workers you need.
Know both cold. Everything else in this section builds on them.
Process the queue in batches, one level at a time, by recording the queue's length before draining exactly that many nodes.
O(V + E).
Reading the queue length inside the loop after you've started pushing children — it grows as you go and the level boundary dissolves. Capture the size first.
Binary Tree Level Order Traversal
Word Ladder
Rotting Oranges
Go as deep as possible before backtracking. Recursion is the natural expression; an explicit stack is the iterative equivalent when depth is a concern.
O(V + E) time, O(depth) space for the call stack.
Stack overflow on deep inputs — a 10,000-node path will blow Python's default recursion limit. Mentioning the iterative alternative unprompted is a good signal.
Number of Islands
Clone Graph
Path Sum
Treat each cell as a node with up to four neighbours. Every graph technique applies; only the adjacency definition changes.
O(rows × cols).
Forgetting to mark cells visited *when you enqueue*, not when you dequeue. Marking on dequeue lets the same cell enter the queue multiple times — still correct, but with a much worse constant, and it's a common source of timeouts.
Number of Islands
Rotting Oranges
Word Search
In an undirected graph, a cycle means reaching a visited node that isn't your parent. In a directed graph, it means reaching a node currently on the recursion stack — visited alone isn't enough.
O(V + E).
Using the undirected rule on a directed graph. Directed cycle detection needs three states (unvisited / in-progress / done), not two. This is the distinction interviewers specifically test.
Course Schedule
Graph Valid Tree
Find Eventual Safe States
Underrated for this role. Any pipeline, agent graph, or dependency resolver is a topo sort.
Count incoming edges for every node. Repeatedly take any node with zero in-degree, emit it, and decrement its neighbours. If you emit fewer nodes than exist, the graph had a cycle.
O(V + E) time and space.
Not checking the emitted count at the end. Kahn's algorithm silently produces a partial ordering when a cycle exists — it doesn't throw. The cycle check is the count comparison, and forgetting it is the classic error.
Course Schedule
Course Schedule II
Alien Dictionary
Resolving execution order in a pipeline or agent tool graph. The cycle check is what catches a circular dependency before it deadlocks at runtime.
Depth-first search, appending each node to a list *after* all its descendants are processed. Reverse the list for a valid topological order.
O(V + E).
Forgetting the reversal, or appending on entry rather than exit. Both produce a plausible-looking order that's wrong.
Course Schedule II
Alien Dictionary
Validating that a dependency graph is actually acyclic before you try to execute it. Same three-state DFS, used as a guard rather than an ordering.
O(V + E).
Reporting only that a cycle exists. In real use you need to say *which* nodes form it, which means tracking the recursion path, not just a boolean.
Course Schedule
Find Eventual Safe States
An agent tool graph where tool A calls B calls A. Catching it at load time beats deadlocking at runtime.
Traversal and simple recursion. Balanced-tree internals are not asked here.
Pre-order visits the node before its children, in-order between left and right, post-order after both. For a binary search tree, in-order yields sorted output — that property is the reason in-order is asked most.
O(n) time, O(height) space recursive.
Not knowing the iterative form. 'Now do it without recursion' is the standard follow-up, and in-order iterative with an explicit stack is the one people fumble.
Binary Tree Inorder Traversal
Validate Binary Search Tree
Kth Smallest in a BST
Top-down passes information from parent to child as an argument; bottom-up returns information from child to parent. Most tree problems are cleaner one way than the other.
O(n).
Choosing the wrong direction and ending up with a global mutable variable to compensate. If you're reaching for an outer-scope accumulator, the bottom-up formulation usually removes the need.
Maximum Depth of Binary Tree
Diameter of Binary Tree
Balanced Binary Tree
Problems where the answer is about a route through the tree rather than a single node — longest path, maximum sum path, root-to-leaf collections.
O(n).
In max-path-sum, the value you return to the parent is not the value you record as the answer. A path through a node can use both children; a path continuing upward can use only one. Conflating them is the classic error.
Binary Tree Maximum Path Sum
Diameter of Binary Tree
Path Sum II
Occasionally asked, usually when the role touches tokenization or autocomplete.
A tree where each edge is a character and each path from the root spells a prefix. Insertion walks or creates nodes; search walks and checks an end-of-word flag.
O(m) per operation for word length m, independent of dictionary size.
Omitting the end-of-word marker. Without it you can't distinguish a stored word from a mere prefix of one — 'car' looks present just because 'cart' is.
Implement Trie
Design Add and Search Words Data Structure
Walk the trie along the query prefix, then collect everything in the subtree below. The walk is the cheap part; the collection is what costs.
O(m) to locate, plus O(size of subtree) to collect.
Collecting the entire subtree when you only need the top few. Store a best-candidate at each node during insertion if you need ranked completions.
Search Suggestions System
Word Search II
Greedy longest-match tokenizers walk a trie of the vocabulary, taking the longest matching prefix at each position.
If you're interviewing anywhere near retrieval, assume at least one of these.
The dot product of two vectors divided by the product of their magnitudes. It measures the angle between them and ignores length entirely — which is why it's the default for comparing embeddings of different-length texts.
O(d) for dimension d — one pass computing three running sums.
Not handling the zero vector. A zero-magnitude vector divides by zero, and it happens in real data more often than you'd expect (empty string, all-stopword input). The second trap is doing three separate loops when one suffices.
Implement from scratch, no numpy
Then: cosine over a batch of N vectors
The follow-up is almost always: 'if all your vectors are L2-normalized, what does cosine reduce to?' Answer: the plain dot product — which is why vector databases normalize at insert time and use dot product at query time.
Dot product sums elementwise products and grows with magnitude. Euclidean distance measures straight-line separation. Cosine is dot product with magnitude divided out.
O(d) each.
Treating them as interchangeable. Dot product rewards longer vectors, so it favours longer documents when embeddings aren't normalized — a real, subtle relevance bug. Knowing that dot product on normalized vectors equals cosine is the distinction interviewers probe.
Implement all three, then compare their rankings on the same data
Divide every component by the vector's L2 norm so the result has length one. All normalized vectors sit on the unit sphere, which makes their dot products directly comparable.
O(d), two passes or one with a stored sum.
The zero vector again — guard the division. And normalizing repeatedly in a hot loop when you could normalize once at write time; this is a real cost at query volume.
Implement L2 normalization, then verify cosine(a,b) == dot(norm(a), norm(b))
Compute the distance from the query to every stored vector, then take the k smallest. Exact by construction, and completely adequate up to surprisingly large corpora.
O(n · d) for the scan, plus O(n log k) for selection.
Jumping straight to ANN. The right move is to build the exact version first, state its cost, and only then discuss approximation — because ANN trades recall for speed, and you need the exact baseline to know what recall you gave up. Candidates who skip to HNSW usually can't answer 'how much accuracy did you lose?'
Implement exact k-NN, then add a bounded heap, then discuss ANN
Three nested loops: for each output cell, sum the products along the shared dimension. Everything else in performance work is about memory access order, not the arithmetic.
O(n³) naive for square matrices.
Not knowing why loop order matters. The ikj ordering is dramatically faster than ijk in row-major memory because it reads contiguously — same operation count, very different cache behaviour. That observation is usually what the question is really about.
Implement matmul without numpy
Then reorder the loops and compare timings
Not deriving backprop — implementing the small, specific pieces correctly.
Exponentiate each logit and divide by the sum of exponentials, turning arbitrary scores into a probability distribution. The stable version subtracts the maximum logit from every element first.
O(n), three passes (max, exp-and-sum, divide) or two if you fuse.
The naive version overflows. exp(1000) is infinity in float64, and you get NaN. Subtracting the max makes the largest exponent exactly exp(0) = 1 and leaves the result mathematically identical, because the constant cancels between numerator and denominator. Being able to explain *why* it cancels is the actual question.
Implement stable softmax
Then log-softmax without computing softmax first
Any logit-to-probability step. The overflow is not theoretical — it shows up with unbounded logits from an untrained or badly initialized head.
Multiply queries by transposed keys, scale by the square root of the key dimension, softmax the result, then weight the values by those probabilities.
O(n² · d) for sequence length n — the quadratic term is why long context is hard.
Not being able to explain the scaling. Dot products of d-dimensional vectors grow with d, pushing softmax into its saturated region where gradients vanish. Dividing by sqrt(d_k) keeps the variance stable. 'It's in the paper' is not an answer.
Implement scaled dot-product attention
Then add a causal mask
Normalize each sample across its features to zero mean and unit variance, then apply learned scale and shift parameters.
O(d) per sample.
Confusing it with batch norm. Layer norm normalizes across features within one sample; batch norm normalizes across the batch per feature. Layer norm is used in transformers precisely because it doesn't depend on batch size — which matters at inference with batch size 1.
Implement layer norm
Then explain why transformers don't use batch norm
The negative log probability the model assigned to the correct class, averaged over examples. Confident and right is near zero; confident and wrong is large.
O(n) given probabilities.
Computing softmax then taking its log. That's numerically unstable — log(exp(x)) round-trips through a value that may have already overflowed. Fuse them into log-softmax, which is what every framework's `cross_entropy` actually does.
Implement cross-entropy from logits, not from probabilities
Common at inference-focused companies and for anything agent-related.
Divide logits by T before softmax. T below 1 sharpens the distribution toward the argmax; T above 1 flattens it toward uniform.
O(n).
T = 0. It's a division by zero, not 'maximum determinism' — implementations special-case it to greedy argmax rather than actually dividing. Knowing that it's a special case rather than a limit is the detail worth having.
Implement temperature scaling
Then plot the distribution at T = 0.1, 1, 2
Keep the k highest-probability tokens, renormalize over just those, and sample. Everything outside the top k gets probability zero.
O(n log k) with a heap, or O(n) with quickselect.
Forgetting to renormalize after truncation. The surviving probabilities no longer sum to one, and sampling from them is silently wrong. The deeper limitation: a fixed k is too permissive when the model is confident and too restrictive when it isn't — which is the argument for top-p.
Implement top-k sampling with renormalization
Sort by probability descending, accumulate until the running total reaches p, keep that set, renormalize, sample. The size of the kept set adapts to the model's confidence.
O(n log n) for the sort.
Off-by-one at the cutoff — you include the token that crosses the threshold, not just those strictly below it. Otherwise a single token with probability above p leaves you with an empty set.
Implement nucleus sampling
Then combine top-k and top-p and decide the order
Greedy takes the highest-probability token at each step. Beam search keeps the b most promising partial sequences and expands all of them, choosing the best complete sequence at the end.
Beam search is b times greedy's cost.
Not normalizing by length. Longer sequences accumulate more negative log-probability, so raw scores systematically favour short outputs. Length-normalized scoring is the standard fix, and forgetting it is why naive beam search produces truncated results.
Implement greedy decoding, then beam search with b = 3
String problems with an AI framing.
Start with characters. Repeatedly find the most frequent adjacent pair across the corpus and merge it into a single token. The ordered list of merges is the trained tokenizer.
O(merges × corpus) naive; real implementations use a priority queue over pair counts.
Merge order is not arbitrary — it must be replayed at encode time in exactly the training order, or you produce different tokens for the same text. The naive full recount after every merge is also what makes a from-scratch implementation unusably slow.
Implement the BPE merge loop on a small corpus
At each position, take the longest string in the vocabulary that matches starting there, then continue from the end of that match.
O(n × max_token_length), or O(n) with a trie.
Greedy is not optimal. Taking the longest match at each step can leave a remainder that tokenizes badly overall — a shorter first choice sometimes yields fewer tokens in total. Knowing that greedy is a heuristic, not the optimum, is the point.
Implement longest-match tokenization with a trie
Then find an input where greedy loses
Split a document into windows that overlap by a fixed amount, so a fact spanning a boundary appears complete in at least one chunk. A sliding window where the stride is smaller than the width.
O(n), and the storage multiplier is width / stride.
Chunking by characters when retrieval operates on tokens — your 512-'token' chunks are then unpredictably sized and some will overflow the model's limit. The second trap is ignoring structure: splitting mid-sentence or mid-code-block produces chunks that embed poorly and read worse.
Implement fixed-size chunking with overlap
Then: never split inside a paragraph
The overlap is not free — it multiplies your index size and your embedding bill. Being able to state that tradeoff is what separates someone who has run a RAG pipeline from someone who has read about one.
You have more retrieved context than fits in the prompt. Decide what to keep. The naive rule is highest-similarity-first until full; better rules account for diversity, recency, or source authority.
O(n log n) to rank, then a linear fill.
Truncating mid-chunk to fill the last few tokens. A half-chunk is often worse than no chunk — it can read as a complete but wrong statement. Drop whole units. Also: forgetting the system prompt and the expected output length count against the same budget.
Implement a greedy fill
Then: guarantee at least one chunk from each distinct source
The classic failure is retrieving five near-identical chunks that crowd out the one containing the actual answer. Diversity-aware selection — MMR, for instance — exists precisely for this.
Asked more at ML-leaning companies than at pure engineering ones.
Pick k initial centroids, assign each point to its nearest, recompute centroids as the mean of their members, repeat until assignments stop changing.
O(iterations × n × k × d).
Random initialization gives unstable results across runs — k-means++ spreads initial centroids and is the expected answer. Also: an empty cluster is a real case that crashes a naive implementation when you divide by zero members.
Implement k-means with k-means++ init
Then handle empty clusters
Precision is how many of your positive predictions were right. Recall is how many of the actual positives you caught. F1 is their harmonic mean.
O(n) over predictions.
Reporting accuracy on imbalanced data. At 1% positives, predicting all-negative scores 99% accuracy and is useless. Also: knowing which one to optimize is domain-dependent — recall matters more when a miss is expensive, precision when a false alarm is.
Implement precision, recall, F1 from a confusion matrix
recall@k asks what fraction of the relevant items appeared in your top k. MRR (mean reciprocal rank) asks how high the first relevant item ranked, averaged over queries — 1 for position one, 0.5 for position two, and so on.
O(1) per query given the ranked list and the ground truth.
Confusing recall@k with precision@k. Recall is over the relevant set; precision is over what you returned. For RAG, recall@k is usually the one that matters — if the answer isn't in the retrieved context, no amount of generation quality saves you. Also: MRR only ever considers the first hit, so it says nothing about the rest of the list.
Implement recall@k and MRR
Then nDCG, and explain when the discount matters
If you claim retrieval experience on your CV, expect to be asked to implement these. Not knowing them is a hard signal that the RAG project was a tutorial.
Discounted cumulative gain weights each result by its relevance, discounted logarithmically by position, then normalizes against the ideal ordering.
O(k log k) for the ideal ranking.
Skipping the normalization. Raw DCG isn't comparable across queries with different numbers of relevant items — the normalization against the ideal DCG is what makes it a fair average.
Implement nDCG@10
Then explain when it beats recall@k
The bridge between coding round and system design round. Often the last 10 minutes.
A bucket holds up to N tokens and refills at a fixed rate. Each request takes one token; empty bucket means reject or wait. Bursts are allowed up to the bucket's capacity, which is the property that makes it more useful than a fixed window.
O(1) per request. Compute refill lazily from elapsed time — no background timer.
Running a timer thread to add tokens. The clean implementation stores last-refill-time and computes the refill on access. The second trap is not clamping to capacity, which lets an idle bucket accumulate unlimited burst.
Implement a token bucket
Then: make it thread-safe
Then: distributed across processes
Every LLM API client needs one. The realistic follow-up is 'now enforce it across ten workers' — which forces the move to a shared store and introduces the race condition they actually want to discuss.
A hashmap for O(1) lookup plus a doubly-linked list for O(1) reordering. Access moves a node to the front; eviction removes from the back.
O(1) get and put.
Trying to do it with an array or a single map. Reordering in an array is O(n). The interview is specifically about realizing you need two structures cooperating — and about getting the linked-list pointer surgery right without a dummy-node crash.
LRU Cache
LFU Cache
Caching embeddings for repeated queries. The follow-up — 'now make it work across processes' — moves you to Redis and a different set of tradeoffs.
Accumulate incoming requests until either the batch is full or a timeout expires, then process them together. Throughput improves; individual latency gets worse.
O(1) per request to enqueue.
Only implementing the size trigger. Without the timeout, a single request during a quiet period waits indefinitely. The timeout is what bounds worst-case latency, and forgetting it is the common bug.
Implement a batcher with max size and max wait
Then make it thread-safe
Every inference server does this. The tradeoff — larger batches mean better GPU utilization and worse p99 latency — is the discussion the question exists to start.
On failure, wait before retrying, doubling the wait each time, up to a cap. Add random jitter so simultaneous failures don't retry in lockstep.
O(1) per attempt.
Omitting jitter. If a thousand clients fail at the same moment and all back off identically, they retry simultaneously and re-crash the service — the thundering herd. Jitter is the entire point of the question. Second trap: retrying non-retryable errors. A 400 will fail identically forever.
Implement exponential backoff with full jitter
Then classify which errors to retry
Know the shape: state, transition, base case, order.
An array where each entry is computed from earlier entries. Define what the index means, write the recurrence, set the base case, and iterate in dependency order.
O(n) time, O(n) space — often reducible to O(1).
Not stating the state definition before writing code. 'dp[i] is the maximum sum ending at i' versus 'the maximum sum in the first i elements' are different problems with different recurrences, and conflating them mid-implementation is where people get stuck.
Climbing Stairs
House Robber
Maximum Subarray
A 2D table where each cell depends on its neighbours above and to the left. Path-counting and path-cost problems are the canonical shapes.
O(rows × cols), often reducible to one row of space.
Initializing the first row and column carelessly. They have no upper or left neighbour and need explicit handling — most grid DP bugs live there rather than in the main recurrence.
Unique Paths
Minimum Path Sum
Maximal Square
Memoization is top-down: write the recursion, cache its results. Tabulation is bottom-up: fill a table in dependency order. Same recurrence, opposite direction.
Identical asymptotically; tabulation usually has a better constant.
Assuming they're always interchangeable. Memoization only computes states you actually reach, which wins when the reachable state space is sparse. Tabulation avoids recursion depth limits, which wins on deep inputs.
Solve one problem both ways and compare
Occasionally relevant — edit distance has a genuine NLP framing.
The minimum number of insertions, deletions, or substitutions to turn one string into another. A 2D table where each cell is the best of three neighbours.
O(m × n) time, O(min(m,n)) space if you only keep one row.
Getting the three transitions backwards. Diagonal is substitute (or match, at no cost), left is insert, up is delete — and mixing them produces a table that looks right and gives wrong answers on asymmetric inputs.
Edit Distance
Delete Operation for Two Strings
Word error rate in speech evaluation is edit distance over words. Fuzzy matching against retrieved text uses the same measure.
The longest sequence appearing in both inputs in order, though not necessarily contiguously. Same 2D table shape as edit distance.
O(m × n).
Confusing subsequence with substring. Substring requires contiguity and is a different, easier problem. Interviewers use the words precisely — mishearing costs you the whole question.
Longest Common Subsequence
Longest Increasing Subsequence
Real algorithms, real interviews somewhere — just not usually this one.