Coding questions · Stripe

Implement streaming per-user reservoir sampling

This question evaluates a candidate's competency in streaming algorithms, per-user reservoir sampling, probabilistic reasoning and proof of correctness, concurrent/distributed merging, and engineering trade-offs for memory and amortized update efficiency.

Design and code (in Python) a streaming algorithm that ingests an unbounded event stream of tuples (user_id, event_time, event_type) and maintains, for each user, at most M events that are a uniform random sample without replacement of all events seen so far for that user. Requirements: (1) Use reservoir sampling so each event has equal inclusion probability; prove correctness. (2) Achieve amortized O(1) update per event and O(U*M) memory, where U is number of active users. (3) Support concurrent shards with deterministic merging given a random seed. (4) Provide unit tests that verify marginal inclusion probabilities and that increasing M reduces variance of feature estimates derived from the reservoir. (5) As an extension, maintain a real-time top-K users by event count using a size-K min-heap that supports increment/decrement when late events are revoked; state time and space complexities.

Per-User Reservoir Sampling

Examples

Example 1

Input: ([("u1",1,"a"),("u1",2,"b"),("u1",3,"c"),("u2",1,"x")], 2, 42)
Output: {'u1': [[1, 'a'], [2, 'b']], 'u2': [[1, 'x']]}

Explanation: Reservoir keeps at most M events per user with seeded randomness.

Example 2

Input: ([], 3, 1)
Output: {}

Explanation: Empty stream has no samples.

Hints

Clarify edge cases before coding.
Keep the return value deterministic.