Course4all

Design Hit Counter

Expert Answer & Key Takeaways

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on State Management and API Design. ### Core Principles 1. Encapsulation: Keep data private and expose functionality through well-defined methods. 2. Trade-offs: Every design choice has a cost. Is it better to have O(1)O(1) read and O(N)O(N) write, or vice versa? 3. State Consistency: Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for O(1)O(1) caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - HashMap: Provides O(1)O(1) lookups for keys to their corresponding nodes. - DLL: Provides O(1)O(1) addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in Queue using Stacks or Dynamic Arrays. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is O(1)O(1), and "flipping" elements to another stack happens only when necessary, averaging O(1)O(1) per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., Circular Queue, Hit Counter). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., Bounded Blocking Queue). - Use Mutexes (Locks) to prevent data races. - Use Condition Variables (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. Identify the API: What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. Define the State: What variables represent the current state? (Size, Capacity, Pointers). 3. Choose the Data Structures: Select the combination that minimizes time complexity for the most frequent operations. 4. Dry Run: Trace the state changes through a sequence of operations based on your chosen structure.

Design Hit Counter

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).
Medium

Examples

Input: hit(1), hit(2), hit(3), getHits(4), hit(300), getHits(300), getHits(301)
Output: 3, 4, 3
Approach 1

Level I: Queue of Timestamps

Intuition

Record every hit as a timestamp in a queue. For getHits, remove all timestamps from the front that are older than 300 seconds.
⏱ Hit: O(1), getHits: O(N).💾 O(N).

Detailed Dry Run

Queue: [1, 2, 3]. getHits(305) -> 1 is older than (305-300=5), so remove 1.
java
import java.util.*;\nclass HitCounter {\n    private Queue<Integer> q = new LinkedList<>();\n    public void hit(int t) { q.add(t); }\n    public int getHits(int t) {\n        while (!q.isEmpty() && t - q.peek() >= 300) q.poll();\n        return q.size();\n    }\n}
Approach 2

Level II: Map of Count by Second

Intuition

Instead of storing every hit, we store the total hit count for each unique second using a HashMap<Timestamp, Count>. This is more space-efficient if there are many hits at the same time.
⏱ Hit: O(1), getHits: O(300).💾 O(300) maximum.

Detailed Dry Run

hit(1), hit(1), hit(2) -> {1: 2, 2: 1}. getHits(301) -> Sum counts for keys > 1.
java
class HitCounter {
    private Map<Integer, Integer> map = new HashMap<>();
    public void hit(int t) { map.put(t, map.getOrDefault(t, 0) + 1); }
    public int getHits(int t) {
        int count = 0;
        for (int time : map.keySet()) if (t - time < 300) count += map.get(time);
        return count;
    }
}
Approach 3

Level III: Scalable Circular Array (Optimal)

Intuition

To handle large-scale systems with millions of hits, we use a fixed-size array of 300 buckets (one for each second). Each bucket stores the timestamp and hit count.
⏱ Hit: O(1), getHits: O(B) where B=300.💾 O(B).

Detailed Dry Run

Timestamp 301 maps to bucket 301%300 = 1. If old timestamp in bucket 1 was 1, we reset count. Else increment.
java
class HitCounter {\n    private int[] times = new int[300], hits = new int[300];\n    public void hit(int t) {\n        int idx = (t - 1) % 300;\n        if (times[idx] != t) { times[idx] = t; hits[idx] = 1; }\n        else hits[idx]++;\n    }\n    public int getHits(int t) {\n        int res = 0;\n        for (int i=0; i<300; i++) if (t - times[i] < 300) res += hits[i];\n        return res;\n    }\n}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionImplement Queue using Stacks
Next Question →Design Circular Queue