Databricks·Software Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Databricks SWE interview with a system design coding problem that blends data structures with metrics tracking. The problem looked like a simple key-value store until the QPS window query came in and things got interesting fast.

Questions Asked (1)

Design an in-memory key-value store that supports PUT and DELETE operations, and can also return the average queries per second over a variable-length recent time window ending at a given timestamp.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

The key-value part was fine, I knocked that out pretty quick.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (e.g., expected scale, concurrency, time window semantics) and then propose a design that separates the key-value store (using a hash map) from the query rate tracking (using a time-series data structure like a ring buffer or balanced BST). Discuss trade-offs between different approaches for tracking queries per second, such as fixed-size buckets vs. sliding window, and how to handle variable-length windows efficiently.

Pro tip: Mention that you would use a ring buffer or a balanced binary search tree to store per-second query counts, enabling O(log n) or O(1) average time for window queries, and discuss how to handle out-of-order timestamps or clock skew.

1. Clarify Requirements

Ask about expected throughput, latency, concurrency, window size limits, and whether timestamps are monotonic. Confirm if the average is over queries per second or total queries in the window.

2. Design Key-Value Store

Propose an in-memory hash map for PUT and DELETE, with thread-safety considerations (e.g., concurrent hash map or locking). Discuss handling of large keys/values and memory management.

3. Track Queries Per Second

Design a data structure to record query counts per second. Options: circular buffer for fixed max window, or a balanced BST (e.g., TreeMap) for variable windows. Explain how to update counts on each query and compute average over a window.

4. Compute Average Over Window

For a given end timestamp and window length, sum the query counts in the window and divide by the number of seconds. Discuss efficient range sum queries using prefix sums or tree traversal.

5. Discuss Trade-offs and Optimizations

Compare approaches: fixed-size ring buffer (O(1) update, O(window) query) vs. balanced BST (O(log n) update, O(log n) query). Mention concurrency, memory overhead, and handling of out-of-order timestamps.

Key Points to Mention

Use a hash map for the key-value store with thread-safe operations.
Track queries per second using a time-series data structure like a ring buffer or balanced BST.
For variable-length windows, support efficient range sum queries (e.g., via prefix sums or tree aggregation).
Discuss trade-offs between fixed-size and dynamic window approaches in terms of time/space complexity.
Address concurrency and synchronization for both the store and the query tracker.
Consider edge cases: empty window, timestamps outside range, and clock skew.

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