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 (yeniden ifade)

Tamsayı zaman damgalarında (saniye) hit kaydet. getHits(t), t dahil geçmiş 300 saniyedeki hit’leri döndürür (yani (t-300, t]).

Sezgi

Hit zamanlarının kuyruğu; getHits’te zaman damgaları ≤ t-300 olanları düş.

Yaklaşımlar

Zaman damgası kuyruğu (300s)

Doğrulanmadı

Zaman O(1) amortizedAlan O(hits in window)

Fikir. hit enqueue eder; getHits front ≤ t-300 iken dequeue; size döndür.

Yürüyüş. hit 1,2,3; getHits(4)=3; hit 300; getHits(300)=4; getHits(301)=3.

Trade-off. Boyu 300 bucket dizileri, saniyede çok hit olan yüksek QPS altında daha iyi ölçeklenir.

Çözüm

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;
  }
}

Şablon bağlantısı

Son olayların kuyruğu (RecentCounter ile aynı aile).

Yansıma

getHits 300 saniyeden eski zaman damgalarını önden atar. Pencere (t-300, t].
Aynı timestamp birden fazla hit: her hit ayrı kayıt mı, sayaç mı? Bellek farkı ne?
Zaman azalmaz (garanti). Garanti yoksa kuyruk yetmez.