FastPrepConstant-Time Weighted Pick with an Alias Table
Problems/Constant-Time Weighted Pick with an Alias Table

Constant-Time Weighted Pick with an Alias Table

Etched logoEtched● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: In an Etched coding interview for a machine learning engineer role, the task was the classic weighted random index pick, with one twist: picking had to run in constant time, and a binary search over prefix sums was not accepted. The report says the interviewer expected the alias method, a table with at most two outcomes per slot, where a uniformly chosen slot and a precomputed threshold decide the result.

The report gives no input format, limits or examples, and a truly random pick cannot be checked. Our practice choices: the random numbers arrive as recorded draws (a column and a ticket below the weight total); the table is built in whole tickets, with weights[i] times n tickets per index and S per column; the two worklists are first-in, first-out queues filled in index order; an index with exactly S tickets starts in the large queue; after giving tickets away, an index goes to the back of the small queue if it has fewer than S left and to the back of the large queue otherwise; and a ticket below the column's keep value picks the column, otherwise its alias. The limits and examples are ours.

The judged task matches the report at about 75%.

You are given positive integer weights weights. A random pick should return index i with probability weights[i] / S, where S is the sum of all weights, and each pick must take constant time. Build an alias table once, then answer each pick with one table lookup.

Let n = weights.length. Think of n columns, each holding exactly S tickets. Index i owns units[i] = weights[i] · n tickets in total, so all indices together own n · S tickets, exactly enough to fill every column. Each column c ends up with two numbers: keep[c], the number of its tickets that belong to index c, and alias[c], the index that owns the other S - keep[c] tickets.

Build the table with two first-in, first-out queues:

  1. Go through the indices in increasing order. Put index i at the back of Small if units[i] < S, and at the back of Large otherwise (so an index with exactly S units starts in Large).
  2. While both queues are non-empty: remove s from the front of Small and l from the front of Large. Set keep[s] = units[s] and alias[s] = l. Index l fills the rest of column s, so subtract S - units[s] from units[l]. Then put l at the back of Small if units[l] < S, or at the back of Large otherwise.
  3. Every index still in either queue gets keep[i] = S and alias[i] = i.

A real random pick chooses a column uniformly and then a ticket uniformly. So that answers can be checked, the random numbers are given to you: draws[j] = [c, r] names column c and ticket r, with 0 <= r < S. The pick is c if r < keep[c], and alias[c] otherwise.

Return the picked index for every draw, in order.

Function

pickIndices(weights: int[], draws: int[][]) → int[]

Examples

Example 1

weights = [1,3]draws = [[0,0],[0,1],[0,2],[0,3],[1,0],[1,3]]return = [0,0,1,1,1,1]

Here n = 2 and S = 4, so index 0 has 1 · 2 = 2 units and index 1 has 3 · 2 = 6 units, and each column holds 4 units.

  • Small = [0] and Large = [1]. Pair 0 with 1: keep[0] = 2, alias[0] = 1, and index 1 gives away 4 - 2 = 2 units, leaving 4. That is not less than 4, so 1 goes back to Large.
  • Small is now empty, so index 1 is left over: keep[1] = 4, alias[1] = 1.
  • Column 0: tickets 0 and 1 are below keep[0] = 2 and pick 0; tickets 2 and 3 pick alias[0] = 1. Column 1 always picks 1.
  • Over all 8 (column, ticket) pairs, index 0 is picked 2 times and index 1 is picked 6 times, which is the ratio 1 : 3.

Example 2

weights = [2,1,1,4]draws = [[1,3],[1,4],[2,5],[0,3],[0,6],[3,7]]return = [1,0,3,0,3,3]

Here n = 4 and S = 8. The units are [8, 4, 4, 16], so Small = [1, 2] and Large = [0, 3]. Index 0 has exactly 8 units, so it starts in Large.

  • Pair 1 with 0: keep[1] = 4, alias[1] = 0. Index 0 drops to 8 - 4 = 4, which is less than 8, so it moves to the back of Small: Small = [2, 0], Large = [3].
  • Pair 2 with 3: keep[2] = 4, alias[2] = 3. Index 3 drops to 12 and goes back to Large.
  • Pair 0 with 3: keep[0] = 4, alias[0] = 3. Index 3 drops to 8 and goes back to Large.
  • Small is empty, so keep[3] = 8, alias[3] = 3. The table is keep = [4, 4, 4, 8], alias = [3, 0, 3, 3].
  • The draws pick: [1, 3] → 1 (3 < 4), [1, 4] → 0, [2, 5] → 3, [0, 3] → 0, [0, 6] → 3, [3, 7] → 3.

Example 3

weights = [5]draws = [[0,0],[0,4]]return = [0,0]

With one index, S = 5 and index 0 has exactly 5 units. Small is empty, so keep[0] = 5 and every ticket from 0 to 4 picks index 0.

Constraints

  • 1 <= weights.length <= 10^4
  • 1 <= weights[i] <= 10^5
  • 1 <= draws.length <= 3000
  • draws[j].length == 2
  • 0 <= draws[j][0] < weights.length
  • 0 <= draws[j][1] < S, where S is the sum of weights

More Etched problems

  • DMA Stream DistributionPHONE SCREEN
  • Periodic Event LoopPHONE SCREEN
See Etched hiring insights
Saved
class Solution {
    public int[] pickIndices(int[] weights, int[][] draws) {
        // Write your code here.
    }
}
Checking account…