Bạn chọn cấu trúc dữ liệu phù hợp cho một bài toán như thế nào?

Question

Accepted Answer

Chọn cấu trúc mà **các thao tác thường xuyên nhất của nó rẻ nhất** cho mẫu truy cập của bạn. Bắt đầu bằng cách liệt kê các thao tác bạn sẽ thực hiện, ước lượng tần suất của chúng, sau đó khớp chúng với điểm mạnh của một cấu trúc.

## Một danh sách kiểm tra quyết định

```text
1. Bạn truy cập dữ liệu thế nào?  theo index -> array
                                  theo key   -> hash map
                                  theo thứ tự-> tree / heap
2. Cần thứ tự?                    sắp xếp    -> balanced BST / sorted array
                                  FIFO       -> queue
                                  LIFO       -> stack
3. Chèn ở giữa thường xuyên?      -> linked list
4. Cần "đã thấy chưa?" nhanh      -> set / hash map
5. Cần "tốt nhất/min/max tiếp"    -> heap (priority queue)
```

## Khớp thao tác với độ phức tạp

| Cần | Cấu trúc tốt nhất | Chi phí thao tác then chốt |
|---|---|---|
| Truy cập ngẫu nhiên theo index | dynamic array | O(1) |
| Tra cứu theo key | hash map | O(1) avg |
| Sắp xếp + truy vấn khoảng | balanced BST | O(log n) |
| Min/max lặp lại | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Tìm kiếm tiền tố | trie | O(L) |

## Ví dụ lập luận

```text
"Tìm 10 từ xuất hiện nhiều nhất trong một file khổng lồ."
 - đếm tần suất       -> hash map (cập nhật O(1))
 - giữ top 10         -> min-heap kích thước 10 (O(log 10) mỗi từ)
```

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

Chọn tốt thường là khác biệt giữa một giải pháp O(n) và O(n²) — đòn bẩy đơn lẻ lớn nhất đối với hiệu năng.

Người phỏng vấn kiểm tra chính xác lập luận này: họ muốn thấy bạn ánh xạ yêu cầu sang chi phí thao tác, chứ không phải học thuộc lòng các cấu trúc.

Cần	Cấu trúc tốt nhất	Chi phí thao tác then chốt
Truy cập ngẫu nhiên theo index	dynamic array	O(1)
Tra cứu theo key	hash map	O(1) avg
Sắp xếp + truy vấn khoảng	balanced BST	O(log n)
Min/max lặp lại	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Tìm kiếm tiền tố	trie	O(L)