A telemetry client keeps a fair random sample of k events from a long stream. The first k events fill the reservoir in order. For each later event at index i (so i >= k), take the next number r from randoms, set j = Math.floor(r * (i + 1)), and if j < k, replace reservoir[j] with this event.
Write sampleEvents(stream, k, randoms) that returns the reservoir after the whole stream. If the stream has fewer than k events, return all of them.
Input: stream = ["a","b","c","d","e"], k = 2, randoms = [0.5,0.9,0.2] Output: ["a","e"]
c: j = floor(0.5 * 3) = 1, replace slot 1. d: j = 3, skip. e: j = floor(0.2 * 5) = 1, replace slot 1 again.
Input: stream = ["x","y"], k = 3, randoms = [] Output: ["x","y"]
Fewer events than slots, so all are kept.
0 <= stream.length <= 10^51 <= k <= 1000randoms.length === Math.max(0, stream.length - k)0 <= randoms[i] < 1Run 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).
I'm here to help with #91 Sample K Events From a Stream. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.