Skip to the code
cf.
+50 XP

#92 Weighted Sample From a Stream

hard

An ad server streams candidate ads, each with a positive whole-number weight in weights, and must pick k of them so heavier ads are more likely to be picked. It uses weighted reservoir sampling: ad i gets the key randoms[i] ** (1 / weights[i]), and the sample is the k ads with the largest keys.

Write weightedSample(items, weights, k, randoms) that returns the picked items ordered from largest key to smallest. If there are fewer than k items, return all of them in that order. Keep at most k items in memory while you scan.

Example 1

Input: items = ["a","b","c","d"], weights = [1,4,1,2], k = 2, randoms = [0.6,0.6,0.6,0.6]
Output: ["b","d"]

With equal random numbers, weight decides: the keys are 0.6, about 0.88, 0.6, and about 0.77.

Example 2

Input: items = ["a","b","c","d"], weights = [1,4,1,2], k = 2, randoms = [0.9,0.5,0.95,0.3]
Output: ["c","a"]

b is heavier, but its key 0.5 ** 0.25 (about 0.84) is still below c (0.95) and a (0.9).

Constraints

  • 0 <= items.length <= 10^5
  • 1 <= weights[i] <= 100
  • 1 <= k <= 100
  • 0 < randoms[i] < 1
  • No two keys are equal in the tests.
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).