← Databricks Interview Insights

Databricks·AI Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say
Jun 2026

Summary

System design round at Databricks for an AI Engineer role, focused entirely on building a key-value cache with hit counting. Pretty deep dive, they wanted specifics on data structures and concurrency, not just a sketch.

Questions Asked (1)

Q1

Design a key-value cache that supports TTL-based expiration, an LRU eviction policy, and efficient hit-count queries both globally and per key within a recent time window.

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

I started with the hash map plus doubly linked list combo for LRU which they seemed fine with, but the hit-count window requirement is where I stumbled.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints (e.g., expected scale, read/write ratio, TTL granularity, time window definition). Then propose a design that combines a hash map for key-value storage, a doubly linked list for LRU eviction, and a time-bucketed counter structure for hit counts. Discuss trade-offs between precision, memory, and performance, and consider concurrency and distributed scenarios.

Pro tip: Mention that TTL expiration can be handled lazily on access plus a background sweeper to avoid memory bloat, and that hit-count queries can use a sliding window with time buckets (e.g., per-second counters) to balance accuracy and memory.

1. Clarify Requirements and Constraints

Ask about scale (number of keys, QPS), TTL precision, time window size, hit-count query frequency, and whether the cache is single-node or distributed. This shapes the design choices.

2. Design Core Data Structures

Propose a hash map for O(1) key lookup, a doubly linked list for LRU order, and a min-heap or timing wheel for TTL expiration. For hit counts, use a ring buffer of time buckets per key and globally.

3. Handle TTL Expiration and LRU Eviction

Explain lazy expiration on access and a background thread for proactive cleanup. For LRU, move accessed items to the front and evict from the tail when capacity is exceeded.

4. Implement Hit-Count Queries

Use a sliding window with time buckets (e.g., per-second counters) for both global and per-key hit counts. Aggregate buckets within the window to answer queries efficiently.

5. Discuss Trade-offs and Scalability

Compare exact vs approximate counting, memory overhead, and concurrency strategies (e.g., sharding, locks). Mention distributed caching options like Redis and how to extend the design.

Key Points to Mention

  • Use a hash map + doubly linked list for O(1) LRU operations.
  • TTL expiration: lazy deletion on access plus background sweeper to avoid memory leaks.
  • Hit-count queries: time-bucketed counters (e.g., per-second) in a ring buffer for sliding window.
  • Trade-offs: exact counting vs approximate (e.g., Count-Min Sketch) for memory efficiency.
  • Concurrency: sharding, read-write locks, or lock-free structures for high throughput.
  • Distributed considerations: consistent hashing, replication, and using Redis as a reference.

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