Khi làm bài về cấu trúc dữ liệu, không nên chỉ luyện từ Easy đến Hard theo độ khó. Cách vững hơn là phân loại dạng bài theo từng cấu trúc: array tập trung vào index và khoảng, linked list tập trung vào pointer, stack và queue tập trung vào ràng buộc thứ tự, tree và graph tập trung vào traversal, heap tập trung vào priority, hash table tập trung vào định vị nhanh.
Hệ thống kiến thức cấu trúc dữ liệu này tổ chức nội dung theo các chủ đề phỏng vấn và tình huống kỹ thuật Java backend: trước tiên hiểu dữ liệu được lưu trữ thế nào, sau đó tìm hiểu complexity của các thao tác thường gặp, cuối cùng liên hệ các cấu trúc với những vấn đề kỹ thuật như Java Collections, MySQL index, Redis, cache và message queue.
Nếu chưa từng dùng Bloom Filter, có lẽ bạn cũng đã nghe nói về nó.
Bloom Filter chủ yếu được dùng để giải quyết bài toán xác định sự tồn tại trong tập dữ liệu lớn. Nó rất phù hợp với trường hợp cần xác định một phần tử có tồn tại trong một tập dữ liệu lớn hay không và chấp nhận sai số nhỏ (ví dụ cache penetration, deduplication dữ liệu lớn).
Đồ thị là một cấu trúc phi tuyến tương đối phức tạp. Tại sao nói đồ thị tương đối phức tạp?
Dựa trên nội dung trước đó, chúng ta biết:
Hash table (còn gọi là bảng băm) có giá trị cao trong phỏng vấn vì một mặt gắn với việc tìm kiếm nhanh và đếm trong các bài toán thuật toán, mặt khác gắn với Java HashMap, cache, loại bỏ trùng lặp và định tuyến sharding trong distributed system.
Câu hỏi này xoay quanh việc: làm thế nào ánh xạ nhanh một key tới chỉ số array, đồng thời vẫn duy trì hiệu suất truy vấn chấp nhận được khi xảy ra collision, mở rộng dung lượng và xuất hiện dữ liệu ở trường hợp cực đoan.
LRU là viết tắt của Least Recently Used, nghĩa là ít được sử dụng gần đây nhất. Khi cache đầy, dữ liệu lâu nhất chưa được truy cập sẽ bị loại bỏ.
Trong các buổi phỏng vấn, tự viết LRU là câu hỏi rất thường gặp vì nó kết hợp hash table và doubly linked list: hash table chịu trách nhiệm tìm node trong O(1), còn doubly linked list chịu trách nhiệm di chuyển node và xóa node cuối trong O(1).
Skip list có thể được hiểu là “sorted linked list có multi-level index”. Việc query một sorted linked list thông thường cần quét từ đầu đến cuối, complexity là O(n); skip list thêm nhiều tầng index phía trên linked list, khi query có thể nhanh chóng bỏ qua một nhóm node từ các tầng cao rồi lần lượt đi xuống.
Trie, còn gọi là cây tiền tố hoặc cây từ điển, phù hợp để xử lý các bài toán prefix matching trên lượng lớn chuỗi. Search suggestions, tra cứu từ điển, lọc từ nhạy cảm và prefix matching trong routing đều có thể thấy ứng dụng của nó.
Ý tưởng cốt lõi của nó rất trực tiếp: tách chuỗi theo từng ký tự và chia sẻ các prefix giống nhau. Ví dụ, app, apple, apply sẽ dùng chung đường đi a -> p -> p.
Union-find chuyên giải quyết các vấn đề về “phân nhóm” và “tính liên thông”. Hai phần tử có thuộc cùng một nhóm không? Sau khi hợp nhất hai set còn bao nhiêu connected components? Thêm một edge vào graph có tạo thành cycle không? Tất cả đều có thể xử lý bằng union-find.
Trong phỏng vấn, code không dài, nhưng nếu viết find không tốt thì sẽ ảnh hưởng trực tiếp đến complexity.
