Implement weighted sampling without replacement
Company: Uber
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Implement in Python a function sample_k(items, weights, k) that returns k items without replacement with probability proportional to weight. Requirements: (a) single pass over N up to 1e8 (streaming), (b) handles extreme weights up to 1e300 without overflow/underflow, (c) reproducible with a seed, (d) O(k) memory and near-linear time, and (e) rejects nonpositive weights gracefully. Explain and justify your algorithm (e.g., Efraimidis–Spirakis weighted reservoir using keys w_i^(1/u_i)), prove unbiasedness, discuss numerical stability, and outline tests (goodness-of-fit, seed determinism, edge cases).
Quick Answer: This question evaluates a candidate's ability to design numerically stable, streaming weighted-sampling methods and tests competencies in randomized algorithms, probability, numerical analysis, and memory/time trade-offs.