FastPrepImplement Beam Search Decoding
Problems/Implement Beam Search Decoding

Implement Beam Search Decoding

Apple logoApple● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report asks for handwritten beam search but does not provide scores, stopping rules, normalization, ties or an interface. FastPrep supplies fixed-length integer-score decoding with explicit per-step pruning. Approximate source match: 60%.

Implement beam search over token sequences.

For this exercise, assume a fixed-length decoder with token IDs from 0 through V - 1. startScores[t] is the score for choosing token t first. nextScores[a][b] is the added score for choosing b after a. Scores are added; larger totals rank first.

  1. Begin with one empty sequence of score zero.
  2. At each step, extend every retained sequence with every token.
  3. Rank extensions by descending total score, breaking ties lexicographically by token IDs.
  4. Keep at most beamWidth extensions before the next step.

Return the retained sequences after exactly steps steps, in rank order. No end token or length normalization is used. Do not replace per-step pruning with a global search over all complete sequences.

Function

beamSearch(startScores: int[], nextScores: int[][], steps: int, beamWidth: int) → int[][]

Examples

Example 1

startScores = [0,-1]nextScores = [[-4,0],[0,-4]]steps = 3beamWidth = 2return = [[0,1,0],[1,0,1]]

After one step the beam is [[0],[1]]. After two steps it is [[0,1],[1,0]], with scores 0 and -1. After three steps it is [[0,1,0],[1,0,1]], again with scores 0 and -1.

Example 2

startScores = [0,-1]nextScores = [[-10,-10],[0,0]]steps = 2beamWidth = 1return = [[0,0]]

Width 1 keeps only [0] after the first step. Its two extensions tie at score -10, so [0,0] survives. The better-scoring [1,0] path cannot be recovered after [1] was pruned.

Example 3

startScores = [0,0]nextScores = [[0,0],[0,0]]steps = 2beamWidth = 3return = [[0,0],[0,1],[1,0]]

All scores tie. Lexicographic ordering keeps [0,0], [0,1], and [1,0] in that order.

Constraints

  • 1 <= startScores.length <= 12.
  • nextScores has startScores.length rows.
  • Every nextScores row has startScores.length values.
  • Every score is an integer from -1000 through 0.
  • 1 <= steps <= 8.
  • 1 <= beamWidth <= 20.

More Apple problems

  • Evaluate DivisionPHONE SCREEN · Seen Nov 2026
  • Reverse a Linked ListPHONE SCREEN · Seen Nov 2026
  • Validate a BST with a Custom ComparisonPHONE SCREEN · Seen Nov 2026
All Apple interview questionsSee Apple hiring insights
Saved
public int[][] beamSearch(int[] startScores, int[][] nextScores, int steps, int beamWidth) {
    // Write your solution here.
}
Checking account…