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

Thao tác kiểm tra tiền tố (StartsWith) là một tính năng nền tảng cho các hệ thống gợi ý tìm kiếm (Auto-complete) trong các ứng dụng Enterprise.

Để đếm số lượng từ có chung một tiền tố một cách hiệu quả thay vì phải duyệt toàn bộ cây mỗi lần gọi hàm, chúng ta cần tối ưu hóa cấu trúc của TrieNode bằng cách bổ sung thêm biến đếm.

Trong thực tế phát triển phần mềm, dữ liệu người dùng nhập vào không bao giờ hoàn toàn chuẩn hóa thành chữ thường không dấu như trong các sách giải thuật cơ bản.

Nguyên lý hoạt động

Hàng đợi (Queue) là một cấu trúc dữ liệu trừu tượng hoạt động theo nguyên lý FIFO (First In, First Out - Vào trước ra trước). Phần tử được thêm vào đầu tiên sẽ là phần tử được lấy ra đầu tiên. Hai thao tác cơ bản nhất của Queue là:

Bản chất vấn đề của Linear Queue cố định

Khi cài đặt một Queue bằng mảng có kích thước cố định (Static Array), chúng ta thường duy trì hai con trỏ là front và rear. Khi thực hiện các thao tác enqueue và dequeue liên tục:

Định nghĩa hiện tượng

• Queue Overflow (Tràn hàng đợi): Xảy ra khi cố gắng thêm (Enqueue) một phần tử vào một Queue đã đạt đến giới hạn dung lượng tối đa (Capacity).
• Queue Underflow (Thiếu hụt hàng đợi): Xảy ra khi cố gắng lấy ra (Dequeue) một phần tử từ một Queue đang hoàn toàn trống rỗng.

Cách phòng ngừa và xử lý an toàn

Để tránh ứng dụng bị crash hoặc phát sinh ngoại lệ không mong muốn, lập trình viên cần thực hiện kiểm tra điều kiện biên (Boundary Conditions) trước khi thực hiện thao tác:

Bản chất so sánh bộ nhớ và hiệu năng

Khi cài đặt Queue bằng Dynamic Array (như ArrayList trong Java hay list trong Python):

Khi cây bị mất cân bằng nghiêm trọng (ví dụ: mỗi nút chỉ có một nút con duy nhất), cấu trúc cây sẽ trở thành một danh sách liên kết dài. Nếu sử dụng đệ quy, mỗi lần gọi hàm sẽ tạo một Stack Frame mới trong Call Stack. Với độ sâu lớn, ứng dụng sẽ gặp lỗi Stack Overflow. Giải pháp tối ưu là sử dụng vòng lặp (Iteration) với Stack thủ công hoặc chuyển đổi thuật toán sang duyệt theo chiều rộng (BFS) nếu không cần thiết phải dùng đệ quy.

Trong các bài toán như tính dãy Fibonacci bằng đệ quy thuần túy, số lượng lời gọi hàm tăng theo hàm mũ (2^n). Memoization giúp lưu trữ kết quả của các tham số đầu vào đã tính toán vào một bộ nhớ đệm (Cache/Map). Khi gặp lại tham số đó, hàm sẽ trả về kết quả ngay lập tức thay vì tính toán lại, giúp giảm độ phức tạp thời gian từ O(2^n) xuống O(n). Đây là bước đệm quan trọng để tiến tới kỹ thuật Dynamic Programming.

Khi truyền tham trị, ngôn ngữ lập trình sẽ tạo một bản sao (copy) của dữ liệu đó cho mỗi lần gọi hàm đệ quy. Nếu dữ liệu là một mảng hoặc đối tượng lớn, việc sao chép này tiêu tốn rất nhiều bộ nhớ và thời gian CPU. Truyền tham chiếu giúp hàm đệ quy làm việc trực tiếp trên địa chỉ bộ nhớ của dữ liệu gốc, giúp tiết kiệm không gian lưu trữ và tăng tốc độ thực thi đáng kể trong các hệ thống Enterprise.

Trong môi trường không hỗ trợ TCO, bạn nên áp dụng các kỹ thuật sau: 1. Kiểm tra độ sâu bằng một biến đếm (Counter) truyền qua tham số và ném ngoại lệ (Exception) nếu vượt ngưỡng cho phép. 2. Chuyển đổi thuật toán đệ quy sang dạng vòng lặp (Iterative approach) sử dụng Stack cấu trúc dữ liệu tự quản lý trên Heap. 3. Sử dụng kỹ thuật Trampolining để thực thi các hàm đệ quy trong một vòng lặp điều khiển, giúp tránh việc chồng chất Stack Frame.

Việc tách biệt giúp lập trình viên dễ dàng xác định điểm dừng của thuật toán, tránh các vòng lặp vô tận. Khi viết Unit Test, việc cô lập Base Case cho phép kiểm tra các trường hợp biên (Edge Cases) một cách độc lập. Nếu logic bị trộn lẫn, việc debug sẽ trở nên khó khăn vì trạng thái của Call Stack thay đổi liên tục, làm giảm khả năng đọc hiểu và bảo trì của mã nguồn trong các dự án dài hạn.

Bản chất hiện tượng Hash Collision

Trong Hash Table, hàm băm (hash function) có nhiệm vụ chuyển đổi một khóa (key) thành một chỉ số (index) trong mảng lưu trữ. Do không gian khóa thường lớn hơn nhiều so với kích thước thực tế của mảng, hiện tượng hai khóa khác nhau sinh ra cùng một giá trị băm là điều tất yếu theo nguyên lý chuồng bồ câu (Pigeonhole Principle). Hiện tượng này được gọi là Hash Collision (Xung đột băm).

Bản chất vấn đề

Thuật toán đệ quy thuần túy (Pure Recursion) để tính số Fibonacci có độ phức tạp thời gian là O(2^N). Khi N tăng, số lượng lời gọi hàm tăng theo cấp số nhân, dẫn đến hiện tượng treo luồng chính (Main Thread Freeze) hoặc tràn bộ nhớ Stack (Stack Overflow).

Khi cài đặt cấu trúc dữ liệu Queue (Hàng đợi) theo nguyên lý FIFO (First In, First Out), việc lựa chọn giữa Array (Mảng) và Linked List (Danh sách liên kết) ảnh hưởng trực tiếp đến hiệu năng và khả năng mở rộng của ứng dụng.