Probabilistic Data Structures & Hashing Questions
Covers probabilistic data structures (e.g., Bloom filters, Count-Min Sketch, HyperLogLog, Cuckoo filters) and hashing techniques, including space-time trade-offs, false positive rates, distinct element estimation, and practical applications in databases, caches, streaming analytics, and network systems.
HardSystem Design
0 practiced
Design a hybrid cache invalidation and membership check system where Bloom filters reduce DB reads but the underlying cache supports deletions and TTLs. Describe how you will avoid stale-positive responses from Bloom filters (which might think a deleted key exists) and propose practical mechanisms such as counting filters, versioned filters/epochs, write-through invalidation, or TTL-aligned filter rotations. Analyze memory and latency trade-offs.
EasyTechnical
0 practiced
You operate a high-scale analytics pipeline receiving billions of events per day. A PM asks: when should we use HyperLogLog (approximate distinct) instead of maintaining exact distinct counts? Describe criteria you would consider (expected cardinality, memory cost, query SLA, mergeability, tolerance for error) and propose a recommended approach for tracking daily uniques.
HardTechnical
0 practiced
Case study: the CFO suggests replacing stored daily exact user lists with HyperLogLog sketches to cut storage costs. Prepare a concise cost-benefit analysis: estimate storage savings (show sample calculations), quantify expected error and business impact, list operational risks (misreporting, auditability), monitoring and validation strategy (A/B tests), and propose a phased rollout plan including rollback criteria.
HardTechnical
0 practiced
Propose an extension to Count-Min Sketch to support negative updates (decrements) while preserving bounded error guarantees. Outline the algorithm, error bounds, memory and CPU impacts, and limitations. Compare your design to Count Sketch (which supports signed updates via random ±1 signs) and discuss mergeability across partitions.
EasyTechnical
0 practiced
Compare cryptographic hash functions (e.g., SHA-256) and non-cryptographic hash functions (e.g., MurmurHash, xxHash) for data engineering tasks such as key partitioning, building probabilistic sketches, and security-sensitive operations. Discuss trade-offs: speed, collision properties, determinism across versions, and cases where one class is preferred over the other.
Unlock Full Question Bank
Get access to hundreds of Probabilistic Data Structures & Hashing interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.