DFS và BFS là nền tảng của các bài toán về cây, đồ thị và ma trận. Trong phỏng vấn, người phỏng vấn sẽ không chỉ hỏi “DFS là gì”, mà thường đưa cho bạn một bài toán đảo, bài toán phụ thuộc khóa học, số bước ngắn nhất hoặc duyệt cây nhị phân theo tầng, rồi yêu cầu bạn chọn cách tìm kiếm và xử lý biên.
Code của Greedy Algorithm thường không dài, điểm khó nằm ở việc giải thích tại sao lựa chọn hiện tại không ảnh hưởng đến nghiệm tối ưu toàn cục. Trong phỏng vấn, nếu chỉ viết code mà không giải thích chiến lược Greedy, bạn rất dễ bị hỏi tiếp đến bí.
Có thể nhận diện như sau: nếu bài toán có thể giải bằng cách sorting hoặc duy trì một boundary tối ưu hiện tại, mỗi bước đưa ra một lựa chọn cục bộ và lựa chọn đó không phá vỡ nghiệm tối ưu ở các bước sau, bạn có thể thử dùng Greedy.
Two pointers và sliding window thường được ôn cùng nhau, nhưng vấn đề chúng giải quyết không hoàn toàn giống nhau. Two pointers thiên về một chiến lược di chuyển, còn sliding window nhấn mạnh việc duy trì trạng thái trong một đoạn liên tiếp.
Một cách phán đoán thực tế: nếu bài toán quan tâm đến quan hệ giữa hai vị trí, hãy nghĩ đến two pointers trước; nếu bài toán quan tâm đến subarray hoặc substring liên tiếp và cần duy trì điều kiện trong window, hãy nghĩ đến sliding window trước.
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).
Heap là một tree thỏa mãn các điều kiện sau:
Giá trị của mỗi node trong heap lớn hơn hoặc bằng (hoặc nhỏ hơn hoặc bằng) giá trị của mọi node trong subtree. Nói cách khác, giá trị của bất kỳ node nào cũng lớn hơn hoặc bằng (hoặc nhỏ hơn hoặc bằng) giá trị của mọi child node.
Red-black tree là một self-balancing binary search tree. Nó được Rudolf Bayer phát minh vào năm 1972 và khi đó được gọi là balanced binary B-tree (symmetric binary B-trees). Sau đó, vào năm 1978, Leo J. Guibas và Robert Sedgewick đã sửa đổi thành “red-black tree” như ngày nay.
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.
Tree là một data structure giống cây trong đời sống, nhưng bị đảo ngược. Mọi tree không rỗng chỉ có một root node.
Một tree có các đặc điểm sau:
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.
Thread A đã lấy được resource 1, thread B cũng đã lấy được resource 2. Tiếp theo, thread A muốn tiếp tục chạy thì cần resource 2; thread B muốn tiếp tục chạy thì lại cần resource 1.
Hai thread đều không ném exception, cũng không phải CPU bị chạy hết công suất. Hiện tượng nhìn thấy trên production có thể chỉ là vài request không trả về trong thời gian dài, còn worker thread trong thread pool dần bị chiếm hết.
