Coinbase·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026Remote

Summary

Coinbase backend interview that went deep on key-value store design. The core problem was extending a simple store/read API with a scan operation, and the whole conversation ended up being about data structure tradeoffs rather than just writing code.

Questions Asked (1)

You have an in-memory key-value store with store and read operations. Add a scan operation that returns all entries matching either a key prefix or a low/high range, sorted by key. What data structure do you pick and why?

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

I went with a sorted map pretty quickly and explained that a plain hash map kills you on range queries since you lose ordering entirely.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the requirements and constraints (e.g., data size, concurrency, persistence) before proposing a data structure. Compare balanced BSTs and skip lists for ordered operations, then justify your choice based on expected workload and system needs. Discuss how to support both prefix and range scans efficiently, and mention trade-offs.

Pro tip: Emphasize that the choice depends on read/write ratio and concurrency requirements; showing awareness of these factors demonstrates senior-level thinking. Also, mention that in-memory stores often use a combination of data structures (e.g., hash map + skip list) to optimize different operations.

1. Clarify Requirements

Ask about data size, read/write patterns, concurrency needs, and whether persistence or replication is required. This ensures your solution aligns with the actual use case.

2. Identify Core Operations

Recognize that store and read are typically O(1) with a hash map, but scan requires ordered traversal. So you need a data structure that maintains order while supporting efficient inserts and lookups.

3. Evaluate Data Structures

Compare balanced BSTs (e.g., red-black tree) and skip lists for ordered operations. Consider their time complexities, implementation complexity, concurrency support, and memory overhead.

4. Propose a Solution

Recommend a skip list or balanced BST for the ordered index, possibly combined with a hash map for O(1) point reads. Explain how to implement prefix and range scans using the ordered structure.

5. Discuss Trade-offs and Optimizations

Mention trade-offs like memory usage, concurrency (e.g., lock-free skip lists), and performance under different workloads. Suggest optimizations like caching or partitioning if needed.

Key Points to Mention

Time complexity: O(log n) for insert, delete, and range scans with balanced BST or skip list.
Skip list advantages: simpler concurrent implementation, probabilistic balancing, and good cache performance.
Balanced BST advantages: deterministic O(log n) worst-case, but more complex to implement lock-free.
Hybrid approach: combine hash map for O(1) point reads with an ordered structure for scans.
Prefix scan implementation: find the first key >= prefix, then iterate until keys no longer match the prefix.
Range scan implementation: find the node with key >= low, then iterate until key > high.
Concurrency considerations: use fine-grained locking or lock-free techniques for scalability.
Memory overhead: skip lists may use more memory due to multiple pointers per node.

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