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:
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:
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.

Memuat komentar...