Implement Beam Search
On this page
Problem statement
Implement beam search decoding. You get a function
next_log_probs(seq)that returns a dictionary of possible next tokens and their log probabilities given a sequence. Starting from a start token, return the highest-scoring complete sequence (ending in an end token) found with beam width W, within a maximum length, with optional length normalisation.
A classic decoding question for ML and inference roles; it checks search, bookkeeping and the classic length-bias trap.
Example

greedy → <s> the </s> p = 0.5 × 0.4 = 0.20
beam (W = 2) → <s> a cat </s> p = 0.4 × 0.9 × 1.0 = 0.36
Constraints (assumed)
- W from 1 to about 10; vocabulary given as a dictionary per step (in a real model, a vector of size V).
- Maximum length up to a few hundred tokens.
- Pure Python for the interview version.
What this question tests
- Search bookkeeping: expanding, pruning, finished vs active beams.
- Log-space arithmetic to avoid underflow.
- Knowing the length bias and how to normalise.
- Comparing with greedy and sampling, and knowing when beam search is the wrong tool.
Questions to ask first
- Should finished sequences stay in the beam or move aside? (Move aside.)
- Length normalisation: yes, and which formula? (log p / length^α, α configurable.)
- What if no beam finishes before max length? (Return the best unfinished one.)
- Is the next-token function batched? (No, one sequence per call here.)
- Any constraints such as no repeated n-grams? (Not here; a follow-up.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.