LeetCode Grinding
Algorithms2 menit baca

Solusi Leetcode - Logger Rate Limiter

Simpan timestamp terakhir setiap pesan dicetak untuk menerapkan interval logging sepuluh detik.

Di artikel ini 4 bagian

Logger rate limiter perlu mengingat kapan setiap pesan terakhir diterima. Request yang ditolak nggak boleh mengubah timestamp itu, supaya percobaan berulang nggak terus memperpanjang waktu tunggu.

Aturan yang harus dipenuhi

Untuk setiap pesan, terima request pertama. Request berikutnya cuma diterima kalau udah lewat minimal timeLimit detik sejak request terakhir yang diterima. Request yang ditolak nggak menggeser timestamp yang disimpan.

Salah satu pilihan adalah queue berisi timestamp dan set berisi pesan aktif. Sebelum setiap request, versi ini menghapus entry yang udah kedaluwarsa:

javascript
class LoggerNaive {
  constructor(timeLimit = 10) {
    this.queue = [];
    this.messageSet = new Set();
    this.limit = timeLimit;
  }

  shouldPrintMessage(timestamp, message) {
    // Remove old messages (older than timeLimit)
    while (
      this.queue.length > 0 &&
      timestamp - this.queue[0].timestamp >= this.limit
    ) {
      const old = this.queue.shift();
      this.messageSet.delete(old.message);
    }

    // Check if message is duplicate
    if (this.messageSet.has(message)) {
      return false;
    }

    // Add new message
    this.queue.push({ timestamp, message });
    this.messageSet.add(message);
    return true;
  }
}

Versi queue dan set ini benar, tapi harus mengurus dua struktur dan membersihkan queue di setiap request. shift pada array JavaScript itu O(n), jadi proses pembersihan ini bisa mendominasi kerjanya.

Timestamp terakhir dilihat

Map bisa langsung menyimpan timestamp terakhir yang diterima:

javascript
class Logger {
  constructor(timeLimit = 10) {
    this.requests = Object.create(null); // Message names must not inherit object properties
    this.limit = timeLimit;
  }

  shouldPrintMessage(timestamp, message) {
    // If message is new OR enough time has passed
    if (
      this.requests[message] === undefined ||
      timestamp - this.requests[message] >= this.limit
    ) {
      this.requests[message] = timestamp; // Update last seen time
      return true;
    }
    return false; // Duplicate within time limit
  }
}

Method ini mengecek apakah timestamp yang disimpan bernilai undefined atau apakah timestamp - lastTimestamp >= timeLimit. Timestamp nol adalah nilai simpanan yang valid. Request yang diizinkan meng-update map dan mengembalikan true. Request yang ditolak membiarkan timestamp sebelumnya tetap sama dan mengembalikan false.

Object-nya nggak punya prototype, jadi nama pesan seperti toString dan __proto__ berperilaku sama kayak key lainnya. Interval default-nya sepuluh detik. Contoh di bawah memberikan tujuh detik secara eksplisit.

Penelusuran dan biaya operasional

Dengan timeLimit = 7, pemanggilannya berjalan seperti ini:

javascript
const logger = new Logger(7);

// Timestamp 1: "hello" is new
logger.shouldPrintMessage(1, "hello"); 
// requests = {"hello": 1}
// Returns: true

// Timestamp 5: "hello" seen 4 seconds ago (< 7)
logger.shouldPrintMessage(5, "hello"); 
// Only 4 seconds passed, not enough
// Returns: false

// Timestamp 6: "world" is new
logger.shouldPrintMessage(6, "world"); 
// requests = {"hello": 1, "world": 6}
// Returns: true

// Timestamp 8: "hello" seen 7 seconds ago (>= 7)
logger.shouldPrintMessage(8, "hello"); 
// 7 seconds passed, enough time
// requests = {"hello": 8, "world": 6}
// Returns: true

// Timestamp 10: "world" seen 4 seconds ago (< 7)
logger.shouldPrintMessage(10, "world"); 
// Only 4 seconds passed, not enough
// Returns: false

Hash map menggantikan dua struktur yang harus dikoordinasikan dengan satu catatan last seen. Pesan yang berulang menimpa timestamp sebelumnya, bukan menambah entry di queue.

Hash map memberikan waktu lookup dan update rata-rata O(1) per request. Hash map menyimpan satu timestamp per pesan unik, jadi space complexity-nya O(n), dengan n adalah jumlah pesan unik.

Batasan untuk sebuah service

Perbandingannya harus sesuai dengan aturan batas di soal. Implementasi ini memakai >= supaya request yang tepat di batas tetap diterima. Perbandingan dengan > bakal menolaknya. Timestamp harus mengikuti asumsi urutan di soal, dan request pertama untuk sebuah pesan harus diizinkan.

Class sederhana ini menyimpan entry selamanya. Service yang jalan terus-menerus mungkin perlu menghapus pesan lama dan membatasi ukuran map. Akses bersama dari banyak thread mungkin butuh sinkronisasi. Kalau state-nya harus tetap ada setelah restart, service-nya juga butuh persistent storage.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan