Top-p Nucleus Sampling Algorithm | Dataford Interview Questions

Given a stream of token probabilities, write an efficient algorithm to implement top-p nucleus sampling.

Implement sample_top_p(probabilities, p, random_value). The probabilities are aligned with token indices and sum to 1.0. Return the selected token index after retaining the smallest probability set whose cumulative probability is at least p, renormalizing that set, and sampling with random_value in [0, 1).

Use descending probability order, breaking ties by the original token index.

Constraints

1 <= len(probabilities) <= 5000
0.0 <= probabilities[i] <= 1.0
The probabilities sum to 1.0 within floating-point precision
0.0 < p <= 1.0
0.0 <= random_value < 1.0
Return the original zero-based token index

Function Signature

def sample_top_p(probabilities, p, random_value):

Your question is Top-p Nucleus Sampling Algorithm. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Given a stream of token probabilities, write an efficient algorithm to implement top-p nucleus sampling.

Use descending probability order, breaking ties by the original token index.

Constraints

1 <= len(probabilities) <= 5000
0.0 <= probabilities[i] <= 1.0
The probabilities sum to 1.0 within floating-point precision
0.0 < p <= 1.0
0.0 <= random_value < 1.0
Return the original zero-based token index

Function Signature

def sample_top_p(probabilities, p, random_value):

Your question is Top-p Nucleus Sampling Algorithm. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.