← Microsoft Interview InsightsMachine Learning Engineer

Microsoft·Machine Learning Engineer·Technical Phone Screen·Senior

Senior
Jun 2026

Summary

Interviewed for an ML Engineer role at Microsoft and got a pretty technical coding question around sequence decoding. Nothing behavioral, just straight into the implementation.

Questions Asked (1)

Q1

Extend a greedy decoder to support beam search with a configurable beam width k. Walk through how you'd maintain multiple partial hypotheses, score extensions using log-probabilities, and handle end-of-sequence termination.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

This one took me a minute to get the log-probability part right.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by defining the beam search algorithm and how it extends greedy decoding by maintaining k hypotheses. Then walk through the iterative process: expanding each hypothesis, scoring with log-probabilities, selecting top k, and handling EOS. Finally, discuss termination conditions and trade-offs.

Pro tip: Emphasize that beam search with k=1 is equivalent to greedy decoding, and mention that length normalization is often needed to avoid favoring shorter sequences. Also, note that beam search can be parallelized across hypotheses for efficiency.

1. Initialize beam with start token

Begin with a single hypothesis containing the start-of-sequence token, with a cumulative log-probability of 0. Set up a list to hold the current beam of size up to k.

2. Expand each hypothesis

For each hypothesis in the current beam, compute the next-token probabilities using the model. Take the top k token candidates per hypothesis (or all if vocabulary is small) to form new extensions.

3. Score and select top k

For each extension, add the log-probability of the new token to the hypothesis's cumulative score. Collect all extensions, sort by score, and keep the top k hypotheses as the new beam.

4. Handle end-of-sequence

When a hypothesis generates the EOS token, mark it as complete and move it to a separate list of finished hypotheses. It no longer participates in expansion but remains for final selection.

5. Terminate and return best

Stop when all hypotheses in the beam are complete or a maximum length is reached. Return the completed hypothesis with the highest score, optionally applying length normalization.

Key Points to Mention

  • Log-probabilities prevent underflow and allow additive scoring.
  • Beam width k controls the trade-off between search quality and computational cost.
  • EOS handling: completed hypotheses are set aside and not expanded further.
  • Termination conditions: all beams hit EOS or max length.
  • Length normalization to avoid bias toward shorter sequences.
  • Parallelization: expanding hypotheses can be batched for efficiency.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.