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

Queue & Deque

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: Intervals →

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

Easyqueue-deque

Number of Recent Calls

Problem (restated)

ping(t) records a call at time t (ms). Return how many calls occurred in [t-3000, t].

Intuition

Queue of timestamps; enqueue t, dequeue anything before t-3000, return size.

Approaches

Sliding queue window

Tested only
Time O(1) amortizedSpace O(w)

Idea. monotonic increasing t guarantees front-only eviction.

Walkthrough. ping(1)→1, ping(100)→2, ping(3001)→3, ping(3002)→3.

Trade-offs. Deque of events is the queue-deque rolling window pattern.

Solution
export class RecentCounter {
  private q: number[] = [];
  ping(t: number): number {
    this.q.push(t);
    while (this.q[0]! < t - 3000) this.q.shift();
    return this.q.length;
  }
}

export class RecentCounter {
  private q: number[] = [];
  ping(t: number): number {
    this.q.push(t);
    while (this.q[0]! < t - 3000) this.q.shift();
    return this.q.length;
  }
}

Template connection

Queue & Deque recent-event tracking.

Reflection