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à đủ.
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.
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.
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.
LeetCode: Cho hai linked list không rỗng biểu diễn hai số nguyên không âm. Các chữ số được lưu theo thứ tự ngược; mỗi node chỉ lưu một chữ số. Hãy cộng hai số và trả về một linked list mới.
Bạn có thể giả định rằng ngoài số 0, hai số này đều không bắt đầu bằng 0.
