Number of Recent Calls (นับการโทรล่าสุด) ใน Python

โจทย์: สร้าง Class RecentCounter มีเมธอด ping(t) คืนจำนวน Ping ในช่วง 3000 ms ย้อนหลัง (Inclusive) t เพิ่มขึ้นทุกครั้ง (Strictly increasing)

Input/Output

ping(1)    → 1
ping(100)  → 2
ping(3001) → 3
ping(3002) → 3

อัลกอริทึม: Queue (Sliding Window)

1. เก็บ Timestamp ใน Queue (List)
2. เมื่อ Ping ใหม่: ลบ Timestamp เก่าที่ < t - 3000 ออกจากหน้า Queue
3. เพิ่ม t เข้า Queue
4. คืนขนาด Queue

ตัวอย่างโค้ด

class RecentCounter:
    def __init__(self):
        self.queue = []
    
    def ping(self, t):
        while self.queue and t - self.queue[0] > 3000:
            self.queue.pop(0)
        self.queue.append(t)
        return len(self.queue)

ob = RecentCounter()
print(ob.ping(1))
print(ob.ping(100))
print(ob.ping(3001))
print(ob.ping(3002))

ผลลัพธ์

1
2
3
3

การปรับปรุงประสิทธิภาพ: ใช้ collections.deque แทน List เพื่อ popleft() O(1) แทน pop(0) O(N)

from collections import deque

class RecentCounter:
    def __init__(self):
        self.queue = deque()
    
    def ping(self, t):
        while self.queue and t - self.queue[0] > 3000:
            self.queue.popleft()
        self.queue.append(t)
        return len(self.queue)

Complexity: Amortized O(1) ต่อการเรียก ping()