Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Queue & Deque

Guide 3 of 6 · Path 3 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumqueue-deque

Design Hit Counter

Problem (restated)

Record hits at integer timestamps (seconds). getHits(t) returns hits in the past 300 seconds inclusive of t (i.e. (t-300, t]).

Intuition

Queue of hit times; on getHits drop timestamps ≤ t-300.

Approaches

Queue of timestamps (300s)

Tested only
Time O(1) amortizedSpace O(hits in window)

Idea. hit enqueues; getHits while front ≤ t-300 dequeue; return size.

Walkthrough. hit 1,2,3; getHits(4)=3; hit 300; getHits(300)=4; getHits(301)=3.

Trade-offs. Bucket arrays of size 300 scale better under high QPS with many hits/sec.

Solution
export class HitCounter {
  private q: number[] = [];
  hit(timestamp: number): void {
    this.q.push(timestamp);
  }
  getHits(timestamp: number): number {
    while (this.q.length && this.q[0]! <= timestamp - 300) this.q.shift();
    return this.q.length;
  }
}

export class HitCounter {
  private q: number[] = [];
  hit(timestamp: number): void {
    this.q.push(timestamp);
  }
  getHits(timestamp: number): number {
    while (this.q.length && this.q[0]! <= timestamp - 300) this.q.shift();
    return this.q.length;
  }
}

Template connection

Queue of recent events (same family as RecentCounter).

Reflection