LeetCode #146 LRU Cache: HashMap + Doubly Linked List คุมความเร็ว O(1)

โจทย์ LRU Cache ให้สร้างแคชความจุคงที่ รองรับ get / put แล้วเตะคีย์ที่ไม่ได้ใช้ นานสุดเมื่อเต็ม เป้าหมายสัมภาษณ์มักอยากได้เฉลี่ย O(1)

วิธีที่ 1: ลิสต์ + สแกน

เก็บคู่คีย์-ค่าในลิสต์ ทุกครั้งที่แตะต้องหาคีย์แล้วย้ายไปหัว เวลา O(n) ต่อครั้ง ใช้อธิบายโจทย์และเทสต์เล็กๆ แต่ช้าเมื่อ capacity สูง

วิธีที่ 2: OrderedDict / dict ที่มีลำดับ (Python)

ใน CPython 3.7+ dict จำลำดับการแทรก ได้ใช้ย้ายคีย์ที่แตะไปท้ายแล้ว popitem(last=False) ตอนเตะ โค้ดสั้น อ่านง่าย เหมาะโปรโตไทป์

วิธีที่ 3: HashMap + Doubly Linked List (แนะนำสัมภาษณ์)

แมปคีย์ → โหนด และลิสต์สองทางคุมลำดับล่าสุด ทุก get/put ตัดโหนดไปหัวใน O(1) ชัดเจนเรื่องโครงสร้างข้อมูล

วิธีที่ 4: ไลบรารีสำเร็จรูป

ในงานจริงอาจใช้แคชของเฟรมเวิร์กที่มี eviction ให้แล้ว แต่ในโจทย์ต้องเขียนเอง

from __future__ import annotations

import unittest
from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)


class LruTests(unittest.TestCase):
    def test_example(self):
        cache = LRUCache(2)
        cache.put(1, 1)
        cache.put(2, 2)
        self.assertEqual(cache.get(1), 1)
        cache.put(3, 3)
        self.assertEqual(cache.get(2), -1)
        cache.put(4, 4)
        self.assertEqual(cache.get(1), -1)
        self.assertEqual(cache.get(3), 3)
        self.assertEqual(cache.get(4), 4)


if __name__ == "__main__":
    unittest.main()

เลือกวิธีไหนดี

• อธิบายโจทย์ / ทดลอง: วิธี 1
• สคริปต์ Python เร็วๆ: วิธี 2
• สัมภาษณ์ที่อยากเห็นพอยน์เตอร์: วิธี 3
• โปรดักชันจริง: ประเมินไลบรารีก่อนเขียนเอง

Recap

• จำคู่ HashMap + DLL สำหรับ O(1)
• เทสต์เคสเตะคีย์หลัง put เกิน capacity
• อย่าลืมอัปเดตลำดับทั้ง get และ put