12 câu hỏi phỏng vấn kinh điển về cấu trúc dữ liệu

Cấu trúc dữ liệu và giải thuật là môn học quan trọng trong lĩnh vực công nghệ thông tin. Đây cũng là nỗi ác mộng của hầu hết sinh viên chuyên ngành này. “Em toàn ngủ trong giờ cấu trúc dữ liệu – giải thuật các anh ạ!” hay “Học môn này thì ứng dụng vào đâu nhỉ….?” là những câu than thở thường ngày của các em.

Cấu trúc dữ liệu và giải thuật là không thể thiếu trong phỏng vấn thử việc. Vai trò của chúng không bao giờ bị coi thường. Tất cả lập trình viên, từ mới vào nghề cho đến các lập trình viên có trình độ cao đều 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ó khả năng phức tạp 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.

Để chuẩn bị tốt hơn cho buổi phỏng vấn, bạn nên tham khảo cuốn “Cracking the Coding interview” và “Introduction to Algorithm” của Thomas Cormen. 2 cuốn sách này sẽ giúp bạn có được một buổi phỏng vấn mỹ mãn.

Và không để các bạn đợi lâu hơn, dưới đây là danh sách 12 câu hỏi phỏng vấn kinh điển về cấu trúc dữ liệu:

#1 Tìm phần tử ở giữa Linked List sau 1 lần duyệt

Sau khi duyệt qua linked list lần đầu tiên và lưu độ dài vào một biến đếm, ta duyệt lần thứ hai với độ dài bằng một nửa lần đầu. Điều này giúp chúng ta tìm được phần tử ở giữa linked list chỉ sau một lần duyệt. Thay vì sử dụng hai lần duyệt với một con trỏ, ta có thể sử dụng hai con trỏ trong một lần duyệt. Con trỏ thứ nhất duyệt từng nút, và con trỏ thứ hai duyệt nhảy cóc hai nút một lần. Với cách làm này, khi con trỏ thứ nhất dừng lại, con trỏ thứ hai sẽ đã đến phần tử ở giữa linked list.

#2: Làm thế nào để xác định một danh sách liên kết có vòng?

Xem thêm : Ý nghĩa thực sự của việc học là gì?

Sử dụng hai con trỏ với bước nhảy khác nhau, ta có thể xác định xem một danh sách liên kết có vòng hay không. Khi hai con trỏ đúng lúc trỏ đến cùng một nút sau một số lần duyệt nhất định, thì danh sách đó là danh sách liên kết có vòng.

#3 Xác định giá trị 2 phần tử trùng nhau trong một mảng các số nguyên (từ 1-100)

Để xác định giá trị 2 phần tử trùng nhau trong một mảng số nguyên từ 1-100, ta cần sử dụng một thuật toán hiệu quả. Thay vì so sánh từng cặp phần tử, ta có thể tính tổng của toàn bộ dãy số và trừ đi tổng các số từ 1 đến 100. Phần chênh lệch sẽ là giá trị cần tìm. Với cách làm này, độ phức tạp thuật toán chỉ là O(n).

#4 Đảo một chuỗi ký tự trong Java

Đảo một chuỗi ký tự trong Java là một trong những câu hỏi yêu thích của các buổi phỏng vấn. String là một kiểu dữ liệu quan trọng trong lập trình, và buổi phỏng vấn của bạn sẽ có nhiều câu hỏi xoay quanh nó. Ngoài ra, người phỏng vấn có thể yêu cầu bạn viết hàm đảo chuỗi theo phương pháp đệ quy.

#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). Mặc dù đây là kiến thức căn bản, nhưng tôi đã gặp nhiều người gặp khó khăn ở câu hỏi này.

#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 để xác định các phần tử trùng giá trị trong một mảng là sử dụng cấu trúc dữ liệu Hashtable hoặc Hashmap. Với Hashmap, ta duyệt qua mảng và lưu mỗi giá trị ứng với một key và số lần xuất hiện của nó ứng với giá trị value. Sau khi duyệt hết mảng, ta có thể kiểm tra các phần tử trùng nhau bằng cách kiểm tra các giá trị tương ứng trong Hashmap. Trong Java, nếu tồn tại các giá trị trùng nhau, phương thức get(index) sẽ trả về null.

#7 Singly Linked List – Danh sách liên kết đơn VS Doubly Linked List – Danh sách liên kết kép

Sự khác biệt lớn nhất giữa danh sách liên kết đơn và danh sách liên kết kép là khả năng duyệt các phần tử trong danh sách. Trong danh sách liên kết đơn, ta chỉ có thể đi tới phần tử kế tiếp mà không thể quay lại phần tử trước đó. Trong danh sách liên kết kép, ta có thể đi đến cả phần tử trước và phần tử sau của một phần tử.

#8 Viết một chương trình in ra màn hình dãy Fibonacci

Dãy Fibonacci là một dãy số đặc biệt, trong đó số sau được tính bằng tổng hai số trước đó. Trong 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, cũng như viết hàm này bằng đệ quy trong Java. Đây là một câu hỏi không quá khó, nhưng các bạn mới vào nghề thường gặp khó khăn khi đến phần đệ quy.

#9 Viết chương trình kiểm tra một số có phải là Palindrome không?

Xem thêm : Một số câu hỏi trắc nghiệm trong Đề thi tuyển dụng của ngân hàng Vietinbank

Số Palindrome là số giống nhau khi đọc từ trái sang phải và từ phải sang trái. Đây cũng là một câu hỏi không liên quan trực tiếp đến cấu trúc dữ liệu, tuy nhiên, khi làm phỏng vấn, bạn không được phép sử dụng các hàm API liên quan đến chuỗi. Gợi ý để giải quyết câu hỏi này là sử dụng phép chia lấy phần dư và phép chia lấy phần nguyên.

#10 Trình bày về 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, những nút bên phải luôn lớn hơn nút gốc, trong khi những nút bên trái nhỏ hơn nút gốc. Giá trị các nút không được trùng nhau. Trong buổi phỏng vấn, bạn có thể được yêu cầu cài đặt cây nhị phân tìm kiếm và viết code để duyệt qua các nút của cây nhị phân.

#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 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ự là một câu hỏi cơ bản nhưng cũng thú vị về cấu trúc dữ liệu. Bạn có thể tìm hiểu thêm về cách làm ở đây.

#12 Cài đặt Stack

Bạn có thể cài đặt Stack bằng 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. Ngoài ra, các hàm tiện ích như contains() hay isEmpty() cũng rất cần thiết. JDK cũng cung cấp một lớp Stack có sẵn (java.util.Stack), bạn có thể tham khảo code của lớp này. Một lưu ý nhỏ, việc cài đặt Stack sai cách có thể gây ra memory leak trong Java, hãy đọc cuốn sách Effective Java của Josh Bloch để hiểu rõ hơn và tránh lỗi này.

Đó là danh sách 12 câu hỏi phỏng vấn kinh điển về cấu trúc dữ liệu mà bạn có thể gặp trong một buổi phỏng vấn. Hy vọng rằng bài viết này sẽ giúp bạn chuẩn bị tốt hơn cho buổi phỏng vấn của mình. Chúc bạn may mắn!

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập