Chuyên đề thuật toán này không sắp xếp kiến thức theo thứ tự giáo trình mà được tổng hợp theo lộ trình luyện bài phỏng vấn thực tế: trước tiên làm rõ độ phức tạp, sau đó nắm các template thường gặp như binary search, two pointers, sliding window, DFS/BFS, backtracking, dynamic programming, greedy, Top K, cuối cùng dùng các bài về string, linked list, sorting và danh sách bài LeetCode để ôn tập.
Đặc điểm của bài toán Backtracking rất rõ ràng: đề bài yêu cầu bạn tìm tất cả phương án, tất cả đường đi, tất cả combination, hoặc thử các lựa chọn trong một tập hợp. Nó rất giống DFS, điểm khác biệt là Backtracking nhấn mạnh hơn vào “chọn -> đệ quy -> hủy lựa chọn”.
Khi viết Backtracking trong phỏng vấn, điều quan trọng nhất là trước tiên phải nêu rõ ý nghĩa của hàm đệ quy. Khi đã xác định rõ ý nghĩa của hàm, tham số, điều kiện kết thúc và thao tác hủy lựa chọn sẽ ít bị rối hơn.
Điểm dễ khiến bạn mắc lỗi nhất khi làm binary search không nằm ở ý tưởng mà ở việc xử lý biên. left, right, mid, điều kiện vòng lặp và giá trị trả về, chỉ cần chưa hiểu rõ ý nghĩa của một yếu tố là bạn rất dễ viết thành vòng lặp vô hạn hoặc bỏ sót đáp án.
Đừng học thuộc các ý tưởng thuật toán một cách tách rời. Cách hỏi hữu ích hơn trong phỏng vấn là: tín hiệu nào cho thấy nên dùng nó? Điểm nào trong template dễ viết sai nhất? Nếu interviewer thay đổi điều kiện, bạn nên bắt đầu điều chỉnh từ biến hoặc state nào?
Danh sách bài này được tổ chức theo ý tưởng. Mỗi nhóm đều đưa ra “tín hiệu nhận diện, template thường dùng, bài tiêu biểu, trọng tâm ôn tập”. Số lượng bài được giới hạn trong phạm vi đủ để đại diện cho template; hiểu rõ những bài này trước sẽ hiệu quả hơn việc máy móc giải thêm nhiều bài.
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.
Complexity analysis là bước đầu tiên trong phỏng vấn thuật toán. Interviewer không nhất thiết yêu cầu bạn trình bày phần chứng minh thật chặt chẽ, nhưng sẽ muốn bạn nói rõ: đoạn code này thực thi bao nhiêu lần, dùng thêm bao nhiêu space, quy mô input tăng thì điều gì xảy ra.
Trước hết cần làm rõ một điểm: complexity analysis thường xét xu hướng tăng trưởng khi quy mô input rất lớn, không phải runtime chính xác. O(n) không có nghĩa chắc chắn nhanh hơn O(nlogn), vì constant, quy mô dữ liệu, cache hit và chi tiết implementation đều ảnh hưởng đến thời gian thực tế. Tuy nhiên, trong phỏng vấn, trước tiên chỉ cần nói rõ growth order theo Big O, sau đó bổ sung một câu về giới hạn trong thực tế là đủ.
Dynamic programming khó không phải vì code luôn dài, mà vì chỉ cần state definition sai thì transition equation, initialization và thứ tự duyệt phía sau đều sai theo.
Trong phỏng vấn, đừng vội học thuộc template ngay từ đầu. Trước tiên hãy tự hỏi hai câu: bài toán này có thể tách thành các bài toán con không? Đáp án hiện tại có phụ thuộc vào các đáp án đã tính trước đó không? Nếu cả hai câu trả lời đều là có, hãy cân nhắc DP.
Bài toán Top K rất thường gặp trong phỏng vấn backend, vì vừa có thể kiểm tra thuật toán, vừa dễ liên hệ với các tình huống kỹ thuật: bảng xếp hạng, thống kê từ khóa phổ biến, median của data stream, mã lỗi xuất hiện nhiều nhất trong log đều có thể quy về Top K.
Với nhóm bài này, không nên chỉ ghi nhớ một cách viết. Interviewer thường hỏi tiếp: Nếu dữ liệu rất lớn thì phải làm thế nào? Nếu là data stream thì sao? Nếu yêu cầu K phần tử có tần suất cao nhất thì sao? Phương án sẽ thay đổi theo từng điều kiện.
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.
Đồ 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:
