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

Bản chất vấn đề

Thông thường, để xóa một node trong Linked List, chúng ta cần truy cập vào node đứng trước nó để thay đổi con trỏ next. Tuy nhiên, trong một số tình huống tối ưu hóa luồng dữ liệu, bạn chỉ nhận được tham chiếu đến đúng node cần xóa.

Bản chất vấn đề

Khi hai danh sách liên kết đơn hội tụ tại một điểm, chúng sẽ chia sẻ chung tất cả các node từ điểm giao nhau đó cho đến hết danh sách. Thách thức đặt ra là tìm ra chính xác node bắt đầu giao nhau mà không làm thay đổi cấu trúc dữ liệu và không dùng cấu trúc phụ trợ như Hash Set.

Bản chất vấn đề

Một danh sách liên kết đối xứng có các giá trị đọc từ trái sang phải giống hệt như đọc từ phải sang trái. Thách thức cho Junior là danh sách liên kết đơn không hỗ trợ duyệt ngược lại từ đuôi về đầu như mảng (Array).

Bản chất vấn đề

Vì danh sách đã được sắp xếp tăng dần hoặc giảm dần, các giá trị trùng lặp chắc chắn sẽ nằm liền kề nhau. Nhiệm vụ của lập trình viên là duyệt qua danh sách và loại bỏ các node thừa để tối ưu không gian lưu trữ và tốc độ tìm kiếm.

Bản chất cơ chế hoạt động

Jump Search là thuật toán tìm kiếm trên mảng đã được sắp xếp. Thay vì tìm kiếm từng phần tử như Linear Search (độ phức tạp O(N)) hoặc chia đôi liên tục như Binary Search (độ phức tạp O(log N)), Jump Search thực hiện việc nhảy cóc qua các bước có kích thước cố định (block size) để tìm khoảng chứa giá trị cần tìm, sau đó thực hiện Linear Search tuyến tính trong khoảng đó.

Bản chất cơ chế hoạt động

Exponential Search (Tìm kiếm lũy thừa) kết hợp việc tìm kiếm phạm vi (range bounding) với Binary Search truyền thống. Thuật toán hoạt động theo hai giai đoạn:

Bản chất cơ chế hoạt động

Khi mảng chứa các phần tử trùng lặp, Binary Search tiêu chuẩn không đảm bảo trả về vị trí xuất hiện đầu tiên hoặc cuối cùng. Để giải quyết, chúng ta cần tùy chỉnh điều kiện khi tìm thấy giá trị arr[mid] == x:

Bản chất cơ chế hoạt động

Xét một ma trận 2D mà mỗi hàng được sắp xếp tăng dần từ trái sang phải, và phần tử đầu tiên của mỗi hàng lớn hơn phần tử cuối cùng của hàng trước đó (hoặc ma trận có tính chất tăng dần theo cả hàng và cột).

Bản chất cơ chế hoạt động

Bài toán yêu cầu tìm căn bậc hai nguyên của một số không âm x, lấy phần nguyên (ví dụ: sqrt(8) = 2). Thay vì dùng hàm toán học thông thường, ta có thể áp dụng Binary Search trong khoảng từ 0 đến x:

Khái niệm

• Queue Overflow: Xảy ra khi cố gắng thực hiện thao tác Enqueue trong khi hàng đợi đã đầy.
• Queue Underflow: Xảy ra khi cố gắng thực hiện thao tác Dequeue hoặc Peek trong khi hàng đợi không còn phần tử nào.

Giải pháp xử lý với Mảng tĩnh

Khi cài đặt Queue bằng mảng tĩnh có kích thước cố định, cần duy trì hai con trỏ hoặc chỉ số là front và rear kèm theo biến đếm số lượng phần tử size.

Cài đặt Queue bằng Mảng

• Ưu điểm:
  • Truy cập phần tử dựa trên chỉ số có độ phức tạp thời gian O(1).
  • Dữ liệu được lưu trữ liền kề trong bộ nhớ, tối ưu hóa khả năng tận dụng bộ nhớ cache (Cache Locality).
• Nhược điểm:
  • Kích thước cố định (đối với mảng tĩnh) hoặc tốn chi phí cấp phát lại bộ nhớ và sao chép dữ liệu (đối với mảng động).
  • Gặp hiện tượng lãng phí bộ nhớ nếu không dùng mảng vòng.

Cài đặt Queue bằng Danh sách liên kết đơn

• Ưu điểm:
  • Kích thước linh hoạt, dễ dàng mở rộng động theo số lượng phần tử thực tế mà không cần định nghĩa trước dung lượng tối đa.
  • Thao tác Enqueue và Dequeue ở cả hai đầu đều đạt độ phức tạp thời gian O(1) nếu duy trì đồng thời con trỏ head và tail.
• Nhược điểm:
  • Tốn thêm bộ nhớ để lưu trữ các con trỏ (pointers) liên kết giữa các node.
  • Không tối ưu Cache Locality do các node nằm rải rác trong bộ nhớ heap.

Lưu ý kinh nghiệm thực chiến

Ở cấp độ Junior, khi phỏng vấn cần nắm vững độ phức tạp thời gian (Time Complexity) và không gian (Space Complexity) của từng cách tiếp cận để lựa chọn cấu trúc dữ liệu phù hợp với bài toán hệ thống cụ thể.

Độ phức tạp thời gian chuẩn của Queue

• Thao tác Enqueue (Thêm phần tử vào cuối): O(1) nếu có duy trì con trỏ tail.
• Thao tác Dequeue (Lấy phần tử ra từ đầu): O(1) nếu quản lý con trỏ head hoặc sử dụng mảng vòng.
• Thao tác Peek (Xem phần tử đầu): O(1).
• Thao tác Search (Tìm kiếm phần tử): O(N).

Nguyên nhân gây kém hiệu quả trong thực tế

• Nếu cài đặt Queue bằng mảng thông thường mà không dùng mảng vòng, khi thực hiện Dequeue, ta phải dịch chuyển toàn bộ các phần tử còn lại về bên trái để lấp đầy vị trí trống, dẫn đến độ phức tạp thời gian của Dequeue bị đẩy lên O(N), làm giảm hiệu năng hệ thống nghiêm trọng.
• Nếu cài đặt danh sách liên kết nhưng quên duy trì con trỏ tail, thao tác Enqueue sẽ phải duyệt qua toàn bộ danh sách từ đầu đến cuối để tìm node cuối cùng, biến độ phức tạp thành O(N).

Lưu ý kinh nghiệm thực chiến

Luôn kiểm tra kỹ các biến con trỏ khi xây dựng cấu trúc dữ liệu tùy chỉnh (Custom Data Structures) để tránh vi phạm các ràng buộc về hiệu năng O(1) trong các tác vụ cốt lõi.

Vai trò của Queue trong hệ thống bất đồng bộ

Queue đóng vai trò là một vùng đệm (buffer) trung gian lưu trữ các thông điệp hoặc tác vụ cần xử lý giữa các thành phần trong hệ thống.

Nguyên lý hoạt động của Queue

Queue (Hàng đợi) hoạt động dựa trên nguyên lý FIFO (First In, First Out - Vào trước ra trước). Phần tử được thêm vào hàng đợi đầu tiên sẽ là phần tử được lấy ra đầu tiên. Các thao tác chính bao gồm:

Bản chất vấn đề

Khi phát triển phần mềm ở cấp độ Enterprise, việc tối ưu hóa tài nguyên phần cứng (CPU và Memory) luôn được ưu tiên hàng đầu. Bài toán tìm phần tử xuất hiện số lần lẻ trong khi các phần tử khác xuất hiện số lần chẵn là một bài toán kinh điển thường gặp trong việc xử lý log hoặc lọc dữ liệu mạng.