Solusi Leetcode - Logger Rate Limiter

Membuat logger rate limiter artinya memutuskan apakah sebuah pesan boleh ditampilkan di timestamp tertentu. Keputusannya cuma bergantung pada kapan pesan itu terakhir diterima. Pendekatan pertama saya memakai queue dan set sekaligus, tapi hash map aja udah cukup untuk aturan ini.

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.

Awalnya saya memakai queue untuk timestamp dan set untuk pesan yang sedang aktif. Entry lama dihapus sebelum setiap request:

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

Lalu saya cuma menyimpan timestamp terakhir yang diterima untuk setiap pesan:

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:

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.

Rate limiter ini butuh satu fakta per pesan: timestamp terakhir yang diterima. Hash map mencatat fakta itu secara langsung, sehingga operasi dasarnya berjalan dalam waktu konstan, sementara urusan cleanup dan kebijakan concurrency diserahkan ke service di sekitarnya.