A browser extension streams log lines and must keep one random line to attach to bug reports, without storing them all. It uses reservoir sampling with a reservoir of one, and takes random numbers from randoms for repeatable tests.
Keep the first line. Then for the line at index i (with i >= 1), it is line number seen = i + 1; take r = randoms[i - 1], and if Math.floor(r * seen) === 0, keep this line instead. Write pickLine(lines, randoms) that returns the kept line, or null if there are no lines.
Input: lines = ["boot","fetch","render","idle"], randoms = [0.4,0.2,0.9] Output: "render"
Line 2: floor(0.4 * 2) = 0, keep fetch. Line 3: floor(0.2 * 3) = 0, keep render. Line 4: floor(0.9 * 4) = 3, not 0, so render stays.
Input: lines = ["only"], randoms = [] Output: "only"
The first line is always kept, and there are no others.
0 <= lines.length <= 10^5randoms.length === Math.max(0, lines.length - 1)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 #90 Pick One Log Line Fairly. 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.