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.
01
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)?
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.
- Số N (lũy thừa của 2) có dạng:
- 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).
02
Làm thế nào để triển khai và tối ưu hóa thuật toán hoặc cấu trúc dữ liệu liên quan đến XOR operations trong chủ đề Bit Manipulation?
Trong lập trình giải thuật với Bit Manipulation, việc làm chủ XOR operations yêu cầu lập trình viên hiểu rõ cấu trúc vật lý trong bộ nhớ và độ phức tạp tính toán:
- Độ phức tạp: Luôn đánh giá Time Complexity (thời gian) và Space Complexity (không gian) tối ưu nhất (ví dụ: tối ưu từ O(n^2) xuống O(n log n)).
- Trường hợp biên (Edge Cases): Xử lý kỹ các giá trị null, mảng rỗng, giá trị giới hạn cực đại/cực tiểu của kiểu dữ liệu.
- Mã nguồn mẫu: Triển khai giải pháp rõ ràng, súc tích bằng các cấu trúc dữ liệu cơ bản, tránh lạm dụng bộ nhớ phụ khi không cần thiết.
.png)
.png)