← Thumbtack Interview Insights

Thumbtack·Data Scientist·Onsite - System Design / Architecture·Senior

Senior
May 2026

Summary

Thumbtack data scientist interview, system design round focused entirely on a single gnarly streaming problem. The question was dense and covered a lot of ground, felt more like a distributed systems eng interview than a DS one.

Questions Asked (1)

Q1

Design a streaming system that tracks new vs returning users per calendar month, emitting counts and percentage shares at month end. The system must handle up to 1B distinct users, 50K requests per second, 8 GB RAM, late-arriving events up to 7 days out, duplicates, and limited per-user state. Cover your data structures and memory footprints, exact vs approximate tradeoffs with error bounds under 0.5 percentage points, late event and watermarking strategy, deduplication, time and space complexity, and fault tolerance.

System DesignAlgorithms & Data StructuresTechnical Trade-offs
Author's notes

This one wrecked me a little.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a hybrid architecture that uses approximate data structures (e.g., HyperLogLog for distinct counts) to meet memory limits while achieving error bounds under 0.5 percentage points. Explain how to handle late events with watermarks and deduplication using per-user state, and discuss fault tolerance through checkpointing and replication.

Pro tip: Quantify memory and error trade-offs explicitly: for 1B users, a HyperLogLog with 2^14 registers uses ~16KB and gives ~0.81% error, but to get under 0.5 percentage points you might need 2^16 registers (~64KB) per month, which is still feasible. Also, mention that percentage share error can be bounded by combining HLL errors.

1. Clarify Requirements and Constraints

Restate the problem: track new vs returning users per calendar month, emit counts and percentage shares at month end. Confirm constraints: 1B distinct users, 50K RPS, 8GB RAM, late events up to 7 days, duplicates, limited per-user state. Ask about exact vs approximate tolerance and definition of 'new' (e.g., first-ever seen vs first in month).

2. Design Data Structures and Memory Footprint

Propose using HyperLogLog (HLL) for approximate distinct counts of new and returning users per month. For exact counts, consider a combination of Bloom filters for deduplication and counters, but note memory limits. Calculate memory: HLL with 2^16 registers uses ~64KB per month per set; for 12 months and two sets, ~1.5MB, well within 8GB. For deduplication, use a Bloom filter with 1B items and 1% false positive rate requires ~1.2GB, which is feasible.

3. Handle Late Events and Watermarking

Use event-time processing with watermarks to handle late events up to 7 days. Define a watermark strategy: allow lateness of 7 days, and trigger window emission at month end plus 7 days. Use a allowed lateness mechanism to update results if late events arrive. Discuss trade-off between latency and completeness.

4. Deduplication and Per-User State

Deduplicate events using a unique event ID or user ID + timestamp. Since per-user state is limited, use a Bloom filter to track seen user IDs for the month, with a false positive rate that doesn't significantly affect counts. For returning users, maintain a global Bloom filter of all users ever seen; new users are those not in the global filter. Update the global filter periodically.

5. Fault Tolerance and Complexity Analysis

Ensure fault tolerance via checkpointing of state (HLL registers, Bloom filters) to durable storage (e.g., S3) and replication. Discuss time complexity: O(1) per event for HLL and Bloom filter updates. Space complexity: O(2^p) for HLL and O(n) for Bloom filter. Mention that approximate results have error bounds: HLL error ~1.04/sqrt(2^p), so for p=16, error ~0.81%, but percentage share error can be computed via error propagation.

Key Points to Mention

  • HyperLogLog for distinct count approximation with error bounds under 0.5 percentage points (e.g., p=16 gives ~0.81% error, but can combine with exact counts for small cardinalities).
  • Bloom filters for deduplication and tracking new vs returning users, with memory calculation and false positive trade-offs.
  • Watermarking and allowed lateness (7 days) for late events, with triggers at month end + 7 days.
  • Memory footprint analysis: HLL and Bloom filter sizes within 8GB, considering 1B users and 50K RPS.
  • Fault tolerance via checkpointing and replication of state, and idempotent processing for duplicates.
  • Time and space complexity: O(1) per event, O(2^p) space for HLL, O(n) for Bloom filter, and error propagation for percentage shares.

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