How should I practice Greedy and Beam Sentence Decoding?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft phone screen and onsite interview problems in FastPrep.

Is Greedy and Beam Sentence Decoding associated with Microsoft?

FastPrep tags this as a Microsoft phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

Greedy and Beam Sentence Decoding

Microsoft● HardFULLTIMEPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

Implement greedy decoding and beam search for a finite next-token probability model. Return the generated sentences and their raw probabilities.

The distinct strings in tokens form the vocabulary. The last string is <eos>. For this exercise, percentages[i][j] / 100 is the probability of generating token j when the previous token is i; each row sums to 100. The initial context is token startToken, which is not included in the returned sentence.

Stopping and sentence probabilities

A generated <eos> ends that hypothesis. Include its transition probability in the product, but omit it from the sentence.
Generate at most maxTokens transitions, including a possible <eos>. At the cutoff, return remaining unfinished hypotheses without appending an artificial ending token.
Join emitted ordinary tokens with one space. Immediate termination produces the empty string.
Write each raw probability as a reduced positive fraction numerator/denominator, including 1/1. Do not renormalize probabilities over the retained beam.

Two decoding strategies

Greedy decoding chooses the highest-probability next token at each step. Break ties by token text, treating <eos> as the empty string, which precedes every ordinary token.
Beam search starts with one empty hypothesis of probability 1. At each step, expand every unfinished hypothesis through every positive-probability next token and carry every finished hypothesis unchanged. Keep at most beamWidth hypotheses from this combined pool, ordered by descending raw probability and then ascending sentence text.
Finished hypotheses occupy beam slots and are never expanded again. Stop beam search when every survivor is finished or the transition cutoff is reached. Keep distinct sentences even when their last token matches.

Return a two-dimensional string array. Row 0 is [greedySentence, greedyProbability]. The remaining rows are the final beam's [sentence, probability] pairs in the stated order. The same sentence may appear in the greedy row and a beam row.

Interview follow-ups

Discuss how to reduce the time and space used to select the next beam. Explain why raw probability can favor short sentences, and how a length-aware scoring rule could change that preference. The judged output uses raw probabilities; a weighted scoring formula was not specified in the report. The report also discusses top-k and top-p sampling conceptually, while the implemented task is greedy and beam decoding.

Function

decodeSentences(tokens: String[], percentages: int[][], startToken: int, maxTokens: int, beamWidth: int) → String[][]

Examples

Example 1

tokens = ["start","a","b","<eos>"]percentages = [[0,60,40,0],[0,0,50,50],[0,0,0,100],[0,0,0,100]]startToken = 0maxTokens = 3beamWidth = 2return = [["a","3/10"],["b","2/5"],["a","3/10"]]

Greedy chooses a, then <eos> on the tie, with probability 3/10. Beam keeps b with probability 2/5 and a with probability 3/10.

Example 2

tokens = ["seed","pear","apple","<eos>"]percentages = [[0,50,50,0],[0,0,0,100],[0,0,0,100],[0,0,0,100]]startToken = 0maxTokens = 2beamWidth = 2return = [["apple","1/2"],["apple","1/2"],["pear","1/2"]]

Equal probabilities use sentence order, so apple precedes pear even though its vocabulary index is larger. Each probability is 1/2.

Example 3

tokens = ["seed","go","<eos>"]percentages = [[0,100,0],[50,50,0],[0,0,100]]startToken = 0maxTokens = 2beamWidth = 3return = [["go go","1/2"],["go go","1/2"],["go seed","1/2"]]

No hypothesis emits <eos> before the two-transition cutoff. Both remaining sentences have probability 1/2; greedy follows the lexical tie to go go.

Constraints

2 <= tokens.length <= 12.
Ordinary tokens are distinct lowercase English words of length 1..8; the final token is exactly <eos>.
percentages is a square matrix with one row and column per token. Entries are integers in 0..100, and each row sums to 100.
0 <= startToken < tokens.length - 1, 1 <= maxTokens <= 8, and 1 <= beamWidth <= 20.
The <eos> row is never queried after termination. All probability arithmetic can be represented exactly with signed 64-bit integers under these bounds.