Implement streaming CTR with deduplication
Company: Roblox
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a Python function to compute streaming, per-campaign CTR over a sliding 24-hour window with click de-duplication and late-arriving events.
Requirements:
- Input: two iterators of dicts sorted non-decreasing by ts (ISO 8601 strings):
impressions: {"imp_id", "campaign_id", "ts"}
clicks: {"click_id", "imp_id", "campaign_id", "ts"}
- Dedup: count at most one click per imp_id (keep earliest click). Ignore clicks whose imp_id was never seen.
- Sliding window: maintain CTR for each campaign over the last 24 hours at every new event. Late events may arrive up to 10 minutes late; include them if they fall within the 24-hour window based on their ts.
- Performance: O(log n) amortized updates per event, memory proportional to events within the last 24 hours. Provide big-O justification.
- Output: an iterator of tuples (ts, campaign_id, impressions_in_window, dedup_clicks_in_window, ctr_in_window) emitted whenever the metric changes for that campaign.
- Edge cases: multiple clicks referencing same imp_id, clock skew between streams, and daylight saving transitions.
Provide a brief explanation of your data structures (e.g., heaps/queues + hash maps) and how you handle late events and expirations.
Quick Answer: This question evaluates streaming data-processing and algorithmic design skills, specifically time-windowed aggregation, click deduplication, late-event handling, state management, and selection of data structures for per-campaign CTR computation.
You are computing per-campaign click-through rate (CTR) for an ad system. Given a list of impression events and a list of click events, compute the CTR for each campaign over the trailing `window_hours` window ending at a query timestamp `query_ts`.
Each impression is a dict `{"imp_id", "campaign_id", "ts"}` and each click is a dict `{"click_id", "imp_id", "campaign_id", "ts"}`, where `ts` is an ISO 8601 timestamp string.
Rules:
- An event is in the window if `window_start < ts <= query_ts`, where `window_start = query_ts - window_hours`.
- Deduplicate clicks: count at most ONE click per `imp_id`, keeping the EARLIEST click. Whether a click is in the window is decided by that earliest click's timestamp.
- Ignore any click whose `imp_id` never appeared in the impressions list.
- CTR = dedup_clicks_in_window / impressions_in_window, rounded to 4 decimals (0.0 when there are no impressions).
Return a list of tuples `(campaign_id, impressions_in_window, dedup_clicks_in_window, ctr_in_window)`, sorted ascending by `campaign_id`. Include a campaign if it has at least one impression OR one dedup click in the window.
Data-structure note for the discussion: a production streaming version would keep, per campaign, a monotonic deque (or min-heap keyed by ts) of in-window impressions and dedup clicks plus a hash map `imp_id -> earliest_click_ts` for O(log n) amortized expiry/insertion; this offline version applies the same window/dedup logic in one pass.
Constraints
- Timestamps are valid ISO 8601 strings, sorted non-decreasing by ts within each stream.
- An event is in-window iff window_start < ts <= query_ts.
- At most one click is counted per imp_id (earliest wins).
- Clicks whose imp_id never appears in impressions are ignored.
- CTR is rounded to 4 decimal places; 0.0 when impressions_in_window == 0.
- Result is sorted ascending by campaign_id.
Examples
Input: ([{"imp_id": "i1", "campaign_id": "A", "ts": "2026-01-01T10:00:00+00:00"}, {"imp_id": "i2", "campaign_id": "A", "ts": "2026-01-01T11:00:00+00:00"}, {"imp_id": "i3", "campaign_id": "B", "ts": "2026-01-01T12:00:00+00:00"}], [{"click_id": "c1", "imp_id": "i1", "campaign_id": "A", "ts": "2026-01-01T10:05:00+00:00"}, {"click_id": "c2", "imp_id": "i1", "campaign_id": "A", "ts": "2026-01-01T10:06:00+00:00"}], "2026-01-01T13:00:00+00:00")
Expected Output: [('A', 2, 1, 0.5), ('B', 1, 0, 0.0)]
Explanation: Campaign A has 2 impressions and 2 clicks on i1; dedup keeps the earliest click only -> 1 click, CTR 1/2 = 0.5. Campaign B has 1 impression, no clicks -> CTR 0.0. All events fall within the 24h window ending 13:00.
Input: ([], [], "2026-01-01T13:00:00+00:00")
Expected Output: []
Explanation: No events at all -> empty result.
Hints
- Build a map imp_id -> campaign_id from ALL impressions so you can validate and attribute clicks, but only count impressions whose ts falls in the window.
- Deduplicate clicks by tracking the earliest timestamp per imp_id BEFORE applying the window filter to clicks.
- Decide a click's window membership by its earliest deduped timestamp, not by any later duplicate.
- A campaign appears in the output if it has any in-window impression OR any in-window dedup click; guard division by zero for CTR.