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

SeniorPrefer not to say

May 2026

Summary

Databricks system design round, one question the whole time: a hit counter. Sounds straightforward but they pushed pretty hard on the concurrency angle at the end, which I was not fully ready for.

Questions Asked (1)

Design a hit counter that can record hits and return the total number of hits in the past 300 seconds. The hit(timestamp) and getHits(timestamp) functions receive monotonically non-decreasing timestamps in seconds. Walk through your design choices and how you'd handle scale.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

I went straight to the circular array with 300 buckets, which is the move, but I fumbled explaining why you reset a bucket when the timestamp gap exceeds 300.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a sliding window approach using a queue or circular buffer to store timestamps and counts. Discuss trade-offs between time and space, and how to scale for high throughput and distributed settings.

Pro tip: Mention that timestamps are monotonically non-decreasing, which allows efficient pruning of old hits without scanning the entire data structure. Also, consider using a ring buffer of 300 buckets for O(1) operations when timestamps are in seconds.

1. Clarify Requirements and Constraints

Ask about expected hit rate, precision (seconds vs milliseconds), memory limits, and whether the system is single-node or distributed. Confirm that timestamps are monotonically non-decreasing.

2. Propose a Data Structure

Suggest a queue of timestamps or a circular buffer of 300 buckets (one per second) to track hits. Explain how to prune old entries when recording or querying.

3. Analyze Time and Space Complexity

For the queue approach, hit is O(1) amortized and getHits is O(k) where k is number of hits in window; for circular buffer, both are O(1) but with fixed memory. Discuss trade-offs.

4. Handle Scale and Distribution

For high throughput, consider sharding by user or time, using a distributed cache like Redis with sorted sets, or a time-series database. Discuss eventual consistency and aggregation.

5. Discuss Edge Cases and Optimizations

Address out-of-order timestamps (though monotonic), empty windows, and memory optimization. Mention using a ring buffer with atomic counters for concurrency.

Key Points to Mention

Monotonically non-decreasing timestamps allow efficient pruning without scanning all data.
Sliding window can be implemented with a queue (list) or a circular buffer of 300 buckets.
Time complexity: O(1) amortized for hit, O(1) for getHits with circular buffer; space O(300) or O(number of hits in window).
For scale, shard by user ID or time, use Redis sorted sets with ZADD and ZCOUNT, or a distributed counter with windowing.
Concurrency: use locks or atomic operations for thread safety; consider lock-free structures for high throughput.
Trade-offs: exact vs approximate counts, memory vs accuracy, single-node vs distributed.

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