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

SeniorPrefer not to say

Apr 2026

Summary

Dropbox software engineering interview focused on designing an in-memory key-value store from scratch. The question started simple but kept expanding into concurrency, eviction, and persistence territory, which I wasn't fully ready for.

Questions Asked (4)

Design and implement an in-memory key-value store with put, get, and delete operations.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

Started fine, hash map, O(1) average case, talked through collision handling and load factor resizing.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (e.g., expected operations, data types, concurrency, persistence) and then propose a simple design using a hash map with optional auxiliary structures for advanced features. Discuss trade-offs between simplicity and scalability, and outline how you would implement and test the solution.

Pro tip: Mention that you would start with a basic hash map implementation and then iterate based on requirements, showing that you prioritize working software over premature optimization. Also, highlight the importance of thread safety and how you would handle it (e.g., using locks or concurrent data structures).

1. Clarify Requirements

Ask questions to understand the scope: expected operations (put, get, delete), data types, concurrency needs, persistence, and performance requirements.

2. Propose a Basic Design

Suggest using a hash map (e.g., HashMap in Java, dict in Python) for O(1) average time complexity. Discuss potential need for additional structures for features like TTL or LRU eviction.

3. Discuss Trade-offs and Extensions

Compare hash map with other structures (e.g., balanced BST for ordered keys). Address concurrency (locks, concurrent hash map) and persistence (snapshots, write-ahead log).

4. Outline Implementation

Describe key methods: put (insert/update), get (retrieve), delete (remove). Mention error handling for missing keys and thread safety mechanisms.

5. Testing and Scalability

Explain how you would test (unit tests, stress tests) and scale (sharding, replication) if needed.

Key Points to Mention

Time complexity: O(1) average for put, get, delete with hash map.
Concurrency: use of locks, concurrent hash map, or read-write locks.
Memory management: handling collisions, resizing, and eviction policies (LRU, TTL).
Persistence: options like write-ahead logging or snapshots for durability.
Trade-offs: simplicity vs. features, memory vs. speed, consistency vs. availability.
Testing: unit tests for basic operations, concurrency tests, and performance benchmarks.

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

What data structure would you use under the hood, and how would your answer change if range queries were required?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This pivot caught me a bit flat.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the exact operations and constraints (e.g., insert, delete, lookup, range queries) before proposing a data structure. Then justify your choice with trade-offs (time/space complexity, implementation complexity) and explain how you would adapt it if range queries become a requirement.

Pro tip: Show awareness of real-world constraints like memory usage, concurrency, and persistence—especially relevant at Dropbox where scale and reliability matter. Mention that you'd validate the choice with benchmarks or profiling rather than relying solely on theoretical complexity.

1. Clarify requirements

Ask about the operations needed (insert, delete, lookup, range queries), data size, access patterns, and performance constraints. This ensures you don't over-engineer or miss a key requirement.

2. Propose a base data structure

For point queries, suggest a hash table for O(1) average lookup, or a balanced BST if ordering is needed. Explain why it fits the clarified requirements.

3. Adapt for range queries

If range queries are required, switch to a balanced BST (e.g., red-black tree) or a B-tree for ordered traversal. For more advanced needs, mention segment trees or Fenwick trees for efficient range aggregations.

4. Discuss trade-offs

Compare time/space complexity, implementation complexity, and suitability for the use case. For example, hash tables are faster for point lookups but cannot handle ranges; BSTs offer O(log n) for both but with higher constant factors.

5. Consider real-world factors

Mention concurrency, persistence, memory overhead, and whether the data fits in memory. At Dropbox, you might also consider distributed data structures or databases that support range queries natively.

Key Points to Mention

Hash table vs. balanced BST: O(1) vs. O(log n) for point queries, and inability vs. ability to handle range queries.
Balanced BSTs (e.g., red-black trees, AVL trees) maintain sorted order and support range queries in O(log n + k) where k is the number of results.
B-trees are optimized for disk-based storage and are used in databases; they support range queries efficiently.
Segment trees and Fenwick trees (BIT) are specialized for range queries with updates, offering O(log n) per operation.
Trade-offs: hash tables are simpler and faster for point lookups but require a separate structure for ranges; BSTs add overhead but provide ordering.
Real-world considerations: concurrency (e.g., lock-free structures), memory footprint, and persistence (e.g., using a database like RocksDB that uses LSM trees).

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

How would you make the key-value store thread-safe under concurrent reads and writes?

System DesignTechnical Trade-offs

Author's notes

Answered but felt reactive the whole time.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements: expected read/write ratio, consistency guarantees, and scale. Then propose a layered approach: use fine-grained locking (e.g., per-key locks) or lock-free data structures, and discuss trade-offs between simplicity and performance. Finally, mention advanced techniques like MVCC or sharding for scalability.

Pro tip: Emphasize that thread-safety is not just about locks; it's about minimizing contention and ensuring correctness under concurrency. Discuss how you would test and measure contention to validate your design.

1. Clarify Requirements

Ask about read/write ratio, consistency needs (strong vs. eventual), latency targets, and scale. This determines the appropriate synchronization strategy.

2. Choose a Synchronization Strategy

Propose options: coarse-grained locking (simple but low concurrency), fine-grained locking (per-key locks), lock-free using atomic operations, or MVCC. Explain trade-offs.

3. Address Contention and Scalability

Discuss how to reduce contention: sharding the store, using read-write locks, or partitioning keys. Mention that lock-free structures can improve throughput but increase complexity.

4. Ensure Correctness and Handle Edge Cases

Cover atomicity of compound operations, memory visibility (e.g., using volatile or memory barriers), and deadlock avoidance. Mention testing with stress tests and race detectors.

5. Evaluate Trade-offs and Propose a Solution

Summarize the chosen approach based on requirements, and discuss how it balances performance, simplicity, and correctness. Mention potential optimizations like read-copy-update (RCU).

Key Points to Mention

Fine-grained locking (e.g., per-key locks) to allow concurrent access to different keys.
Lock-free data structures using atomic operations (e.g., CAS) for high performance.
Read-write locks to allow multiple concurrent readers but exclusive writers.
Sharding or partitioning the key-value store to reduce lock contention.
Memory consistency and visibility issues (e.g., using volatile, memory barriers).
Testing strategies: stress tests, race detectors, and performance profiling.

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

How would you extend the store to support TTL-based key expiration, LRU or LFU eviction, and optional persistence to disk?

System DesignTechnical Trade-offs

Author's notes

This came at the end and felt like a stress test to see how far my thinking went.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and constraints (e.g., expected scale, consistency needs, latency targets). Then propose a modular design that separates concerns: TTL management, eviction policies, and persistence, explaining how they interact. Finally, discuss trade-offs and potential optimizations for each component.

Pro tip: Emphasize that TTL and eviction policies often work together—expired items should be removed lazily or actively, and eviction should consider TTL to avoid evicting non-expired items prematurely. Also, mention that persistence can be optional and pluggable to avoid over-engineering.

1. Clarify Requirements and Constraints

Ask about expected data size, read/write patterns, latency requirements, and durability needs to tailor the design.

2. Design TTL-Based Expiration

Propose storing expiration timestamps with each key and using lazy deletion on access plus a background sweeper for active cleanup.

3. Implement Eviction Policies (LRU/LFU)

Choose data structures (e.g., doubly linked list + hash map for LRU, frequency counts for LFU) and integrate with TTL to prioritize eviction of expired or soon-to-expire items.

4. Add Optional Persistence

Design a pluggable persistence layer (e.g., write-ahead log or snapshotting) that can be enabled or disabled, ensuring it doesn't block main operations.

5. Discuss Trade-offs and Optimizations

Compare approaches (e.g., lazy vs. active expiration, LRU vs. LFU, persistence overhead) and suggest monitoring and tuning strategies.

Key Points to Mention

TTL implementation: lazy expiration on read vs. active background sweeper, and handling of expired keys during eviction.
Eviction data structures: LRU using doubly linked list + hash map, LFU using frequency buckets or min-heap, and their time/space complexities.
Integration of TTL and eviction: eviction should consider TTL to avoid removing non-expired items; expired items can be evicted first.
Persistence options: write-ahead log (WAL) for durability, snapshotting for faster recovery, and trade-offs between performance and durability.
Concurrency and thread-safety: locking strategies (e.g., fine-grained locks, read-write locks) to handle concurrent access during expiration and eviction.
Trade-offs: memory overhead vs. accuracy of eviction, latency impact of persistence, and complexity of combining policies.

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