[AlgoMastery]
Topics›Queue›Design Hit Counter
📖

Design Hit Counter

Queue
~20 min read
5 practice problems

Overview

Design Hit Counter is a problem where you need to track the number of hits (requests, events, etc.) within a specific time window. A queue is perfect for this because it maintains timestamps in chronological order and automatically removes timestamps outside the window.

This problem demonstrates:

  • Time-window tracking - Track hits within time window
  • Automatic cleanup - Remove old timestamps outside window
  • Efficient counting - Count hits efficiently
  • Chronological order - Queue maintains timestamp order

Key characteristics:

  • Time-based window - Track hits within time window (e.g., last 5 minutes)
  • Queue of timestamps - Store hit timestamps in queue
  • Automatic cleanup - Remove timestamps outside window
  • O(1) operations - Efficient hit recording and counting
  • Real-time - Handle hits as they arrive

How Hit Counter Works

Hit counter uses a queue to track timestamps:

  1. Record hit - Enqueue current timestamp
  2. Remove old - Remove timestamps outside time window
  3. Count hits - Return queue size (number of hits in window)
  4. Chronological order - Queue maintains timestamp order

The queue automatically maintains hits within the time window.

Basic Hit Counter Implementation

Simple hit counter using queue:

class HitCounter {
  private queue: number[] = [];
  private windowSize: number; // in seconds
  
  constructor(windowSize: number = 300) { // Default 5 minutes
    this.windowSize = windowSize;
  }
  
  hit(timestamp: number): void {
    // Remove old hits outside window
    this.cleanup(timestamp);
    
    // Add new hit
    this.queue.push(timestamp);
  }
  
  getHits(timestamp: number): number {
    // Remove old hits outside window
    this.cleanup(timestamp);
    
    // Return count of hits in window
    return this.queue.length;
  }
  
  private cleanup(timestamp: number): void {
    // Remove timestamps outside window
    while (this.queue.length > 0 && timestamp - this.queue[0] >= this.windowSize) {
      this.queue.shift();
    }
  }
}

Time: O(n) cleanup worst case, O(1) amortized, Space: O(n)

Limitation: shift() is O(n), making cleanup inefficient.

Pattern 1: LeetCode - Design Hit Counter

LeetCode problem implementation:

class HitCounter {
  private queue: number[] = [];
  
  hit(timestamp: number): void {
    this.queue.push(timestamp);
  }
  
  getHits(timestamp: number): number {
    // Remove hits older than 5 minutes (300 seconds)
    while (this.queue.length > 0 && timestamp - this.queue[0] >= 300) {
      this.queue.shift();
    }
    
    return this.queue.length;
  }
}

Time: O(n) worst case, O(1) amortized, Space: O(n)

Key insight: Remove timestamps older than 5 minutes.

Pattern 2: Optimized Hit Counter with Circular Buffer

Using circular buffer for better performance:

class HitCounterOptimized {
  private timestamps: number[];
  private hits: number[];
  private windowSize: number;
  private totalHits = 0;
  
  constructor(windowSize: number = 300) {
    this.windowSize = windowSize;
    // Use array of size windowSize (one bucket per second)
    this.timestamps = new Array(windowSize).fill(0);
    this.hits = new Array(windowSize).fill(0);
  }
  
  hit(timestamp: number): void {
    const index = timestamp % this.windowSize;
    
    // If timestamp is for different second, reset bucket
    if (this.timestamps[index] !== timestamp) {
      this.timestamps[index] = timestamp;
      this.totalHits -= this.hits[index];
      this.hits[index] = 1;
      this.totalHits++;
    } else {
      // Same second, increment
      this.hits[index]++;
      this.totalHits++;
    }
  }
  
  getHits(timestamp: number): number {
    let count = 0;
    
    // Count hits in valid time window
    for (let i = 0; i < this.windowSize; i++) {
      if (timestamp - this.timestamps[i] < this.windowSize) {
        count += this.hits[i];
      }
    }
    
    return count;
  }
}

Time: O(1) hit, O(k) getHits where k is window size, Space: O(k)

Key optimization: Bucket hits by second, avoiding queue operations.

Pattern 3: Hit Counter with Deque

Using deque for efficient removal:

class HitCounterDeque {
  private deque: number[] = [];
  private windowSize: number;
  
  constructor(windowSize: number = 300) {
    this.windowSize = windowSize;
  }
  
  hit(timestamp: number): void {
    this.deque.push(timestamp);
    this.cleanup(timestamp);
  }
  
  getHits(timestamp: number): number {
    this.cleanup(timestamp);
    return this.deque.length;
  }
  
  private cleanup(timestamp: number): void {
    // Remove from front (oldest timestamps)
    while (this.deque.length > 0 && timestamp - this.deque[0] >= this.windowSize) {
      this.deque.shift();
    }
  }
}

Time: O(n) worst case cleanup, Space: O(n)

Note: Still uses shift(), but deque structure allows efficient front removal.

Pattern 4: Distributed Hit Counter

Hit counter that can handle distributed systems:

class DistributedHitCounter {
  private queues: Map<string, number[]> = new Map();
  private windowSize: number;
  
  constructor(windowSize: number = 300) {
    this.windowSize = windowSize;
  }
  
  hit(serverId: string, timestamp: number): void {
    if (!this.queues.has(serverId)) {
      this.queues.set(serverId, []);
    }
    
    const queue = this.queues.get(serverId)!;
    queue.push(timestamp);
    this.cleanup(queue, timestamp);
  }
  
  getHits(timestamp: number): number {
    let total = 0;
    
    for (const queue of this.queues.values()) {
      this.cleanup(queue, timestamp);
      total += queue.length;
    }
    
    return total;
  }
  
  private cleanup(queue: number[], timestamp: number): void {
    while (queue.length > 0 && timestamp - queue[0] >= this.windowSize) {
      queue.shift();
    }
  }
}

Time: O(n × servers), Space: O(n × servers)

Use case: Track hits across multiple servers.

Pattern 5: Hit Counter with Rate Limiting

Hit counter that enforces rate limits:

class RateLimitedHitCounter {
  private queue: number[] = [];
  private windowSize: number;
  private maxHits: number;
  
  constructor(windowSize: number, maxHits: number) {
    this.windowSize = windowSize;
    this.maxHits = maxHits;
  }
  
  hit(timestamp: number): boolean {
    // Cleanup old hits
    this.cleanup(timestamp);
    
    // Check rate limit
    if (this.queue.length >= this.maxHits) {
      return false; // Rate limit exceeded
    }
    
    // Record hit
    this.queue.push(timestamp);
    return true;
  }
  
  getHits(timestamp: number): number {
    this.cleanup(timestamp);
    return this.queue.length;
  }
  
  private cleanup(timestamp: number): void {
    while (this.queue.length > 0 && timestamp - this.queue[0] >= this.windowSize) {
      this.queue.shift();
    }
  }
}

Time: O(n) cleanup, Space: O(n)

Key insight: Enforce rate limit by checking queue size.

Pattern 6: Hit Counter with Sliding Window

Hit counter with configurable window:

class SlidingWindowHitCounter {
  private queue: number[] = [];
  
  hit(timestamp: number): void {
    this.queue.push(timestamp);
  }
  
  getHits(timestamp: number, windowSize: number): number {
    // Remove hits outside window
    while (this.queue.length > 0 && timestamp - this.queue[0] >= windowSize) {
      this.queue.shift();
    }
    
    return this.queue.length;
  }
  
  // Get hits for multiple windows
  getHitsMultipleWindows(timestamp: number, windows: number[]): Map<number, number> {
    const result = new Map<number, number>();
    
    for (const windowSize of windows) {
      result.set(windowSize, this.getHits(timestamp, windowSize));
    }
    
    return result;
  }
}

Time: O(n × windows), Space: O(n)

Key insight: Support multiple window sizes.

Pattern 7: Hit Counter with Persistence

Hit counter that can persist state:

class PersistentHitCounter {
  private queue: number[] = [];
  private windowSize: number;
  
  constructor(windowSize: number = 300) {
    this.windowSize = windowSize;
    // Load from storage if available
    this.loadState();
  }
  
  hit(timestamp: number): void {
    this.cleanup(timestamp);
    this.queue.push(timestamp);
    this.saveState();
  }
  
  getHits(timestamp: number): number {
    this.cleanup(timestamp);
    return this.queue.length;
  }
  
  private cleanup(timestamp: number): void {
    while (this.queue.length > 0 && timestamp - this.queue[0] >= this.windowSize) {
      this.queue.shift();
    }
  }
  
  private saveState(): void {
    // Save to storage (localStorage, database, etc.)
    localStorage.setItem('hitCounter', JSON.stringify(this.queue));
  }
  
  private loadState(): void {
    // Load from storage
    const saved = localStorage.getItem('hitCounter');
    if (saved) {
      this.queue = JSON.parse(saved);
    }
  }
}

Time: O(n) cleanup + storage, Space: O(n)

Key insight: Persist state for recovery.

When to Use Queue for Hit Counter

Use queue for hit counter when you see:

  • "Hit counter" - Track hits/requests/events
  • "Time window" - Track hits within time window
  • "Rate limiting" - Enforce rate limits
  • "Analytics" - Track user activity
  • "Request counting" - Count API requests
  • "Event tracking" - Track events over time
  • "Sliding window" - Maintain sliding window of hits

Key distinction:

  • Queue - Perfect for time-ordered timestamps
  • Array - Can work but less semantic
  • Circular buffer - More efficient for fixed window

Hit Counter Patterns

| Pattern | Description | Use Case |

|---------|-------------|----------|

| Basic | Simple queue of timestamps | General purpose |

| Optimized | Bucket-based with circular buffer | High performance |

| Rate Limited | Enforce maximum hits | Rate limiting |

| Distributed | Multiple servers | Distributed systems |

| Sliding Window | Configurable window sizes | Flexible analytics |

| Persistent | Save/load state | Recovery, persistence |

Remember:

  • Queue for chronological timestamp tracking
  • Cleanup old timestamps outside window
  • Optimize with buckets for high performance

Template (Basic Hit Counter)

class HitCounterTemplate {
  private queue: number[] = [];
  private windowSize: number;
  
  constructor(windowSize: number = 300) {
    this.windowSize = windowSize;
  }
  
  hit(timestamp: number): void {
    this.cleanup(timestamp);
    this.queue.push(timestamp);
  }
  
  getHits(timestamp: number): number {
    this.cleanup(timestamp);
    return this.queue.length;
  }
  
  private cleanup(timestamp: number): void {
    while (this.queue.length > 0 && timestamp - this.queue[0] >= this.windowSize) {
      this.queue.shift();
    }
  }
}

Template (Optimized with Buckets)

class HitCounterBucketsTemplate {
  private timestamps: number[];
  private hits: number[];
  private windowSize: number;
  private totalHits = 0;
  
  constructor(windowSize: number) {
    this.windowSize = windowSize;
    this.timestamps = new Array(windowSize).fill(0);
    this.hits = new Array(windowSize).fill(0);
  }
  
  hit(timestamp: number): void {
    const index = timestamp % this.windowSize;
    
    if (this.timestamps[index] !== timestamp) {
      this.timestamps[index] = timestamp;
      this.totalHits -= this.hits[index];
      this.hits[index] = 1;
      this.totalHits++;
    } else {
      this.hits[index]++;
      this.totalHits++;
    }
  }
  
  getHits(timestamp: number): number {
    let count = 0;
    for (let i = 0; i < this.windowSize; i++) {
      if (timestamp - this.timestamps[i] < this.windowSize) {
        count += this.hits[i];
      }
    }
    return count;
  }
}

Time and Space Complexity

Basic Implementation

  • hit: O(1) amortized, O(n) worst case
  • getHits: O(1) amortized, O(n) worst case
  • Space: O(n) where n is hits in window

Optimized with Buckets

  • hit: O(1)
  • getHits: O(k) where k is window size
  • Space: O(k)

Note: Bucket-based approach provides better worst-case performance.

Practice Tips

  1. Cleanup on both operations - Cleanup in both hit() and getHits()
  2. Use buckets - For high performance, use bucket-based approach
  3. Handle edge cases - Empty queue, timestamps out of order
  4. Avoid shift() - Use optimized approach for better performance
  5. Window size - Consider window size in design
  6. Rate limiting - Can combine with rate limiting
  7. Distributed - Consider distributed systems requirements

Common Mistakes

  1. Not cleaning up - Forgetting to remove old timestamps
  2. Using shift() - O(n) operation, use buckets instead
  3. Wrong window calculation - Off-by-one errors in window size
  4. Not handling out-of-order - Timestamps arriving out of order
  5. Memory leaks - Not cleaning up old timestamps
  6. Race conditions - Not handling concurrent access
  7. Precision issues - Timestamp precision problems

Real-World Applications

Hit counter is used extensively in:

  • Web Analytics - Track page views, user activity
  • API Rate Limiting - Limit API requests per time window
  • Monitoring Systems - Track system events, errors
  • Social Media - Track likes, views, interactions
  • E-commerce - Track product views, purchases
  • Security - Track login attempts, suspicious activity
  • Performance Monitoring - Track request rates
  • Ad Serving - Track ad impressions, clicks

Related Concepts

  • Queue - Data structure for timestamp tracking
  • Sliding Window - General sliding window pattern
  • Rate Limiting - Enforcing rate limits
  • Time Series - Time-series data analysis
  • Circular Buffer - Efficient window implementation

Summary

Design Hit Counter demonstrates:

  • Time-window tracking - Track hits within time window
  • Queue-based - Queue maintains timestamp order
  • Automatic cleanup - Remove timestamps outside window
  • Efficient counting - Count hits efficiently
  • Real-time - Handle hits as they arrive

Key takeaways:

  • Use queue to maintain chronological timestamps
  • Cleanup old timestamps outside window
  • Use bucket-based approach for high performance
  • Essential for analytics, rate limiting, and monitoring
  • Foundation for many time-window problems

Mastering hit counter design will help you solve time-window problems, implement rate limiting, and design efficient analytics systems in coding interviews.

← PreviousMoving Average from Data StreamNext →Design Logger Rate Limiter