cresta·Software Engineer·Technical Phone Screen
Jun 2026
Cresta software engineer interview that went deep into NLP decoding algorithms. Two-part question covering greedy decoding and beam search, both with implementation and analysis. Pretty niche stuff if you haven't touched language model internals before.
- Given a probabilistic next-token dictionary mapping each token to its possible continuations with probabilities, implement greedy decoding starting from a start token. Provide both a recursive and an iterative version, return the full token sequence including the end token, and analyze time and space complexity.
- Implement beam search decoding with a configurable beam width using BFS-style expansion, maintaining the top-k partial sequences by cumulative log-probability at each step. Explain how you handle ties, missing tokens, cycles or dead-ends, score normalization like length normalization, and termination. Compare beam search vs greedy decoding on quality, complexity, and use cases, and demonstrate on a small example.
“The iterative version was fine, pretty mechanical.”