FastPrepTop-K Sampler
Problems/Top-K Sampler

Top-K Sampler

Scale AI logoScale AI● MediumINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A candidate for the Scale AI Machine Learning Research Engineering Intern role (Summer 2025) had two ML coding tasks in the first live round. One of them was building a top-k sampler for picking tokens.

The report does not give an input format, a tie rule, or how randomness is supplied. Here you get the logits, k, and the random draws. Equal logits rank by smaller index, the kept tokens are walked from highest logit to lowest, and there is no temperature.

Our version is about 70% the same as the reported question.

A language model gives every token in its vocabulary a score called a logit. A top-k sampler picks the next token in two steps. First it keeps only the k tokens with the highest logits. Then it picks one of those tokens at random, using softmax probabilities.

You are given logits, where logits[i] is the logit of token i, the number k, and a list of random numbers draws. Each draw is a uniform random number from 0 up to, but not including, 1. The draws are given to you so the answer is fixed. Do not make your own random numbers.

Return an array with one token index for each draw, in the same order as draws.

How a draw picks a token

  1. Rank all tokens by logit, from highest to lowest. When two logits are equal, the smaller index ranks first. Keep the first k tokens of this ranking.
  2. Give each kept token i the weight exp(logits[i]). Its probability is its weight divided by the sum of the weights of all kept tokens. A token that was not kept has probability 0.
  3. Go through the kept tokens in rank order and keep a running total of their probabilities. Return the first token whose running total is greater than the draw.

Every draw uses the same kept tokens and the same probabilities. There is no temperature setting.

Function

sampleTopK(logits: double[], k: int, draws: double[]) → int[]

Examples

Example 1

logits = [2.0,1.0,0.1,3.0]k = 2draws = [0.1,0.8]return = [3,0]

Ranked by logit, the tokens are 3 (3.0), 0 (2.0), 1 (1.0) and 2 (0.1). With k = 2, tokens 3 and 0 are kept.

Their weights are exp(3) and exp(2), so their probabilities are about 0.731 and 0.269. The running totals are about 0.731 and 1.0.

  • Draw 0.1: the first running total, 0.731, is already greater, so the answer is token 3.
  • Draw 0.8: 0.731 is not greater than 0.8, but 1.0 is, so the answer is token 0.

Example 2

logits = [1.0,1.0,1.0]k = 2draws = [0.25,0.75,0.4999]return = [0,1,0]

All three logits are equal, so the smaller indices rank first and tokens 0 and 1 are kept. Token 2 is never picked.

Each kept token has probability 0.5, so the running totals are 0.5 and 1.0. Draws 0.25 and 0.4999 are below 0.5 and pick token 0. Draw 0.75 picks token 1.

Example 3

logits = [0.0,-1.0,2.0]k = 3draws = [0.5,0.95,0.99]return = [2,0,1]

Here k equals the number of tokens, so every token is kept. In rank order they are 2, 0 and 1.

The weights are exp(2), exp(0) and exp(-1), about 7.389, 1 and 0.368, with a sum of about 8.757. The probabilities are about 0.844, 0.114 and 0.042, so the running totals are about 0.844, 0.958 and 1.0.

  • Draw 0.5 picks token 2.
  • Draw 0.95 is not below 0.844 but is below 0.958, so it picks token 0.
  • Draw 0.99 picks token 1.

Constraints

  • 1 <= logits.length <= 10^5
  • -100 <= logits[i] <= 100
  • 1 <= k <= logits.length
  • 1 <= draws.length <= 1000
  • 0 <= draws[j] < 1
  • Every draw differs by at least 10^-6 from every running total in step 3, so rounding never changes which token is picked.

More Scale AI Phone Screen questions

  • Four-Player Trick-Taking Card Game SimulationOA · PHONE SCREEN · Seen Aug 2026
  • Task Processor: Dependencies and DeadlinesPHONE SCREEN · Seen Aug 2026
  • Best Poker Category with a JokerPHONE SCREEN · ONSITE INTERVIEW · Seen Jun 2026
  • Free Time for Every Meeting RoomPHONE SCREEN · Seen Apr 2026
  • Free Windows Between Busy IntervalsOA · PHONE SCREEN · Seen Apr 2026
  • Order Queries by Shortest Processing TimePHONE SCREEN · Seen Apr 2026
  • Party Time by Town and Quiet Gaps by CityPHONE SCREEN · Seen Jan 2026
  • Party Windows and Dead Zone TimePHONE SCREEN · Seen Oct 2025
  • Overlap Duration of Two Time IntervalsPHONE SCREEN · Seen Jun 2025
  • Multi-Head Attention BlockPHONE SCREEN · Seen Mar 2025

Similar questions at other companies

  • Retrieve Vectors by Cosine SimilarityHarvey · ONSITE INTERVIEWHarvey interview questions
  • Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
  • Integers With Multiple Sum of Two CubesCharta Health · PHONE SCREEN · ONSITE INTERVIEWCharta Health interview questions
  • Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
  • Streaming Median of Trade PricesXantium · PHONE SCREEN
  • Apartment Housemate PreferencesGoogle · PHONE SCREENGoogle interview questions
  • Top K Pins with Insert and QueryPinterest · PHONE SCREENPinterest interview questions
  • Top K Movies by Play Count from CSV DataTubi · PHONE SCREEN
  • Alert Engine with a Repeat IntervalChronosphere · PHONE SCREEN
  • Adaptive Calibration ErrorOpenAI · PHONE SCREENOpenAI interview questions

Interview reports that mention this question

  • Scale AI ML Research Engineering Intern Interviews: 1 Experience

Scale AI interview experiences

  • Scale AI Forward Deployed Engineer Debugging Round: 1 Experience
  • Scale AI SWE Intern Debugging Interview: 9 Experiences
  • Scale AI New Grad SWE and MLE Question Bank
  • Scale AI New Grad SWE Poker Screen and Onsite: 1 Experience
  • Scale AI New Grad SWE OA Questions: 1 Experience
All Scale AI interview questionsSee Scale AI hiring insights
Saved
class Solution {
    public int[] sampleTopK(double[] logits, int k, double[] draws) {
        // Write your code here.
    }
}
Checking account…