Login

Phỏng vấn cấu trúc dữ liệu: array, linked list, hash map, stack, queue và cây

  • author-image

    Nguyễn Đình Cường

  • blog-tag
  • blog-comment 0 comment
  • created-date 09 Nov, 2026
blog-thumbnail

Cấu trúc dữ liệu là nền tảng của các bài phỏng vấn thuật toán. Bạn không cần cài đặt tất cả từ đầu mỗi lần, nhưng cần hiểu đặc điểm, chi phí từng thao tác và biết chọn đúng cấu trúc cho từng bài toán. Dưới đây là bản tổng hợp dễ nhớ.

Mảng (Array)

Các phần tử nằm liên tiếp trong bộ nhớ, truy cập theo chỉ số trong thời gian hằng số O(1). Chèn hoặc xóa ở giữa tốn O(n) vì phải dịch chuyển phần tử. Mảng động như ArrayList, list của Python hay mảng JavaScript tự mở rộng khi đầy, việc thêm vào cuối có chi phí trung bình O(1).

Danh sách liên kết (Linked List)

Mỗi nút giữ giá trị và con trỏ tới nút kế tiếp. Chèn hoặc xóa khi đã có nút trước đó chỉ O(1), nhưng tìm một phần tử phải duyệt O(n). Bài hay gặp: đảo ngược danh sách, phát hiện chu trình bằng hai con trỏ nhanh và chậm.

function reverse(head) {  let prev = null;  let cur = head;  while (cur) {    const next = cur.next;    cur.next = prev;    prev = cur;    cur = next;  }  return prev;}

Bảng băm (Hash Map / Hash Set)

Dùng hàm băm biến khóa thành chỉ số, cho phép tra cứu, thêm, xóa trung bình O(1). Trường hợp xấu nhất có thể lên O(n) khi nhiều khóa đụng độ, nhưng thực tế hiếm gặp. Hash map là công cụ quan trọng nhất trong phỏng vấn vì nó biến nhiều bài O(n²) thành O(n): đếm tần suất, tìm phần tử trùng, tìm cặp có tổng cho trước.

Ngăn xếp (Stack)

Vào sau ra trước (LIFO). Các thao tác push, pop, peek đều O(1). Ứng dụng: nút quay lại, hoàn tác, ngăn xếp gọi hàm, kiểm tra dấu ngoặc hợp lệ.

function isValid(s) {  const pairs = { ')': '(', ']': '[', '}': '{' };  const stack = [];  for (const ch of s) {    if (ch in pairs) {      if (stack.pop() !== pairs[ch]) return false;    } else {      stack.push(ch);    }  }  return stack.length === 0;}

Hàng đợi (Queue)

Vào trước ra trước (FIFO). Dùng cho xử lý tác vụ theo thứ tự, duyệt đồ thị theo chiều rộng (BFS), bộ đệm. Biến thể gồm hàng đợi hai đầu (deque) và hàng đợi ưu tiên (priority queue, thường cài bằng heap) để luôn lấy phần tử lớn nhất hoặc nhỏ nhất.

Cây (Tree)

Cây nhị phân mỗi nút có tối đa hai con. Cây tìm kiếm nhị phân (BST) giữ nút trái nhỏ hơn và nút phải lớn hơn, nên tìm kiếm trung bình O(log n) nếu cây cân bằng. Bạn nên biết ba cách duyệt theo chiều sâu (trước, giữa, sau) và duyệt theo tầng bằng hàng đợi.

function maxDepth(node) {  if (!node) return 0;  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));}

Đồ thị (Graph) ngắn gọn

Đồ thị gồm các đỉnh và cạnh, biểu diễn bằng danh sách kề hoặc ma trận kề. Hai cách duyệt cơ bản là DFS (dùng đệ quy hoặc ngăn xếp) và BFS (dùng hàng đợi, tìm đường đi ngắn nhất trên đồ thị không trọng số). Ví dụ đời thực: mạng xã hội, bản đồ đường đi, quan hệ phụ thuộc giữa các module.

Bảng so sánh nhanh

Cấu trúcTruy cậpTìmThêm/xóa
MảngO(1)O(n)O(n)
Linked listO(n)O(n)O(1) khi có vị trí
Hash mapkhông áp dụngO(1) trung bìnhO(1) trung bình
BST cân bằngkhông áp dụngO(log n)O(log n)

Cách chọn cấu trúc khi làm bài

  1. Cần tra cứu nhanh theo khóa: hash map hoặc hash set.
  2. Cần thứ tự vào ra: stack hoặc queue.
  3. Cần luôn lấy phần tử lớn nhất hoặc nhỏ nhất: heap.
  4. Cần dữ liệu có thứ tự và tìm kiếm nhanh: cây cân bằng hoặc mảng đã sắp xếp với tìm nhị phân.

Ba bài mẫu nên luyện cho mỗi nhóm

  • Mảng và hash map: hai số có tổng bằng target, nhóm các từ đảo chữ cái với nhau, tìm phần tử xuất hiện nhiều nhất.
  • Stack và queue: kiểm tra ngoặc hợp lệ, cài hàng đợi bằng hai ngăn xếp, tìm phần tử lớn hơn kế tiếp.
  • Cây và đồ thị: độ sâu cây nhị phân, duyệt theo tầng, đếm số vùng đảo trên lưới.

Khi làm bài, bạn nên nói thành tiếng ví dụ nhỏ trước, rồi mới viết code, và kiểm tra các trường hợp biên như mảng rỗng, một phần tử hoặc phần tử trùng lặp.

Kết luận

Hãy học bằng cách tự cài đặt mỗi cấu trúc một lần, rồi giải vài bài cho mỗi loại. Hiểu bản chất giúp bạn linh hoạt hơn nhiều so với việc nhớ đáp án có sẵn.

Nếu cần một lộ trình học thuật toán và cấu trúc dữ liệu có bài tập, hãy xem các khóa học tại codebem.com.

author_photo
Nguyễn Đình Cường

0 comment