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

Bản chất vấn đề

Quick Sort là một thuật toán sắp xếp rất hiệu quả với độ phức tạp trung bình là $O(n \log n)$ và chi phí bộ nhớ phụ nhỏ $O(\log n)$. Tuy nhiên, Quick Sort có điểm yếu chí mạng: trường hợp xấu nhất (Worst-case time complexity) là $O(n^2)$ khi chọn pivot kém trên các mảng đã được sắp xếp gần xong hoặc có nhiều phần tử trùng lặp. Hơn nữa, đệ quy sâu có thể gây tràn bộ nhớ Stack Overflow.

Trong nhiều bài toán thực tế như Longest Common Subsequence (LCS) hoặc Edit Distance, bảng trạng thái có kích thước $M \times N$. Nếu $M$ và $N$ lên tới hàng chục nghìn, việc cấp phát mảng 2 chiều sẽ gây ra lỗi Out of Memory.

Tree DP là dạng bài toán quy hoạch động được thực hiện trên cấu trúc dữ liệu cây hoặc đồ thị có hướng không có chu trình (DAG), thường dùng trong các bài toán tối ưu hóa trên hệ thống phân cấp.

Trong nhiều bài toán tối ưu hóa, nếu áp dụng quy hoạch động truyền thống, độ phức tạp thời gian sẽ là $O(N^2)$, dẫn đến việc quá thời gian (Time Limit Exceeded) khi $N$ rất lớn (ví dụ $N = 10^5$). Kỹ thuật kết hợp với tìm kiếm nhị phân hoặc cấu trúc dữ liệu như Segment Tree / Fenwick Tree giúp hạ độ phức tạp xuống $O(N \log N)$.

Trong các bài toán mà tập hợp các phần tử cần chọn có kích thước nhỏ (ví dụ N dưới 20), kỹ thuật Bitmask Dynamic Programming được sử dụng để biểu diễn trạng thái của tập hợp dưới dạng một số nguyên nhị phân.

Khi phỏng vấn ở cấp độ Middle, các bài toán quy hoạch động không chỉ dừng lại ở việc tìm giá trị lớn nhất hay nhỏ nhất, mà còn mở rộng sang bài toán đếm số lượng cấu hình hợp lệ.

Khi xử lý mảng dữ liệu lớn với các hàm bậc cao nối tiếp nhau (ví dụ: array.filter(...).map(...)), JavaScript Engine sẽ phải duyệt qua toàn bộ mảng và tạo ra một mảng trung gian mới tại mỗi bước. Điều này làm tăng độ phức tạp không gian từ O(1) lên O(N) cho từng bước và tiêu tốn tài nguyên cho Garbage Collection.

Trong JavaScript, các biến kiểu mảng lưu trữ địa chỉ tham chiếu (reference) trong bộ nhớ chứ không lưu trực tiếp giá trị. Khi thực hiện các thao tác thay đổi trực tiếp như push, pop, splice, sort, tham chiếu gốc không thay đổi, khiến các state management library không nhận diện được sự thay đổi để kích hoạt việc render lại UI.

Độ cục bộ bộ nhớ (Memory Locality) đóng vai trò quyết định trong việc tận dụng bộ nhớ đệm (CPU Cache L1/L2/L3). Mảng đa chiều trong các ngôn ngữ bậc cao thường được cài đặt dưới dạng mảng của các mảng (array of arrays), làm cho dữ liệu phân mảnh trên RAM và gây ra hiện tượng Cache Miss.

Offset-based Pagination sử dụng câu lệnh OFFSET trong cơ sở dữ liệu. Khi offset tăng lên (ví dụ trang 100000), cơ sở dữ liệu vẫn phải đọc và bỏ qua 100000 bản ghi trước đó, làm suy giảm hiệu năng mảng dữ liệu trả về và tăng tải cho CPU.

Trong Dynamic Arrays (như Array trong JavaScript hay ArrayList trong Java), khi thực hiện thao tác chèn hoặc xóa phần tử ở đầu mảng (shift hoặc unshift), toàn bộ các phần tử còn lại trong mảng phải dịch chuyển lại vị trí trong bộ nhớ. Điều này dẫn đến độ phức tạp thời gian là O(N).

Trong môi trường đa luồng, Collections.synchronizedMap sử dụng cơ chế khóa toàn cục (mutex) trên toàn bộ đối tượng map, dẫn đến hiện tượng tranh chấp tài nguyên (contention) nghiêm trọng khi nhiều luồng cùng truy cập. Ngược lại, ConcurrentHashMap sử dụng kỹ thuật phân đoạn khóa (lock striping) hoặc CAS (Compare-And-Swap) để chỉ khóa các bucket cụ thể đang được thao tác. Điều này cho phép nhiều luồng đọc và ghi đồng thời vào các phần khác nhau của map mà không gây ra tình trạng block lẫn nhau, giúp cải thiện đáng kể throughput của hệ thống.

Để tránh hiện tượng clustering (tập trung dữ liệu tại một vài bucket), Hash Function cần đảm bảo các tiêu chí sau: 1. Tính phân phối đều (Uniform Distribution): Các giá trị hash tạo ra phải phân bổ ngẫu nhiên trên toàn bộ dải giá trị của kiểu dữ liệu. 2. Tính hiệu quả: Việc tính toán hash phải nhanh chóng, không gây nghẽn CPU. 3. Sử dụng các số nguyên tố: Khi kết hợp các trường dữ liệu, nên nhân với một số nguyên tố (thường là 31 hoặc 37) để giảm thiểu xác suất trùng lặp. Ví dụ: int result = 31 * result + field.hashCode();. Việc này giúp các giá trị hash khác nhau đáng kể ngay cả khi các trường dữ liệu có sự thay đổi nhỏ.

HashMap cung cấp độ phức tạp thời gian O(1) cho các thao tác tìm kiếm, chèn và xóa, nhưng nó không duy trì thứ tự của các phần tử. Khi ứng dụng yêu cầu truy vấn phạm vi (ví dụ: lấy tất cả các key trong khoảng từ A đến B), HashMap buộc phải duyệt toàn bộ phần tử (O(n)). TreeMap, dựa trên cấu trúc Red-Black Tree, duy trì thứ tự của các key theo thứ tự tự nhiên hoặc Comparator tùy chỉnh. Điều này cho phép thực hiện các thao tác như subMap() với độ phức tạp O(log n), tối ưu hơn nhiều so với việc duyệt toàn bộ HashMap trong các kịch bản nghiệp vụ cụ thể.

Rehashing là quá trình tạo một bảng mới với kích thước lớn hơn và di chuyển toàn bộ dữ liệu từ bảng cũ sang bảng mới khi hệ số tải (load factor) vượt ngưỡng. Trong các ứng dụng low-latency, quá trình này gây ra hiện tượng 'stop-the-world' tạm thời vì nó tiêu tốn tài nguyên CPU và bộ nhớ đáng kể. Để giảm thiểu ảnh hưởng, giải pháp là: 1. Cấu hình initial capacity phù hợp ngay từ đầu để tránh việc resize không cần thiết. 2. Sử dụng chiến lược Incremental Rehashing, nơi dữ liệu được di chuyển dần dần trong mỗi thao tác chèn, thay vì di chuyển toàn bộ trong một lần duy nhất.