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

Bộ lọc: Entry

2701

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 đó.

2702

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.

2703

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.

2704

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).

2705

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).

2706

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:

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.
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.

2707

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:

Khởi tạo: prev = null, curr = head.
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.
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).

2708

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.

2709

Độ 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).

2710

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ả.

2711

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).

2712

Làm thế nào để kiểm tra một số nguyên dương N có phải là lũy thừa của 2 (Power of Two) chỉ bằng các phép toán Bitwise trong O(1)?

Senior

Một số nguyên dương N là lũy thừa của 2 nếu và chỉ nếu biểu diễn nhị phân của nó chỉ chứa duy nhất một bit 1 (ví dụ: 4 = 100_2, 8 = 1000_2, 16 = 10000_2).

Giải pháp Bitwise: Sử dụng biểu thức (N & (N - 1)) == 0.
Giải thích cơ chế:
- Số N (lũy thừa của 2) có dạng: 100...0.
- Số N - 1 sẽ có dạng: 011...1 (tất cả các bit sau bit 1 của N đều bị đảo ngược).
- Khi thực hiện phép toán AND bitwise (&): (100...0) & (011...1) = 000...0.
- Đối với bất kỳ số nào không phải là lũy thừa của 2, biểu diễn nhị phân của nó sẽ có nhiều hơn một bit 1. Do đó, phép toán N & (N - 1) sẽ giữ lại các bit 1 phía trước và không thể cho kết quả bằng 0.
Lưu ý: Cần kiểm tra thêm điều kiện N phải lớn hơn 0. Hàm hoàn chỉnh: return (N > 0) && ((N & (N - 1)) == 0). Độ phức tạp thời gian và không gian đều là O(1).

2713

Cấu trúc dữ liệu Trie (Prefix Tree) hoạt động như thế nào? Tại sao nó cực kỳ hiệu quả cho tính năng Autocomplete và Search Suggestions?

Senior

Trie (Cây tiền tố) là một cây có cấu trúc phân nhánh đặc biệt dùng để lưu trữ một tập hợp các chuỗi ký tự, trong đó các node chia sẻ chung tiền tố (prefix) với nhau.

Cơ chế hoạt động: Mỗi node của Trie đại diện cho một ký tự. Node gốc không chứa ký tự nào. Đường đi từ gốc đến một node cụ thể biểu diễn tiền tố hoặc từ hoàn chỉnh được lưu trữ. Mỗi node sẽ chứa một mảng liên kết các con trỏ tới các ký tự tiếp theo và một biến boolean đánh dấu kết thúc từ (isEndOfWord).
Tại sao hiệu quả cho Autocomplete:
1. Tốc độ tìm kiếm từ có độ dài L chỉ là O(L), hoàn toàn độc lập với số lượng từ N được lưu trong Trie (ví dụ: tìm từ trong 1 triệu từ vẫn chỉ tốn số bước bằng số ký tự của từ đó).
2. Dễ dàng tìm kiếm tất cả các từ bắt đầu bằng một tiền tố cho trước bằng cách đi đến node đại diện cho tiền tố đó, sau đó duyệt DFS/BFS để thu thập tất cả các từ con bên dưới. Điều này giúp tối ưu hóa tối đa thời gian phản hồi cho các hệ thống gợi ý từ khóa thời gian thực.

2714

Giải thuật Quay lui (Backtracking) khác gì so với duyệt vét cạn (Brute Force)? Giải thích cơ chế Pruning (Cắt tỉa nhánh)?

Senior

Brute Force (Vét cạn): Tạo ra tất cả các cấu hình/lời giải có thể có của bài toán, sau đó kiểm tra xem cấu hình nào thỏa mãn yêu cầu. Cách này sinh ra không gian trạng thái khổng lồ và cực kỳ chậm.

Backtracking (Quay lui): Xây dựng lời giải từng bước một cách có hệ thống. Tại mỗi bước, nếu phát hiện ra lời giải đang xây dựng dở dang chắc chắn không thể dẫn đến lời giải hợp lệ cuối cùng, thuật toán sẽ ngay lập tức dừng lại, hủy bỏ nhánh đó (quay lui) để thử phương án khác.

Pruning (Cắt tỉa nhánh): Là kỹ thuật áp dụng các điều kiện ràng buộc toán học hoặc logic để phát hiện sớm các nhánh không khả thi và loại bỏ chúng ngay lập tức từ gốc trước khi đi sâu vào đệ quy. Ví dụ trong bài toán N-Queens, nếu đặt quân hậu ở cột i bị trùng đường chéo với quân hậu trước đó, ta bỏ qua hoàn toàn việc thử đặt các quân hậu tiếp theo trên nhánh này. Cắt tỉa giúp giảm đáng kể thời gian chạy từ giai thừa/mũ xuống mức chấp nhận được trên thực tế.

2715

Đệ quy đuôi (Tail Recursion) là gì và tại sao nó giúp tối ưu hóa bộ nhớ ngăn xếp (Stack) hơn đệ quy thông thường?

Senior

Đệ quy đuôi là dạng đệ quy mà lời gọi đệ quy là thao tác cuối cùng được thực thi trong hàm trước khi trả về kết quả. Không có bất kỳ phép toán nào khác (như cộng, nhân) được thực hiện sau cuộc gọi đệ quy đó.

Đệ quy thường: return n * fact(n - 1). Sau khi fact(n - 1) chạy xong, chương trình vẫn phải quay lại để thực hiện phép nhân với n. Vì vậy, JVM/Compiler bắt buộc phải giữ lại khung ngăn xếp (stack frame) của hàm hiện tại để lưu trữ biến n.
Đệ quy đuôi: return fact_tail(n - 1, n * accumulator). Kết quả của lời gọi đệ quy tiếp theo cũng chính là kết quả cuối cùng của hàm hiện tại.
Tối ưu hóa đệ quy đuôi (TCO - Tail Call Optimization): Các trình biên dịch thông minh (như GCC, Kotlin, Swift, Safari JS Engine) sẽ phát hiện đệ quy đuôi và tái sử dụng lại stack frame hiện tại thay vì tạo ra stack frame mới. Thao tác đệ quy đuôi được chuyển đổi ngầm thành vòng lặp (loop), giúp giải quyết triệt để nguy cơ tràn bộ nhớ ngăn xếp (Stack Overflow) với độ phức tạp không gian O(1).