Databricks·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

Databricks SWE interview with a system design coding problem that looked simple on the surface but had enough moving parts to keep you busy for the full session. The core challenge was building a key-value store with sliding window hit tracking, and the design decisions around expiry strategy were where things got interesting.

Questions Asked (1)

Design and implement an in-memory key-value store that supports put, get, delete, and a getHits operation that returns the number of get calls on a key within a sliding 5-minute window ending at a given timestamp.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I started with the hash map part no problem, but the sliding window hit tracking is where I got tangled.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements: is the timestamp provided with each operation or is it the current time? Then propose a design using a hash map for key-value storage and a per-key time-ordered structure (e.g., deque or circular buffer) to track get timestamps within the sliding window. Discuss trade-offs between memory usage, time complexity, and concurrency, and consider optimizations like lazy deletion or bucketing for high-throughput scenarios.

Pro tip: Mention that you would use a monotonic clock or assume timestamps are non-decreasing to simplify the sliding window logic, and highlight that getHits should be O(1) or O(log n) by evicting expired timestamps lazily.

1. Clarify requirements and constraints

Ask whether timestamps are provided per operation or use system time, whether keys can expire, and expected scale (QPS, memory). Confirm that getHits returns the count of get calls for a key in the last 5 minutes ending at the given timestamp.

2. Design core data structures

Use a hash map to store key-value pairs for put/get/delete. For getHits, maintain a per-key deque (or circular buffer) of timestamps of get calls, or use a bucketed approach (e.g., 1-second buckets) to reduce memory.

3. Implement sliding window logic

On each get, record the timestamp. On getHits, remove timestamps older than (current_timestamp - 300 seconds) from the front of the deque, then return the size. Ensure operations are efficient and handle out-of-order timestamps if necessary.

4. Analyze trade-offs and optimizations

Discuss time/space complexity: put/get/delete O(1), getHits O(k) where k is number of gets in window (amortized O(1) with lazy eviction). Consider bucketing to bound memory, and concurrency using locks or sharding.

5. Test and handle edge cases

Test with empty keys, multiple gets at same timestamp, timestamps far apart, and high concurrency. Ensure delete removes both value and hit history, and that getHits works even if no gets occurred.

Key Points to Mention

Use a hash map for O(1) key-value operations.
Per-key deque or circular buffer to store get timestamps for sliding window.
Lazy eviction of expired timestamps on getHits to achieve amortized O(1).
Bucketing (e.g., 1-second granularity) to reduce memory overhead for high-frequency gets.
Concurrency considerations: thread-safe data structures or locking per key.
Trade-off between exact counting and approximate counting (e.g., using buckets) for scalability.

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