Cấu trúc dữ liệu và giải thuật không chỉ là môn học căn bản mà còn là nỗi ác mộng của hơn 80% sinh viên học ngành công nghệ thông tin. Việc ứng dụng kiến thức về cấu trúc dữ liệu trong thực tế thường là một điều mờ mịt với nhiều người.
Tuy nhiên, vai trò của cấu trúc dữ liệu và giải thuật trong các buổi phỏng vấn thử việc không thể bị xem nhẹ. Tất cả các lập trình viên, từ hạng lông cho đến hạng nặng và siêu nặng, đều cần phải nắm vững các cấu trúc dữ liệu như stack, linked list, queue, array, tree, graph (đồ thị). Mặc dù cây và đồ thị có vẻ khó hơn so với các cấu trúc khác, nhưng tôi vẫn thấy không ít người sử dụng chúng rất thành thạo.
Danh sách dưới đây là 12 câu hỏi kinh điển về cấu trúc dữ liệu mà bạn nên chuẩn bị trước khi tham gia phỏng vấn:
Câu hỏi 1: Tìm phần tử ở giữa Linked List sau 1 lần duyệt
Khi chỉ được duyệt qua danh sách một lần, nhiều lập trình viên gặp khó khăn khi tìm ra phần tử ở giữa của một danh sách liên kết. Một mẹo nhỏ để giải quyết câu hỏi này là sử dụng hai con trỏ thay vì một con trỏ để duyệt qua danh sách trong cùng một lần. Con trỏ thứ nhất sẽ duyệt từng nút một, trong khi con trỏ thứ hai sẽ nhảy hai nút một lần. Khi con trỏ đầu tiên dừng lại, con trỏ thứ hai sẽ đến được phần tử ở giữa.
Câu hỏi 2: Làm thế nào để xác định một danh sách liên kết có vòng?
Để kiểm tra xem một danh sách liên kết có chứa một vòng hay không, chúng ta có thể sử dụng hai con trỏ có bước nhảy khác nhau. Nếu sau một số lượt duyệt nhất định, hai con trỏ này trỏ tới cùng một nút, thì tức là danh sách liên kết đó chứa một vòng.
Câu hỏi 3: Xác định giá trị của hai phần tử trùng nhau trong một mảng số nguyên từ 1-100
Thay vì so sánh từng cặp phần tử trong mảng để tìm giá trị trùng nhau, có một cách giải quyết thông minh hơn. Hãy tính tổng của toàn bộ dãy số, sau đó trừ đi tổng các số từ 1 đến 100. Phần chênh lệch giữa hai tổng sẽ là giá trị cần tìm. Với cách làm này, độ phức tạp của thuật toán chỉ là O(n).
Câu hỏi 4: Đảo một xâu ký tự trong Java
Việc đảo ngược một xâu ký tự là một trong những câu hỏi được yêu thích của nhiều người. Trong buổi phỏng vấn, bạn có thể gặp phải yêu cầu viết một hàm đảo ngược xâu ký tự mà không được sử dụng các hàm có sẵn. Bạn cũng có thể phải trình bày cách đảo ngược một xâu ký tự bằng đệ quy.
Câu hỏi 5: Stack vs Queue?
Stack hoạt động theo nguyên tắc "LIFO" - Last In First Out, trong khi Queue hoạt động theo nguyên tắc "FIFO" - First In First Out. Dù đây là kiến thức căn bản, nhưng không ít người vẫn gặp khó khăn với câu hỏi này.
Câu hỏi 6: Xác định các phần tử trùng giá trị trong một mảng số nguyên
Một cách để giải quyết vấn đề này là sử dụng cấu trúc dữ liệu Hashtable hoặc Hashmap. Ta có thể duyệt qua mảng, lưu mỗi giá trị như một key và số lần xuất hiện của nó như một value trong Hashmap. Sau đó, ta có thể kiểm tra phần tử trùng giá trị thông qua giá trị tương ứng trong Hashmap. Với việc sử dụng Hashmap, độ phức tạp của thuật toán là O(n).
Câu hỏi 7: Singly Linked List vs Doubly Linked List
Sự khác biệt lớn nhất giữa hai loại danh sách liên kết này là khả năng duyệt qua các phần tử. Với danh sách liên kết đơn, bạn chỉ có thể đi tới phần tử kế tiếp và không thể quay lại phần tử trước đó. Trong khi đó, với danh sách liên kết kép, bạn có thể đi tới cả phần tử trước và sau.
Câu hỏi 8: In ra màn hình dãy Fibonacci
Dãy Fibonacci là dãy số đặc biệt với tính chất số sau bằng tổng hai số trước đó. Trong một buổi phỏng vấn, bạn có thể được yêu cầu viết một hàm trả về số thứ i trong dãy Fibonacci, hoặc viết hàm đệ quy để tính dãy Fibonacci trong Java.
Câu hỏi 9: Kiểm tra một số có phải là Palindrome không?
Số Palindrome là số đọc từ trước xuôi hay ngược lại đều giống nhau. Một câu hỏi khác không liên quan đến cấu trúc dữ liệu nhưng thường xuất hiện trong phỏng vấn cấu trúc dữ liệu. Bạn phải giải quyết câu hỏi được sử dụng các phép toán số học, các lệnh rẽ nhánh và lặp mà không được sử dụng các hàm có sẵn.
Câu hỏi 10: Cây nhị phân tìm kiếm - Binary search tree
Cây nhị phân tìm kiếm là một cấu trúc dữ liệu quan trọng. Mỗi nút trong cây nhị phân tìm kiếm có tối đa hai nút con và các nút bên phải luôn lớn hơn nút gốc, trong khi các nút bên trái nhỏ hơn nút gốc. Sự khác biệt quan trọng khi thực hiện phỏng vấn không chỉ là hiểu lý thuyết về cây nhị phân tìm kiếm mà còn việc cài đặt cây và viết các phương thức để duyệt các nút.
Câu hỏi 11: Đảo vị trí các phần tử trong danh sách liên kết sử dụng đệ quy và duyệt tuần tự
Đảo ngược danh sách liên kết bằng cách sử dụng đệ quy và duyệt tuần tự là một câu hỏi cơ bản và thú vị về cấu trúc dữ liệu. Bạn có thể tìm hiểu thêm về cách giải quyết câu hỏi này trong tài liệu tham khảo.
Câu hỏi 12: Cài đặt Stack
Bạn có thể cài đặt cấu trúc dữ liệu Stack thông qua mảng hoặc danh sách liên kết. Các hàm cơ bản như push() và pop() là bắt buộc. Cũng nên cung cấp các hàm tiện ích như contains() hoặc isEmpty(). Nếu bạn sử dụng Java, cũng có sẵn một lớp Stack trong gói java.util.Stack.
Lưu ý, việc cài đặt Stack không đúng cách có thể gây ra memory leak trong Java. Hãy tham khảo cuốn sách "Effective Java" của Josh Bloch để hiểu rõ hơn và tránh các lỗi này.
Đó là 12 câu hỏi kinh điển về cấu trúc dữ liệu mà bạn nên chuẩn bị trước khi tham gia phỏng vấn. Hy vọng rằng bài viết này có thể giúp bạn nắm vững kiến thức và cải thiện khả năng phỏng vấn của mình. Chúc bạn thành công trong sự nghiệp lập trình!
