cresta·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

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.

Questions Asked (2)

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.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The iterative version was fine, pretty mechanical.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem: greedy decoding selects the highest-probability next token at each step until the end token is reached. Then implement both recursive and iterative versions, ensuring the full sequence including the end token is returned. Finally, analyze time and space complexity, discussing trade-offs between recursion and iteration.

Pro tip: Mention that recursion depth could be an issue for long sequences, so iterative is often preferred in production; also note that greedy decoding is deterministic and may not be optimal for all tasks.

1. Clarify the problem and assumptions

Confirm the input format (dictionary mapping tokens to continuations with probabilities), the start token, and the end token. Ask if probabilities are guaranteed to sum to 1 and if there are cycles.

2. Design the greedy decoding logic

At each step, select the continuation with the highest probability. Append it to the sequence and continue until the end token is selected. Ensure the end token is included in the output.

3. Implement recursive version

Write a recursive function that takes the current token and accumulated sequence. Base case: if current token is end token, return sequence. Otherwise, find the highest-probability next token and recurse.

4. Implement iterative version

Use a loop: start with the start token, repeatedly look up the highest-probability next token, append to sequence, and update current token until end token is reached. Return the sequence.

5. Analyze time and space complexity

Time: O(n * m) where n is sequence length and m is average number of continuations per token (to find max). Space: O(n) for the sequence, plus O(n) recursion stack for recursive version.

Key Points to Mention

Greedy decoding selects the highest-probability token at each step, which is locally optimal but not globally optimal.
The end token must be included in the returned sequence; handle cases where end token is never reached (infinite loop) by assuming it will be reached or adding a max length.
Recursive implementation may hit recursion depth limits for long sequences; iterative is more robust.
Time complexity: O(n * m) where n is output length and m is average number of continuations per token; can be O(n) if using a precomputed argmax.
Space complexity: O(n) for the output sequence; recursive version adds O(n) call stack space.
Trade-offs: recursion is elegant but less efficient; iteration is more memory-efficient and avoids stack overflow.

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

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.

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

This is where I spent most of my time and honestly where things got messy.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by defining the problem and clarifying assumptions, then walk through the beam search algorithm step-by-step, covering edge cases and design decisions. Compare beam search with greedy decoding on quality, complexity, and use cases, and illustrate with a small example. Conclude with trade-offs and potential optimizations.

Pro tip: Emphasize that beam search is a heuristic and discuss how beam width and length normalization affect the quality-diversity trade-off, showing awareness of practical tuning.

1. Clarify Problem and Assumptions

Restate the problem, define inputs/outputs, and state assumptions about the model (e.g., provides log-probabilities, vocabulary, end-of-sequence token).

2. Describe Beam Search Algorithm

Explain BFS-style expansion: maintain top-k sequences by cumulative log-probability, expand each with all possible next tokens, prune to top-k, and repeat until termination.

3. Address Edge Cases and Design Decisions

Discuss handling ties (e.g., stable sort, random tie-breaking), missing tokens (e.g., unknown token handling), cycles/dead-ends (e.g., avoid infinite loops, handle EOS), score normalization (e.g., length normalization), and termination conditions (e.g., max length, EOS).

4. Compare Beam Search vs Greedy Decoding

Contrast quality (beam search finds higher-probability sequences), complexity (beam search O(k * V) per step vs greedy O(V)), and use cases (beam search for translation/summarization, greedy for real-time/low-resource).

5. Demonstrate with a Small Example

Walk through a tiny vocabulary and model to show how beam search with k=2 expands and selects sequences, highlighting differences from greedy.

Key Points to Mention

Cumulative log-probability and why log-space avoids underflow
Beam width trade-off: larger k improves quality but increases computation
Length normalization to prevent bias toward shorter sequences
Handling of EOS token and termination criteria
Tie-breaking strategies and their impact on determinism
Complexity analysis: O(k * V) per step vs O(V) for greedy

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