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

Bản chất bài toán

Trong hệ thống thanh toán, đôi khi một luồng xử lý đơn lẻ (single-thread worker) cần xử lý tối đa số lượng yêu cầu giao dịch không trùng lặp về thời gian thực hiện để tối ưu hóa hiệu suất thông lượng.

Bản chất bài toán

Khi có nhiều yêu cầu đặt lịch phòng họp với các khoảng thời gian [start, end] khác nhau và một phòng họp vật lý duy nhất, hệ thống cần chọn tập hợp các cuộc họp không bị xung đột thời gian với nhau sao cho số lượng cuộc họp được tổ chức là lớn nhất.

Bản chất bài toán

Các tiến trình ghi log hệ thống thường tạo ra các khoảng thời gian hoạt động bị chồng chéo lên nhau. Để hiển thị trên Dashboard giám sát, ta cần gộp các khoảng thời gian chồng chéo này lại thành các khoảng thời gian liên tục lớn nhất có thể.

Bản chất bài toán

Xe tải có giới hạn trọng lượng tối đa cố định. Kho hàng có nhiều kiện hàng với trọng lượng và giá trị lợi nhuận khác nhau. Hệ thống cần chọn các phần của kiện hàng hoặc toàn bộ kiện hàng sao cho tổng giá trị lợi nhuận đạt mức cao nhất mà không vượt quá tải trọng xe.

Bản chất bài toán

Hệ thống phát sóng trực tuyến nhận được một danh sách các tác vụ render video. Mỗi tác vụ có thời hạn hoàn thành (Deadline) và lợi nhuận (Profit) cố định nếu hoàn thành đúng hạn. Mỗi tác vụ mất 1 đơn vị thời gian để xử lý. Hệ thống cần tìm cách sắp xếp lịch trình để tối đa hóa tổng lợi nhuận.

Phân tích bản chất

Thuật toán Dijkstra dựa trên cơ chế tham lam (greedy), giả định rằng khi một nút đã được thăm, đường đi ngắn nhất đến nó đã được tìm thấy. Điều này không còn đúng nếu đồ thị chứa cạnh có trọng số âm, vì một đường đi dài hơn về số lượng cạnh có thể có tổng trọng số nhỏ hơn sau khi đi qua cạnh âm.

Bản chất của DSU

Disjoint Set Union (DSU) hay còn gọi là Union-Find là cấu trúc dữ liệu chuyên biệt để quản lý các tập hợp rời nhau. Thay vì duyệt toàn bộ đồ thị mỗi khi cần kiểm tra xem hai đối tượng có cùng quyền truy cập hay không, DSU duy trì các nhóm thông qua hai thao tác chính: Find (tìm đại diện nhóm) và Union (hợp nhất hai nhóm).

So sánh cơ bản

• Greedy Best-First Search: Chỉ sử dụng hàm heuristic h(n) để ước tính khoảng cách đến đích. Nó ưu tiên nút trông có vẻ gần đích nhất, dẫn đến việc thường tìm ra đường đi không tối ưu.
• A* Search: Sử dụng hàm f(n) = g(n) + h(n), trong đó g(n) là chi phí thực tế từ điểm bắt đầu đến nút hiện tại, và h(n) là ước tính từ nút hiện tại đến đích.

Tại sao A* là tiêu chuẩn

1. Tính tối ưu (Optimality): Nếu hàm heuristic h(n) là admissible (không bao giờ ước tính quá cao chi phí thực tế), A* đảm bảo tìm được đường đi ngắn nhất.
2. Tính đầy đủ (Completeness): A* sẽ luôn tìm thấy lời giải nếu nó tồn tại.
3. Cân bằng: A* kết hợp được ưu điểm của Dijkstra (tối ưu hóa chi phí đã đi) và Greedy (định hướng tìm kiếm bằng heuristic), giúp giảm đáng kể không gian tìm kiếm so với việc duyệt mù quáng.

Kinh nghiệm thực chiến

Trong các hệ thống Enterprise, việc chọn hàm heuristic h(n) là yếu tố quyết định hiệu năng. Nếu h(n) quá đơn giản, A* sẽ trở thành Dijkstra. Nếu h(n) quá phức tạp, chi phí tính toán heuristic sẽ làm chậm hệ thống.

Phân tích thuật toán

• Kosaraju: Yêu cầu hai lần duyệt DFS và cần đảo ngược toàn bộ các cạnh của đồ thị (Transpose Graph). Việc đảo ngược đồ thị tốn kém bộ nhớ và thời gian xử lý khi đồ thị có quy mô lớn.
• Tarjan: Chỉ cần một lần duyệt DFS duy nhất. Nó sử dụng một mảng để lưu trữ thời điểm thăm (discovery time) và giá trị low-link để xác định các thành phần liên thông mạnh trong quá trình đệ quy.

Ưu điểm của Tarjan

1. Hiệu năng: Tiết kiệm thời gian vì chỉ duyệt đồ thị một lần duy nhất.
2. Bộ nhớ: Không cần tạo bản sao đồ thị đảo ngược, giúp giảm đáng kể áp lực lên bộ nhớ (Memory footprint).

Lưu ý cho Junior

Khi triển khai Tarjan, cần chú ý đến giới hạn của Stack trong ngôn ngữ lập trình (như Java hay Python) vì đệ quy sâu có thể gây ra Stack Overflow. Trong các hệ thống Enterprise, nếu đồ thị quá lớn, hãy cân nhắc chuyển đổi thuật toán đệ quy sang dạng lặp (iterative) bằng cách sử dụng Stack thủ công.

Cơ chế Coloring

• Trắng (White): Nút chưa được thăm.
• Xám (Gray): Nút đang nằm trong ngăn xếp đệ quy (đang được xử lý).
• Đen (Black): Nút đã xử lý xong hoàn toàn.

Tại sao cần 3 trạng thái

Nếu chỉ sử dụng mảng 'Visited' (đã thăm/chưa thăm), chúng ta không thể phân biệt được một nút đã thăm là 'nút tổ tiên' (đang trong đường đi hiện tại) hay là 'nút đã duyệt xong từ một nhánh khác'.

Bản chất vấn đề

Thuật toán Binary Search hoạt động dựa trên nguyên lý chia để trị (divide and conquer), yêu cầu tiên quyết là dữ liệu đầu vào phải được sắp xếp theo một thứ tự nhất định (tăng dần hoặc giảm dần). Nếu áp dụng trên mảng chưa sắp xếp, thuật toán sẽ không thể xác định được nửa nào của mảng chứa giá trị cần tìm.

Cơ chế hoạt động

Hash Table sử dụng hàm băm (hash function) để ánh xạ khóa (key) tới một chỉ số (index) trong mảng. Trong điều kiện lý tưởng, mỗi khóa ánh xạ tới một vị trí duy nhất.

Mảng (Array)

• Ưu điểm: Hỗ trợ truy cập ngẫu nhiên (random access) thông qua chỉ số, cho phép áp dụng các thuật toán như Binary Search (O(log n)).
• Nhược điểm: Cần khối bộ nhớ liên tục, khó thay đổi kích thước khi đã khởi tạo.

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

• Ưu điểm: Cấp phát bộ nhớ động, chèn/xóa phần tử nhanh nếu đã biết vị trí.
• Nhược điểm: Không hỗ trợ truy cập ngẫu nhiên. Để tìm kiếm một phần tử, bắt buộc phải duyệt tuần tự từ đầu danh sách (Linear Search) với độ phức tạp O(n).

Kết luận

Trong các bài toán yêu cầu tìm kiếm hiệu năng cao, Array luôn là lựa chọn ưu tiên nhờ tính chất lưu trữ liên tục trong bộ nhớ (cache-friendly), giúp CPU truy xuất dữ liệu nhanh hơn nhiều so với việc nhảy qua các con trỏ (pointer) trong Linked List.

Mặc dù Linear Search có độ phức tạp O(n), nó vẫn là lựa chọn tối ưu trong các trường hợp sau:

Khái niệm

Search Space (Không gian tìm kiếm) là tập hợp tất cả các giá trị có thể chứa kết quả mà thuật toán cần kiểm tra.