Thiết kế LRU Cache với get/put O(1) — vì sao cần kết hợp HashMap và doubly linked list?

Ý tưởng: Cần hai khả năng O

1. cùng lúc:
2. tra cứu key
3. biết & dời phần tử "vừa dùng" và loại phần tử "lâu nhất chưa dùng". - HashMap key → node: tra cứu O(1). - Doubly linked list xếp theo thứ tự dùng: đầu = mới nhất, đuôi = cũ nhất. Có con trỏ trước/sau nên tách & chèn node bất kỳ trong O(1)

Mỗi get/put đẩy node lên đầu. Khi đầy, xóa node ở đuôi. Dùng dummy head/tail để khỏi xử lý biên.

class LRUCache {
  private map = new Map<number, number>() // Map JS giữ thứ tự chèn → mô phỏng LRU
  constructor(private capacity: number) {}
  get(key: number): number {
    if (!this.map.has(key)) return -1
    const val = this.map.get(key)!
    this.map.delete(key); this.map.set(key, val) // chuyển xuống cuối = mới dùng
    return val
  }
  put(key: number, value: number): void {
    if (this.map.has(key)) this.map.delete(key)
    else if (this.map.size >= this.capacity)
      this.map.delete(this.map.keys().next().value!) // xóa key cũ nhất
    this.map.set(key, value)
  }
}

Độ phức tạp: get/put O(1) thời gian, O(capacity) bộ nhớ.

Lưu ý: Phỏng vấn thường muốn bạn tự cài doubly linked list + HashMap để chứng tỏ hiểu cơ chế O(1); bản trên lợi dụng Map của JS giữ thứ tự chèn — gọn nhưng nên nói rõ trade-off khi được hỏi.

Idea: You need two O

1. abilities at once:
2. look up a key
3. know & move the "just used" item and evict the "least recently used" one. - HashMap key → node: O
4. lookup. - Doubly linked list ordered by usage: head = most recent, tail = oldest. With prev/next pointers you can unlink & insert any node in O(1)

Each get/put moves the node to the head. When full, drop the tail node. Use dummy head/tail to avoid edge cases.

class LRUCache {
  private map = new Map<number, number>() // JS Map keeps insertion order → simulates LRU
  constructor(private capacity: number) {}
  get(key: number): number {
    if (!this.map.has(key)) return -1
    const val = this.map.get(key)!
    this.map.delete(key); this.map.set(key, val) // move to end = recently used
    return val
  }
  put(key: number, value: number): void {
    if (this.map.has(key)) this.map.delete(key)
    else if (this.map.size >= this.capacity)
      this.map.delete(this.map.keys().next().value!) // evict oldest key
    this.map.set(key, value)
  }
}

Complexity: get/put O(1) time, O(capacity) space.

Note: Interviews usually want you to hand-roll the doubly linked list + HashMap to prove you understand the O(1) mechanism; the version above exploits JS Map insertion order — compact, but call out the trade-off when asked.