Những thuật toán cần học trước khi đi phỏng vấn lập trình

Khi chuẩn bị cho các buổi phỏng vấn lập trình, nhiều người tập trung quá nhiều vào việc giải thật nhiều bài LeetCode mà bỏ qua nền tảng quan trọng: hiểu bản chất của thuật toán và cấu trúc dữ liệu. Thực tế, các công ty không đánh giá bạn chỉ dựa trên việc “viết code chạy đúng”. Họ muốn biết bạn: Chọn giải pháp như thế nào, tối ưu ra sao, giải thích được logic và độ phức tạp của thuật toán. Bài viết này tổng hợp những kiến thức cốt lõi bạn cần nắm vững trước khi bước vào phỏng vấn, dựa trên lộ trình kinh điển từ Coding Interview University .

{"type":"doc","content":[{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"1. Độ phức tạp thuật toán (Big-O)"}]},{"type":"paragraph","content":[{"type":"text","text":"Đây là nền tảng quan trọng nhất và cũng là thứ nhiều người bỏ qua."}]},{"type":"paragraph","content":[{"type":"text","text":"Big-O giúp bạn đo lường:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Thời gian chạy của thuật toán"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Mức độ tiêu tốn bộ nhớ"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Bạn cần hiểu rõ các mức cơ bản:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(1): thời gian hằng số"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(log n): tăng rất chậm"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(n): tuyến tính"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(n log n): thường thấy ở thuật toán tốt"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(n²): kém hiệu quả với dữ liệu lớn"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Điểm quan trọng không phải là nhớ công thức, mà là:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Nhìn code và nhận ra độ phức tạp"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"So sánh được hai giải pháp với nhau"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Trong phỏng vấn, việc bạn nói được “giải pháp này là O(n) và có thể cải thiện xuống O(log n)” thường quan trọng hơn việc code nhanh."}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"2. Cấu trúc dữ liệu cơ bản"}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Array (Mảng)"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Truy cập theo index rất nhanh: O(1)"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Chèn/xóa ở giữa: O(n)"}]}]}]},{"type":"image","attrs":{"src":"https://cropycnghyhgkxgxdfkh.supabase.co/storage/v1/object/public/media_portfolio/media/ff22ed8e-7113-4142-86a7-c465b83b5852.png","alt":null,"title":null,"width":381,"height":285.75}},{"type":"paragraph","content":[{"type":"text","text":"Bạn sẽ dùng array trong hầu hết các bài toán."}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Linked List"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Chèn/xóa nhanh: O(1)"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Truy cập chậm: O(n)"}]}]}]},{"type":"image","attrs":{"src":"https://cropycnghyhgkxgxdfkh.supabase.co/storage/v1/object/public/media_portfolio/media/b36334d8-fc11-48d0-8190-7b39693b3fae.png","alt":null,"title":null,"width":null,"height":null}},{"type":"paragraph","content":[{"type":"text","text":"Quan trọng không phải là dùng trong thực tế, mà là hiểu cách quản lý con trỏ và bộ nhớ."}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Stack"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Hoạt động theo nguyên tắc LIFO"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Push/Pop: O(1)"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Ứng dụng:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Kiểm tra dấu ngoặc"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Duyệt DFS"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Undo/Redo"}]}]}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Queue "}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Hoạt động theo nguyên tắc FIFO"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Enqueue/Dequeue: O(1)"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Ứng dụng:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"BFS"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Xử lý hàng đợi"}]}]}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Hash Table"}]},{"type":"paragraph","content":[{"type":"text","text":"Đây là cấu trúc dữ liệu quan trọng nhất trong phỏng vấn."}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Truy xuất trung bình: O(1)"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Dùng để:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Kiểm tra trùng lặp"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Đếm tần suất"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Lưu cache"}]}]}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Phần lớn bài toán “tối ưu từ O(n²) xuống O(n)” đều dùng hash table."}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"3. Thuật toán tìm kiếm"}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Linear Search"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Duyệt từng phần tử"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(n)"}]}]}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Binary Search"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"O(log n)"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Áp dụng cho dữ liệu đã sắp xếp"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Đây là dạng bài xuất hiện rất thường xuyên:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Tìm phần tử"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Tìm vị trí đầu/cuối"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Tìm trong mảng xoay"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Bạn cần hiểu rõ điều kiện áp dụng và cách triển khai."}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"4. Cây (Tree)"}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Binary Tree"}]},{"type":"paragraph","content":[{"type":"text","text":"Là cấu trúc nền tảng cho nhiều bài toán."}]},{"type":"paragraph","content":[{"type":"text","text":"Bạn cần nắm:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"DFS:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Preorder"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Inorder"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Postorder"}]}]}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"BFS"}]}]}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Binary Search Tree (BST)"}]},{"type":"paragraph","content":[{"type":"text","text":"Nguyên tắc:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Node bên trái nhỏ hơn root"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Node bên phải lớn hơn root"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Giúp tối ưu tìm kiếm xuống O(log n) trong trường hợp cân bằng."}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"5. Heap và Priority Queue"}]},{"type":"paragraph","content":[{"type":"text","text":"Heap thường được dùng khi:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Cần lấy phần tử lớn nhất hoặc nhỏ nhất nhanh"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Độ phức tạp:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Insert: O(log n)"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Extract: O(log n)"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Các dạng bài phổ biến:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Top K elements"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Kth largest"}]}]}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"6. Thuật toán sắp xếp"}]},{"type":"paragraph","content":[{"type":"text","text":"Bạn không cần thuộc tất cả, nhưng cần hiểu bản chất."}]},{"type":"paragraph","content":[{"type":"text","text":"Quan trọng nhất:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Merge Sort: O(n log n)"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Quick Sort: trung bình O(n log n)"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Bạn nên hiểu:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Khi nào dùng"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Ưu nhược điểm"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Tính ổn định của thuật toán"}]}]}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"7. Đồ thị (Graph)"}]},{"type":"paragraph","content":[{"type":"text","text":"Đây là phần nâng cao nhưng rất phổ biến trong phỏng vấn."}]},{"type":"paragraph","content":[{"type":"text","text":"Bạn cần hiểu:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Cách biểu diễn:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Danh sách kề"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Ma trận kề"}]}]}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Duyệt:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"BFS"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"DFS"}]}]}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Ứng dụng:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Tìm đường đi"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Phân tích mạng"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Dependency"}]}]}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"8. Đệ quy và Quy hoạch động"}]},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Đệ quy"}]},{"type":"paragraph","content":[{"type":"text","text":"Là nền tảng để giải:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Tree"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Backtracking"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Bạn cần hiểu:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Base case"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Recursive case"}]}]}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":3},"content":[{"type":"text","text":"Quy hoạch động (Dynamic Programming)"}]},{"type":"paragraph","content":[{"type":"text","text":"Áp dụng khi:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Bài toán có subproblem lặp lại"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Các dạng phổ biến:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Fibonacci"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Knapsack"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Longest subsequence"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Đây là phần khó, nhưng cũng là phần tạo khác biệt trong phỏng vấn."}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"9. Nguyên tắc học quan trọng"}]},{"type":"paragraph","content":[{"type":"text","text":"Một sai lầm phổ biến là:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Học lý thuyết trước"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Đợi “học xong hết” rồi mới làm bài"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Cách này không hiệu quả."}]},{"type":"paragraph","content":[{"type":"text","text":"Bạn nên:"}]},{"type":"bulletList","content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Học một chủ đề"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Làm ngay 2–3 bài liên quan"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Quay lại làm thêm sau đó"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Theo tài liệu gốc, điều quan trọng nhất là:"}]},{"type":"blockquote","content":[{"type":"paragraph","content":[{"type":"text","text":"Bạn không được tuyển dụng vì kiến thức, mà vì khả năng áp dụng kiến thức vào giải quyết vấn đề"}]}]},{"type":"horizontalRule"},{"type":"heading","attrs":{"level":2},"content":[{"type":"text","text":"10. Kết luận"}]},{"type":"paragraph","content":[{"type":"text","text":"Chuẩn bị cho phỏng vấn lập trình không phải là học càng nhiều càng tốt, mà là học đúng trọng tâm và luyện tập có hệ thống."}]},{"type":"paragraph","content":[{"type":"text","text":"Một lộ trình hợp lý:"}]},{"type":"orderedList","attrs":{"start":1,"type":null},"content":[{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Big-O"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Array và Hash Table"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Binary Search"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Linked List"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Stack và Queue"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Tree"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Heap"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Graph"}]}]},{"type":"listItem","content":[{"type":"paragraph","content":[{"type":"text","text":"Dynamic Programming"}]}]}]},{"type":"paragraph","content":[{"type":"text","text":"Nếu bạn nắm vững những phần này và luyện tập đủ, bạn đã có nền tảng rất tốt để vượt qua các vòng phỏng vấn kỹ thuật."}]}]}