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

Một hàm băm chất lượng thấp thường tạo ra sự phân bổ không đồng đều, dẫn đến hiện tượng cụm dữ liệu (clustering) tại một vài bucket nhất định. Khi nhiều khóa cùng trỏ về một bucket, độ phức tạp thời gian sẽ chuyển từ O(1) sang O(n) do phải duyệt qua danh sách liên kết hoặc cây nhị phân tại bucket đó.

Primary Clustering xảy ra khi các phần tử bị băm vào các vị trí liên tiếp, tạo thành các khối dữ liệu dài. Khi tìm kiếm hoặc chèn, thuật toán phải duyệt qua toàn bộ khối này, làm giảm hiệu năng đáng kể.

Hash Table dựa trên cả hai phương thức này để vận hành:

Hash Table cung cấp độ phức tạp trung bình O(1) cho các thao tác cơ bản, trong khi Tree Map (thường là Red-Black Tree) cung cấp O(log n).

Đây là kỹ thuật 'Space-Time Tradeoff'. Thay vì duyệt qua một mảng để tìm kiếm phần tử tương ứng (mất O(n) cho mỗi phần tử, tổng O(n^2)), chúng ta có thể đưa dữ liệu vào Hash Table trước.

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