Capital One·Data Scientist·Onsite - System Design / Architecture·Senior

Senior

May 2026

Summary

Capital One data scientist interview that went deep fast. One system design question that touched streaming pipelines, probabilistic data structures, and complexity guarantees all at once. Not a vibe check.

Questions Asked (1)

You're receiving an unbounded stream of events, each with an event time, user ID, and category. Events can arrive up to 48 hours late and are out of order. Design an API with an ingest method and a query method that returns, for each hour in a given window, the count of unique users and the 95th percentile of per-user interarrival delay based on event time. Late arrivals must retroactively correct prior aggregates, ingest must be amortized O(log n), memory must be bounded relative to the correction window and active categories, and queries over H hours must run in O(H + C·log W). Walk through your data structures, how you handle clock skew and deduplication, and write test cases that cover late data arriving right at the 48-hour boundary.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

This was a lot to hold in your head at once.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a windowed, bucketed architecture that separates ingest and query paths. Use a time-bucketed store (e.g., per-hour buckets) with per-bucket sketches for unique users and interarrival delay quantiles, and a correction buffer for late events. Explain how you handle out-of-order and late data via watermarking and retroactive updates, and how you bound memory by limiting the correction window and active categories.

Pro tip: Emphasize the trade-off between accuracy and memory: use approximate sketches (HLL, t-digest) for bounded memory, but discuss how to handle exact counts for small cardinalities or when needed. Also, mention that you'd validate the 48-hour boundary with tests that simulate clock skew and late arrivals.

1. Clarify requirements and constraints

Ask about expected event rate, number of categories, query patterns, and acceptable error margins. Confirm that 'unique users' can be approximate and that '95th percentile' can be approximate.

2. Design ingest path with bucketing and sketches

Ingest events into per-hour buckets based on event time. For each bucket and category, maintain a HyperLogLog for unique users and a t-digest for interarrival delays. Use a hash set for deduplication within the correction window.

3. Handle late data and retroactive corrections

Maintain a watermark to track the latest event time seen. For events older than the watermark but within 48 hours, update the corresponding bucket's sketches and mark the bucket as dirty. For events older than 48 hours, either drop or route to a cold path.

4. Design query path with efficient aggregation

For a query over H hours, iterate over the H hourly buckets, merge the sketches per category, and compute the final aggregates. Use a segment tree or Fenwick tree over buckets to allow O(log W) updates and O(H + C log W) queries.

5. Address clock skew, deduplication, and memory bounds

Use event time for bucketing and a watermark based on processing time to handle skew. Deduplicate using a bounded LRU cache of event IDs within the correction window. Bound memory by limiting the number of active categories and the correction window size.

Key Points to Mention

Use of approximate data structures (HyperLogLog for unique users, t-digest for quantiles) to achieve bounded memory and amortized O(log n) ingest.
Time-bucketed storage with per-bucket sketches and a segment tree for efficient range queries.
Watermarking and handling of out-of-order events, including retroactive updates to prior aggregates.
Deduplication strategy using event IDs and a bounded cache to handle duplicates within the correction window.
Memory bounds: limit active categories and correction window, and use sketches that scale with cardinality.
Test cases: simulate events arriving exactly at 48-hour boundary, clock skew, and out-of-order arrivals to verify correctness and performance.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.