Nhiều web dev nghĩ rằng thuật toán chỉ để “vượt qua phỏng vấn”. Thực tế, thuật toán là công cụ để bạn tối ưu hóa code từ việc xử lý chậm chạp O(n²) xuống O(log n), cứu rỗi server khỏi bị sập khi traffic tăng cao.
#1. Mảng (Array) vs Hash Map: Cuộc chiến O(n) và O(1)
Trong PHP, mọi mảng thực chất là một Hash Map (HashTable).
- Vấn đề: Bạn có 10.000 sản phẩm và cần kiểm tra xem sản phẩm có ID là 500 có tồn tại không.
- Cách tệ (O(n)):
in_array(500, $productIds). PHP sẽ lặp qua từng phần tử. Nếu xui xẻo, nó phải lặp 10.000 lần. - Cách tốt (O(1)):
isset($productMap[500]). PHP sử dụng hàm băm (Hash function) để tìm thẳng đến vị trí bộ nhớ chứa ID đó.
Tip: Nếu bạn cần lookup dữ liệu lặp đi lặp lại trong một mảng lớn, hãy dùng array_flip() để biến Value thành Key và tận dụng tốc độ O(1).
#2. Chiến lược Caching: Thuật toán LRU (Least Recently Used)
Khi bạn cài đặt Redis, bạn thường thấy cấu hình maxmemory-policy: allkeys-lru. Đây là một thuật toán cực kỳ quan trọng:
- Nguyên lý: Khi bộ nhớ đầy, hệ thống sẽ xóa đi các phần tử ít được truy cập nhất trong thời gian gần đây.
- Ứng dụng: Giúp cache luôn giữ lại những dữ liệu “hot” nhất, tối ưu hóa tỷ lệ Cache Hit.
#3. Đồ thị (Graph): Xử lý quan hệ “Bạn của bạn”
Trong các hệ thống mạng xã hội hoặc thương mại điện tử (gợi ý sản phẩm), dữ liệu không nằm ở dạng bảng phẳng mà ở dạng đồ thị.
- BFS (Breadth-First Search): Tìm kiếm theo chiều rộng. Thích hợp để tìm những người bạn ở “cấp độ 1” hoặc “cấp độ 2”.
- DFS (Depth-First Search): Tìm kiếm theo chiều sâu. Thích hợp để duyệt qua toàn bộ các danh mục sản phẩm lồng nhau nhiều tầng.
#4. Quizz cho phỏng vấn Senior
Câu hỏi: Bạn cần tìm Top 10 bài viết có lượt xem cao nhất từ một mảng gồm 1 triệu bài viết trong bộ nhớ. Bạn sẽ giải quyết thế nào cho tối ưu nhất về RAM?
Trả lời:
Nhiều người sẽ nghĩ ngay đến việc dùng sort() toàn bộ mảng. Tuy nhiên, sort() tốn O(n log n) và chiếm rất nhiều RAM để copy mảng.
Giải pháp tối ưu là sử dụng cấu trúc dữ liệu Min-Heap (độ lớn 10).
- Duyệt qua từng bài viết một (O(n)).
- Nếu heap chưa đủ 10 phần tử, thêm vào.
- Nếu đã đủ 10, so sánh bài viết hiện tại với phần tử nhỏ nhất trong heap (phần tử ở gốc - O(1)). Nếu lớn hơn, thay thế nó và thực hiện re-heapify (O(log 10)). Cách này chỉ tốn O(n log 10), cực kỳ tiết kiệm bộ nhớ vì chỉ giữ đúng 10 phần tử trong RAM tại một thời điểm.
#5. Kết luận
Thuật toán không phải là những công thức khô khan. Hiểu bản chất dữ liệu giúp bạn có tư duy “nguyên tử” về code, từ đó viết ra những hệ thống không chỉ chạy đúng mà còn chạy cực kỳ thanh thoát.