Bạn thiết kế một cấu trúc dữ liệu với các yêu cầu O(1)/O(log n) cụ thể như thế nào?

Question

Accepted Answer

Thiết kế một cấu trúc tùy chỉnh nghĩa là **kết hợp các cấu trúc có sẵn** sao cho mỗi thao tác yêu cầu đạt độ phức tạp mục tiêu của nó, để một cấu trúc che điểm yếu của cấu trúc khác. Kỹ thuật kinh điển là ghép một **hash map** với một **array, heap, hoặc linked list**.

## Một ví dụ đã giải: insert, delete, getRandom — tất cả O(1)

Yêu cầu: `insert(x)`, `remove(x)`, và `getRandom()` mỗi cái trong O(1). Chỉ một hash map không thể làm random O(1); chỉ một array không thể làm remove O(1). **Kết hợp chúng**.

```python
import random
class RandomizedSet:
    def __init__(self):
        self.idx = {}      # value -> index trong list
        self.vals = []     # các value để chọn ngẫu nhiên O(1)
    def insert(self, x):                    # O(1)
        if x in self.idx: return False
        self.idx[x] = len(self.vals)
        self.vals.append(x)
        return True
    def remove(self, x):                    # O(1): hoán đổi với cuối, pop
        if x not in self.idx: return False
        i, last = self.idx[x], self.vals[-1]
        self.vals[i] = last                 # chuyển cái cuối vào chỗ trống
        self.idx[last] = i
        self.vals.pop()
        del self.idx[x]
        return True
    def getRandom(self):                    # O(1)
        return random.choice(self.vals)
```

## Một công thức thiết kế tổng quát

```text
1. Liệt kê mọi thao tác yêu cầu + độ phức tạp mục tiêu của nó.
2. Với mỗi cái, nêu tên một cấu trúc đạt được nó:
     theo key O(1)     -> hash map
     theo index O(1)   -> array
     min/max O(log n)  -> heap
     có thứ tự O(log n)-> balanced tree / skip list
     nối O(1)          -> doubly linked list
3. KẾT HỢP chúng; dùng hash map để ánh xạ key -> vị trí/node
   trong cấu trúc kia sao cho cập nhật vẫn O(1).
4. Kiểm chứng mỗi thao tác so với mục tiêu của nó.
```

| Mẫu | Các cấu trúc kết hợp | Cho phép |
|---|---|---|
| LRU cache | hash map + doubly linked list | get/put O(1) |
| Randomized set O(1) | hash map + array | insert/remove/random O(1) |
| Min O(1) trên một stack | stack + min-stack phụ trợ | getMin O(1) |

## Tại sao điều này quan trọng

Các hệ thống thực tế hiếm khi cần một cấu trúc giáo khoa đơn lẻ — chúng cần một cấu trúc hỗn hợp được tinh chỉnh cho một mẫu truy cập cụ thể, đó chính là điều các thiết kế này mang lại.

Người phỏng vấn dùng các bài toán này để kiểm tra liệu bạn có thể lập luận từ **chi phí thao tác đến một sự kết hợp**, kỹ năng cốt lõi đằng sau thiết kế hệ thống hiệu năng cao.

Mẫu	Các cấu trúc kết hợp	Cho phép
LRU cache	hash map + doubly linked list	get/put O(1)
Randomized set O(1)	hash map + array	insert/remove/random O(1)
Min O(1) trên một stack	stack + min-stack phụ trợ	getMin O(1)