Katkat
Back

Design sequence decoding with greedy and beam search

CrestaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenMachine Learning

Last updated

This interview question evaluates core ML concepts, assumptions, math intuition, training/evaluation trade-offs, and practical failure modes in a realistic interview setting. A strong answer for Design sequence decoding with greedy and beam search states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given a probabilistic next-token dictionary D that maps each token t to a dictionary of candidate next tokens {u: p(u|t)}. Use '<START>' as the start token and '.' as the end-of-sequence token.

  1. Implement greedy decoding that, starting from '<START>', repeatedly selects the highest-probability next token until '.' is produced or no continuation exists. Provide both a recursive and an iterative version, and return the sequence of tokens (include '.' if produced). Analyze time and space complexity.
  2. Implement beam search decoding with beam width k using a BFS-style expansion: at each decoding step, maintain up to k highest-scoring partial sequences ranked by cumulative log-probability, expand each by its top-k next tokens from D, and continue until all beams end with '.'. Return the best sequence and optionally the top-k sequences. Explain how you handle ties, tokens missing from D, potential cycles or dead-ends, score normalization (e.g., length normalization), and termination criteria. Compare greedy and beam search in terms of quality, complexity, and typical use cases, and demonstrate your implementations on a small example dictionary.