Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

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

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?