DSA
Trang này chứa các mẹo và tài nguyên để chuẩn bị cho các cuộc phỏng vấn DSA.
Dưới đây là danh sách 30 câu hỏi phỏng vấn về Cấu trúc Dữ liệu và Thuật toán (DSA) từ cơ bản đến nâng cao, kèm theo câu trả lời ngắn gọn và dễ hiểu. Các câu hỏi được chia thành ba cấp độ: cơ bản, trung cấp và nâng cao.
Cấp độ cơ bản
Cấu trúc dữ liệu là gì? Trả lời: Cấu trúc dữ liệu là cách tổ chức và lưu trữ dữ liệu để có thể sử dụng hiệu quả trong các thao tác như truy cập, thêm, xóa, hoặc tìm kiếm.
Sự khác biệt giữa mảng (array) và danh sách liên kết (linked list) là gì? Trả lời: Mảng lưu trữ dữ liệu trong các ô nhớ liên tục, truy cập nhanh qua chỉ số (O(1)), nhưng thêm/xóa chậm (O(n)). Danh sách liên kết lưu trữ dữ liệu không liên tục qua các nút, thêm/xóa nhanh (O(1)), nhưng truy cập chậm (O(n)).
Stack và Queue khác nhau như thế nào? Trả lời: Stack hoạt động theo nguyên tắc LIFO (Last In, First Out), còn Queue theo FIFO (First In, First Out).
Thế nào là độ phức tạp thời gian (time complexity)? Trả lời: Độ phức tạp thời gian đo lường số lượng thao tác mà một thuật toán thực hiện dựa trên kích thước đầu vào, thường biểu diễn bằng ký hiệu Big-O.
Big-O của thuật toán tìm kiếm tuyến tính (linear search) là gì? Trả lời: O(n), vì nó kiểm tra từng phần tử trong danh sách.
Cây nhị phân (binary tree) là gì? Trả lời: Cây nhị phân là cấu trúc dữ liệu dạng cây mà mỗi nút có tối đa hai nút con (trái và phải).
Lợi ích của việc sử dụng con trỏ (pointer) trong danh sách liên kết là gì? Trả lời: Con trỏ cho phép liên kết các nút không cần bộ nhớ liên tục, giúp thêm/xóa phần tử dễ dàng.
Hàm băm (hash function) trong bảng băm (hash table) hoạt động thế nào? Trả lời: Hàm băm ánh xạ dữ liệu đầu vào thành một chỉ số trong bảng băm, giúp truy cập nhanh (thường O(1)).
Sự khác biệt giữa DFS và BFS là gì? Trả lời: DFS (Depth-First Search) duyệt sâu theo một nhánh trước (dùng stack), còn BFS (Breadth-First Search) duyệt theo mức (dùng queue).
Thuật toán sắp xếp nổi bọt (bubble sort) hoạt động thế nào? Trả lời: So sánh và hoán đổi các phần tử liền kề nếu chúng không đúng thứ tự, lặp lại cho đến khi danh sách được sắp xếp. Độ phức tạp: O(n²).
Cấp độ trung cấp
Làm thế nào để phát hiện vòng (cycle) trong danh sách liên kết? Trả lời: Dùng thuật toán Floyd’s Cycle-Finding (con trỏ nhanh-chậm): một con trỏ di chuyển nhanh gấp đôi, nếu gặp nhau thì có vòng.
Cây tìm kiếm nhị phân (BST) có đặc điểm gì? Trả lời: Mỗi nút có giá trị lớn hơn tất cả nút bên trái và nhỏ hơn tất cả nút bên phải, giúp tìm kiếm hiệu quả (O(log n)).
Big-O của thuật toán sắp xếp nhanh (quick sort) trong trường hợp trung bình và xấu nhất là gì? Trả lời: Trung bình: O(n log n), xấu nhất: O(n²) khi pivot không tối ưu.
Heap là gì và ứng dụng của nó? Trả lời: Heap là cây nhị phân mà nút cha luôn lớn hơn (max-heap) hoặc nhỏ hơn (min-heap) nút con. Ứng dụng: hàng đợi ưu tiên, thuật toán Dijkstra.
Làm thế nào để đảo ngược một danh sách liên kết? Trả lời: Dùng ba con trỏ (prev, current, next): thay đổi hướng liên kết của từng nút trong khi duyệt. Độ phức tạp: O(n).
Thuật toán tìm kiếm nhị phân (binary search) hoạt động thế nào? Trả lời: Chia đôi danh sách đã sắp xếp, so sánh với phần tử giữa, lặp lại cho đến khi tìm thấy hoặc không còn khoảng tìm kiếm. Độ phức tạp: O(log n).
Graph là gì? Có bao nhiêu cách biểu diễn graph? Trả lời: Graph là tập hợp các đỉnh và cạnh. Có hai cách biểu diễn: danh sách kề (adjacency list) và ma trận kề (adjacency matrix).
Khi nào xảy ra va chạm (collision) trong bảng băm và cách giải quyết? Trả lời: Va chạm xảy ra khi hai khóa ánh xạ cùng một chỉ số. Giải quyết bằng: chaining (danh sách liên kết) hoặc open addressing (probing).
Thuật toán sắp xếp trộn (merge sort) hoạt động thế nào? Trả lời: Chia danh sách thành các phần nhỏ, sắp xếp từng phần, rồi trộn lại. Độ phức tạp: O(n log n).
Trie là gì và ứng dụng của nó? Trả lời: Trie là cây tiền tố lưu trữ chuỗi ký tự, dùng trong tìm kiếm từ điển, tự động hoàn thành (autocomplete).
Cấp độ nâng cao
Thuật toán Dijkstra tìm đường ngắn nhất hoạt động thế nào? Trả lời: Dùng hàng đợi ưu tiên để chọn đỉnh có khoảng cách nhỏ nhất, cập nhật khoảng cách đến các đỉnh kề. Độ phức tạp: O((V + E) log V).
Cây AVL và cây đỏ-đen (red-black tree) khác nhau thế nào? Trả lời: Cả hai đều tự cân bằng, nhưng AVL nghiêm ngặt hơn (chênh lệch chiều cao tối đa 1), còn đỏ-đen linh hoạt hơn (dùng màu để cân bằng).
Làm thế nào để tìm phần tử lớn thứ k trong mảng? Trả lời: Dùng QuickSelect: chọn pivot, phân vùng mảng, lặp lại cho đến khi pivot ở vị trí k. Độ phức tạp trung bình: O(n).
Thuật toán Kruskal tìm cây khung nhỏ nhất (MST) hoạt động thế nào? Trả lời: Sắp xếp các cạnh theo trọng số, thêm từng cạnh vào MST nếu không tạo vòng (dùng Union-Find). Độ phức tạp: O(E log V).
Dynamic Programming (quy hoạch động) là gì? Trả lời: Là kỹ thuật chia bài toán thành các bài toán con, lưu kết quả để tránh tính toán lại (memoization hoặc tabulation).
Làm thế nào để giải bài toán dãy con tăng dài nhất (LIS)? Trả lời: Dùng DP: với mỗi phần tử, tìm dãy con tăng dài nhất kết thúc tại nó. Độ phức tạp: O(n²) hoặc O(n log n) với binary search.
Thuật toán A khác gì so với Dijkstra? Trả lời: A* dùng hàm heuristic để ưu tiên đường đi hứa hẹn hơn, nhanh hơn Dijkstra trong tìm kiếm đường ngắn nhất có mục tiêu.
Làm thế nào để kiểm tra một cây có phải là cây nhị phân tìm kiếm (BST) không? Trả lời: Duyệt theo thứ tự giữa (inorder), kiểm tra xem dãy kết quả có tăng dần không. Độ phức tạp: O(n).
Bloom Filter là gì và ứng dụng của nó? Trả lời: Bloom Filter là cấu trúc dữ liệu xác suất kiểm tra sự tồn tại của phần tử, có thể cho kết quả sai dương (false positive). Ứng dụng: kiểm tra URL trùng lặp, bộ lọc spam.
Làm thế nào để tìm đường đi Euler trong đồ thị? Trả lời: Kiểm tra số đỉnh có bậc lẻ: đồ thị có đường đi Euler nếu có 0 hoặc 2 đỉnh bậc lẻ. Dùng DFS để tìm đường đi.
Last updated