← Dropbox Interview Insights

Dropbox·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say
May 2026

Summary

Dropbox system design round, one meaty question about building a key-value store with hit counting baked in. Took longer than I expected to get through all the follow-ups and I'm not totally sure I nailed the scaling piece.

Questions Asked (1)

Q1

Design a key-value store that tracks how many times each key is accessed, supports querying a key's hit count, and can return the top-N most-accessed keys. Discuss data structures, concurrency handling, time-window variants, and horizontal scaling.

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

Started with the obvious hashmap for key-to-count, then they pushed me on top-N and I went straight to a min-heap of size N which felt right.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (e.g., read/write ratio, consistency, latency, scale) and then propose a layered design: a hash map for key-value storage with counters, a min-heap or sorted structure for top-N queries, and concurrency control via sharding and locks. Discuss time-window variants using sliding windows or bucketed counters, and horizontal scaling through consistent hashing and distributed aggregation.

Pro tip: Emphasize the trade-offs between exact and approximate top-N (e.g., using Count-Min Sketch) and how to handle hot keys without sacrificing performance. Also, mention that Dropbox's scale likely requires a distributed, eventually consistent system, so discuss how to reconcile counts across nodes.

1. Clarify Requirements and Constraints

Ask about expected scale (QPS, number of keys), read/write ratio, latency requirements, consistency needs, and whether top-N is global or per time window. This shapes data structure and scaling choices.

2. Design Core Data Structures

Propose a hash map for O(1) key access and hit count updates, and a min-heap or balanced BST for maintaining top-N efficiently. Discuss trade-offs between exact and approximate methods (e.g., Count-Min Sketch) for high-cardinality scenarios.

3. Address Concurrency and Consistency

Explain how to handle concurrent updates using fine-grained locking (e.g., per-key locks), lock-free structures, or sharding. Discuss consistency models (strong vs. eventual) and how they affect top-N accuracy.

4. Support Time-Window Variants

Describe sliding window or bucketed counters (e.g., per-minute buckets) to compute top-N over recent intervals. Discuss memory trade-offs and how to expire old data.

5. Plan for Horizontal Scaling

Propose sharding by key using consistent hashing, with each shard maintaining local counts and top-N. For global top-N, aggregate results from shards, possibly using a hierarchical or streaming approach to reduce network overhead.

Key Points to Mention

  • Use of hash map for O(1) access and counter updates, with a min-heap for top-N queries (O(log N) update, O(1) retrieval).
  • Concurrency control: sharding by key to reduce contention, per-key locks or atomic operations, and lock-free data structures for high throughput.
  • Time-window variants: sliding window with bucketed counters (e.g., per-minute) to support queries like 'top-N in last hour', and trade-offs in memory and accuracy.
  • Horizontal scaling: consistent hashing to distribute keys, local top-N per shard, and a merge step for global top-N; consider approximate algorithms (Count-Min Sketch) for scalability.
  • Trade-offs: exact vs. approximate counts, strong vs. eventual consistency, and latency vs. accuracy for top-N queries.
  • Handling hot keys: techniques like key splitting, local aggregation, or caching to avoid bottlenecks.

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