Thư Viện Câu Hỏi Phỏng Vấn

Tổng hợp các câu hỏi tuyển dụng thực tế theo nhiều cấp độ từ Entry đến Expert để bạn tự tin chinh phục nhà tuyển dụng.

Tất cả Full-stack, Web & Mobile Coding & Data structures System design & Architecture
Tất cả công nghệ Arrays (19) Backtracking (7) Big-O Notation (16) Binary Tree (19) Bit Manipulation (9) Blockchain (42) Data Structures (69) Divide & Conquer (2) Dynamic Programming (10) Fibonacci Series (4) Graph Theory (19) Greedy Algorithms (7) Hash Tables (25) Heaps and Maps (10) Linked Lists (17) Queues (11) Recursion (5) Searching (18) Sorting (13) Stacks (10) Strings (17) Trees (31) Trie (8)
Bộ lọc: Mọi cấp độ Entry Junior Middle Senior Expert
241

Làm thế nào để phát hiện chu trình (cycle) trong đồ thị có hướng (Directed Graph)?

Senior

Có thể sử dụng thuật toán duyệt đồ thị DFS (Depth-First Search) kết hợp kỹ thuật tô màu các đỉnh (hoặc sử dụng Recursion Stack):

  • Trạng thái 3 màu:
    • Trắng (Unvisited): Đỉnh chưa được duyệt.
    • Xám (Visiting): Đỉnh đang nằm trong nhánh đệ quy hiện tại (chưa duyệt xong các đỉnh kề).
    • Đen (Visited): Đỉnh và toàn bộ các đỉnh kề của nó đã duyệt xong.
  • Phát hiện chu trình: Trong quá trình duyệt DFS, nếu gặp một đỉnh kề đang ở trạng thái Xám, điều đó có nghĩa là có một cạnh ngược (back edge) trỏ về tổ tiên của nó trên nhánh đệ quy, tức là đồ thị tồn tại chu trình.
242

Hãy giải thích cơ chế của kỹ thuật Sliding Window (Cửa sổ trượt) trên mảng dữ liệu?

Senior

Sliding Window được dùng để tìm kiếm một phân đoạn con (subarray) thỏa mãn điều kiện nhất định trên mảng mà không cần tính toán lại từ đầu các phần tử trùng lặp:

  • Cơ chế: Duy trì một \'cửa sổ\' được định nghĩa bởi hai chỉ số start và end. Khi mở rộng cửa sổ sang phải (end++), ta cộng thêm phần tử mới vào kết quả tạm thời. Khi điều kiện bị vi phạm, ta thu hẹp cửa sổ từ bên trái (start++) và trừ bớt giá trị của phần tử bị loại bỏ.
  • Hiệu năng: Giúp chuyển đổi các thuật toán vét cạn độ phức tạp O(n^2) thành thuật toán tuyến tính O(n) vì mỗi phần tử chỉ được duyệt qua tối đa 2 lần.
243

Hãy phân biệt sự khác nhau giữa tiếp cận Bottom-Up (Tabulation) và Top-Down (Memoization) trong Quy hoạch động?

Senior
  • Top-Down (Memoization): Bắt đầu giải quyết từ bài toán lớn nhất bằng đệ quy. Trong quá trình chạy, kết quả của các bài toán con sẽ được lưu lại (thường trong HashMap hoặc mảng). Khi gặp lại bài toán con đó, ta trả về ngay kết quả đã lưu mà không cần tính lại. Dễ hiểu và tự nhiên nhưng tốn chi phí gọi hàm đệ quy trên Stack.
  • Bottom-Up (Tabulation): Bắt đầu giải quyết từ các bài toán con nhỏ nhất trước, điền kết quả vào một bảng (mảng 1D hoặc 2D) bằng vòng lặp, sau đó sử dụng các kết quả này để tính toán dần lên bài toán lớn hơn. Tránh được việc tràn Stack và thường tối ưu hơn về không gian bộ nhớ.
    • 244

    Bài toán cái túi (0/1 Knapsack Problem) được giải quyết bằng Quy hoạch động như thế nào?

    Senior

    Bài toán yêu cầu chọn các đồ vật có khối lượng và giá trị sao cho tổng khối lượng không vượt quá W và tổng giá trị lớn nhất:

    1. Trạng thái: Gọi dp[i][w] là giá trị lớn nhất có thể đạt được khi chọn trong i đồ vật đầu tiên với giới hạn khối lượng là w.
    2. Công thức truy hồi: Với đồ vật thứ i có khối lượng weight[i] và giá trị val[i]:
      • Nếu weight[i] > w: Không thể chọn đồ vật này -> dp[i][w] = dp[i-1][w].
      • Nếu weight[i] <= w: Ta chọn giá trị lớn hơn giữa việc lấy hoặc không lấy đồ vật -> dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + val[i]).
    3. Kết quả: Nằm ở ô dp[n][W] với độ phức tạp thời gian là O(n*W).
    245

    Sự khác biệt thế nào giữa các thuật toán sắp xếp ổn định (Stable Sort) và không ổn định (Unstable Sort)? Tại sao tính chất này quan trọng?

    Senior
  • Stable Sort (Sắp xếp ổn định): Bảo toàn thứ tự xuất hiện ban đầu của các phần tử có giá trị bằng nhau sau khi sắp xếp. Ví dụ: Merge Sort, Insertion Sort, Bubble Sort.
  • Unstable Sort (Sắp xếp không ổn định): Có thể làm thay đổi thứ tự ban đầu của các phần tử bằng nhau. Ví dụ: Quick Sort, Heap Sort.
  • Tầm quan trọng: Rất quan trọng khi bạn cần sắp xếp dữ liệu nhiều lần theo nhiều tiêu chí khác nhau. Ví dụ: Sắp xếp danh sách nhân viên theo \'Tên\' (tăng dần), sau đó sắp xếp tiếp theo \'Phòng ban\'. Nếu dùng thuật toán ổn định, các nhân viên trong cùng một phòng ban vẫn giữ nguyên thứ tự sắp xếp theo tên trước đó.
    • 246

    Làm thế nào để thuật toán Quick Sort đạt hiệu năng tốt nhất và tránh rơi vào trường hợp xấu nhất O(n^2)?

    Senior

    Trường hợp xấu nhất O(n^2) của Quick Sort xảy ra khi mảng đầu vào đã được sắp xếp (hoặc ngược lại) và ta liên tục chọn phần tử chốt (pivot) ở vị trí biên (đầu hoặc cuối mảng), dẫn đến việc phân chia mảng bị lệch hoàn toàn (một bên 0 phần tử, một bên n-1 phần tử).

    • Giải pháp khắc phục:
      1. Chọn Pivot ngẫu nhiên (Randomized Quick Sort): Chọn pivot ngẫu nhiên trong khoảng mảng đang xét thay vì cố định.
      2. Kỹ thuật Median-of-Three: Chọn pivot là trung vị của ba phần tử: đầu mảng, giữa mảng và cuối mảng. Kỹ thuật này giúp phân chia mảng cân bằng nhất có thể.
      3. Xáo trộn mảng (Shuffle): Thực hiện xáo trộn ngẫu nhiên mảng đầu vào trước khi tiến hành sắp xếp.
    247

    Hợp đồng thông minh (Smart Contract) là gì và làm thế nào để ngăn chặn lỗ hổng Reentrancy Attack trong Solidity?

    Senior

    Smart Contract là chương trình tự thực thi mã nguồn được lưu trữ và chạy trên blockchain khi các điều kiện thỏa thuận được đáp ứng.

    • Reentrancy Attack: Xảy ra khi một hợp đồng gọi đến một hợp đồng bên ngoài chưa tin cậy trước khi nó cập nhật trạng thái số dư (state) của chính nó. Hợp đồng độc hại có thể gọi ngược lại (re-enter) hàm rút tiền liên tục để rút hết quỹ trước khi giao dịch ban đầu kịp cập nhật số dư.
    • Phòng chống:
      1. Checks-Effects-Interactions Pattern: Luôn thực hiện kiểm tra điều kiện (checks) trước, sau đó thay đổi trạng thái số dư trong bộ nhớ (effects), rồi mới thực hiện chuyển tiền (interactions).
      2. ReentrancyGuard: Sử dụng modifier nonReentrant của OpenZeppelin để khóa hàm trong suốt quá trình thực thi.
    248

    Sự khác biệt giữa cây AVL và cây Đỏ-Đen (Red-Black Tree)? Khi nào nên chọn loại nào?

    Senior

    Cả hai đều là cây nhị phân tìm kiếm tự cân bằng nhưng có sự khác biệt về mức độ cân bằng:

    • Cây AVL: Cân bằng nghiêm ngặt hơn (chênh lệch chiều cao tối đa là 1). Do đó, cây AVL có tốc độ tìm kiếm nhanh hơn vì chiều cao tối ưu hơn. Tuy nhiên, chi phí tự cân bằng (xoay cây) khi thêm/xóa phần tử rất đắt.
    • Cây Đỏ-Đen: Cân bằng lỏng lẻo hơn. Thao tác thêm/xóa nhanh hơn AVL vì số lần xoay cây tối đa ít hơn. Tốc độ tìm kiếm chậm hơn một chút so với AVL.
    • Lựa chọn: Chọn AVL cho các ứng dụng có tần suất đọc/tìm kiếm dữ liệu lớn hơn nhiều so với ghi. Chọn Red-Black cho các ứng dụng có tần suất thêm/xóa dữ liệu thường xuyên (ví dụ: Map và Set trong C++ STL được cài đặt bằng cây Đỏ-Đen).
    249

    Khái niệm Load Factor (hệ số tải) trong Hash Table là gì và tầm quan trọng của nó khi Rehashing?

    Senior

    Hệ số tải (Load Factor - alpha) là tỷ lệ giữa số lượng phần tử hiện có (n) chia cho dung lượng của bảng băm (k): alpha = n/k.

    • Tầm quan trọng: Khi hệ số tải vượt quá một ngưỡng nhất định (thường là 0.75), xác suất xảy ra xung đột (collision) tăng cao, làm giảm hiệu năng tìm kiếm từ O(1) về O(n).
    • Rehashing: Khi đạt ngưỡng, Hash Table sẽ tự động tăng kích thước bảng băm (thường gấp đôi) và tính toán lại vị trí (hash index) cho toàn bộ phần tử cũ sang bảng mới. Điều này giúp giữ hệ số tải luôn thấp để đảm bảo tốc độ truy cập luôn đạt O(1).
    250

    Thuật toán tìm kiếm chuỗi KMP (Knuth-Morris-Pratt) hoạt động như thế nào để đạt độ phức tạp O(n + m)?

    Senior

    Thuật toán KMP tìm kiếm chuỗi mẫu (pattern) trong chuỗi văn bản (text) mà không cần quay lui con trỏ của chuỗi văn bản khi gặp ký tự không khớp:

    1. Mảng tiền tố (LPS Array): KMP xây dựng trước một mảng LPS (Longest Proper Prefix which is also Suffix). LPS[i] lưu độ dài của tiền tố khớp với hậu tố dài nhất của chuỗi mẫu tính đến chỉ số i.
    2. So khớp: Khi duyệt chuỗi văn bản, nếu gặp ký tự không khớp tại vị trí j của chuỗi mẫu, ta không lùi con trỏ chuỗi văn bản về mà dịch chuyển con trỏ chuỗi mẫu sang vị trí LPS[j-1] để tiếp tục so sánh. Điều này tránh được các phép so sánh trùng lặp vô ích.
    251

    Làm thế nào để đảo ngược một Danh sách liên kết đơn (Singly Linked List) bằng phương pháp lặp (Iterative)?

    Senior

    Để đảo ngược danh sách liên kết đơn tại chỗ, ta sử dụng 3 con trỏ prev, curr, và next:

    1. Khởi tạo: prev = null, curr = head.
    2. Duyệt qua danh sách cho đến khi curr == null: a. Lưu node tiếp theo: next = curr.next. b. Đảo ngược liên kết của node hiện tại: curr.next = prev. c. Dịch chuyển hai con trỏ tiến lên: prev = curr, curr = next.
    3. Khi vòng lặp kết thúc, gán head = prev để làm node đầu mới. Độ phức tạp thời gian là O(n) và độ phức tạp không gian là O(1).
    252

    Làm thế nào để kiểm tra một Cây nhị phân có phải là Cây nhị phân tìm kiếm (BST - Binary Search Tree) hợp lệ hay không?

    Senior

    Một Cây nhị phân tìm kiếm (BST) hợp lệ nếu mọi node đều thỏa mãn điều kiện: Tất cả các node thuộc cây con bên trái phải có giá trị nhỏ hơn node hiện tại, và tất cả các node thuộc cây con bên phải phải có giá trị lớn hơn node hiện tại.

    • Sai lầm phổ biến: Chỉ kiểm tra cục bộ xem node con bên trái có nhỏ hơn node cha và node con bên phải có lớn hơn node cha hay không. Cách này sai nếu node con bên trái của con bên phải lại nhỏ hơn node gốc.
    • Giải pháp tối ưu: Duyệt cây và truyền kèm phạm vi giá trị hợp lệ [min, max] cho từng node:
      1. Node gốc bắt đầu với phạm vi [-infinity, +infinity].
      2. Khi đi sang con bên trái, cập nhật giá trị max bằng giá trị của node hiện tại: [min, node.val].
      3. Khi đi sang con bên phải, cập nhật giá trị min bằng giá trị của node hiện tại: [node.val, max].
      4. Nếu giá trị của bất kỳ node nào nằm ngoài phạm vi của nó, trả về false. Độ phức tạp thời gian là O(n) và độ phức tạp không gian là O(h) với h là chiều cao của cây do đệ quy.
    253

    Độ phức tạp thời gian khấu hao (Amortized Time Complexity) là gì? Cho ví dụ thực tế trong cấu trúc dữ liệu?

    Senior

    Độ phức tạp thời gian khấu hao (Amortized Complexity) là công cụ phân tích hiệu năng trung bình của một chuỗi các thao tác liên tiếp trên một cấu trúc dữ liệu, trong đó có một vài thao tác cực kỳ tốn thời gian nhưng tần suất xuất hiện rất hiếm, trong khi đa số thao tác khác lại cực kỳ nhanh.

    • Khác biệt với Average Case: Khấu hao đảm bảo hiệu năng trung bình của chuỗi thao tác trong trường hợp xấu nhất (Worst-Case), chứ không dựa trên phân phối xác suất ngẫu nhiên của dữ liệu.
    • Ví dụ thực tế (ArrayList/Vector):
      • Thao tác thêm phần tử vào cuối push_back() thường tốn O(1) nếu mảng còn chỗ trống.
      • Khi mảng đầy, ta phải tạo mảng mới có dung lượng gấp đôi và sao chép toàn bộ n phần tử cũ sang, tốn O(n).
      • Tuy nhiên, thao tác tốn O(n) này chỉ xảy ra sau n lần thêm phần tử thành công. Tổng chi phí cho n lần thêm là n * O(1) + O(n) = O(n). Chia trung bình cho n thao tác, chi phí mỗi lần chỉ là O(1). Ta nói độ phức tạp khấu hao của push_back là O(1).
    254

    Hàng đợi ưu tiên (Priority Queue) hoạt động như thế nào và sự khác biệt khi triển khai bằng Heap so với Mảng/Danh sách liên kết?

    Senior

    Hàng đợi ưu tiên là cấu trúc dữ liệu mà mỗi phần tử được gắn với một độ ưu tiên. Phần tử có độ ưu tiên cao nhất luôn được lấy ra trước, bất kể thời điểm thêm vào.

    • Triển khai bằng Mảng/Danh sách liên kết:
      • Nếu giữ mảng không sắp xếp: Thêm phần tử tốn O(1), lấy phần tử lớn nhất tốn O(n) vì phải quét toàn bộ mảng.
      • Nếu giữ mảng sắp xếp: Thêm phần tử tốn O(n) vì phải dịch chuyển các phần tử khác, lấy ra tốn O(1).
    • Triển khai bằng Binary Heap (Tối ưu nhất):
      • Heap là cây nhị phân gần hoàn chỉnh thỏa mãn tính chất Heap (cha luôn lớn hơn hoặc nhỏ hơn con).
      • Thao tác thêm phần tử enqueue tốn O(log n) nhờ quá trình sift-up.
      • Thao tác lấy ra phần tử đầu dequeue tốn O(log n) nhờ quá trình sift-down.
      • Xem phần tử đầu peek tốn O(1).
      • Đây là sự cân bằng tuyệt vời giúp quản lý các tác vụ ưu tiên động cực kỳ hiệu quả.
    255

    Cấu trúc dữ liệu Heap (Min-Heap / Max-Heap) là gì? Thao tác thêm phần tử (Heapify-up) và xóa phần tử gốc (Heapify-down) có độ phức tạp là bao nhiêu?

    Senior

    Heap là một cây nhị phân gần như hoàn chỉnh (thường được biểu diễn dưới dạng mảng để tiết kiệm bộ nhớ) thỏa mãn tính chất:

    • Max-Heap: Giá trị của node cha luôn lớn hơn hoặc bằng giá trị các con của nó (Gốc là giá trị lớn nhất).
    • Min-Heap: Giá trị của node cha luôn nhỏ hơn hoặc bằng giá trị các con của nó (Gốc là giá trị nhỏ nhất).
    • Thao tác Thêm (Heapify-up): Phần tử mới được chèn vào cuối cây (cuối mảng). Sau đó, nó được so sánh với cha và hoán vị đi lên nếu vi phạm thuộc tính Heap. Chiều cao tối đa của cây là log n, nên độ phức tạp là O(log n).
    • Thao tác Xóa gốc (Heapify-down): Thay thế phần tử gốc bằng phần tử cuối cùng của mảng, sau đó xóa phần tử cuối cùng này. Tiếp theo, so sánh gốc mới với các con và hoán vị đi xuống với con lớn hơn (hoặc nhỏ hơn đối với Min-Heap) để tái lập cấu trúc Heap. Độ phức tạp là O(log n).

    vừa nâng cấp PRO khóa 1 phút trước   Tìm hiểu khóa học