Cấu trúc dữ liệu và giải thuật là môn học căn bản, đồng thời cũng là ác mộng của hơn 80% sinh viên học chuyên ngành công nghệ thông tin.
“Em toàn ngủ trong giờ cấu trúc dữ liệu – giải thuật các anh ạ!”
“Học môn này thì ứng dụng vào đâu nhỉ….?”
Cấu trúc dữ liệu và giải thuật là món ăn không thể thiếu của các buổi phỏng vấn thử việc. Chưa bao giờ vai trò của cấu trúc dữ liệu và giải thuật bị xem nhẹ. Tất cả lập trình viên, từ hạng lông đến hạng nặng và siêu nặng đều phải nắm được 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ó nhằn so với số còn lại 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 của tôi rất ngắn và đơn giản, để chuẩn bị tốt hơn, tôi nghĩ bạn nên tham khảo cuốn “Cracking the Coding interview”, cuốn sách này chứa cả câu hỏi và câu trả lời hợp lý. Một cuốn sách nữa, được coi như kinh thánh của cấu trúc dữ liệu – giải thuật, đó là cuốn “Introduction to Algorithm” của Thomas Cormen. 2 cuốn sách này sẽ phần nào 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, bây giờ tôi sẽ bắt đầu danh sách 12 câu hỏi kinh điển về cấu trúc dữ liệu của mình.
#1 Tìm phần tử ở giữa Linked List sau 1 lần duyệt
Sau 2 lần thì như thế này: duyệt tuần tự trong lần đầu tiên, lưu độ dài vào một biến đếm, và lần thứ hai thì duyệt với độ dài bằng một nửa lần 1.
Không ít lập trình viên bối rối khi họ chỉ được giới hạn trong 1 lần duyệt duy nhất.
Mẹo để giải quyết câu hỏi này: thay vì dùng 2 lần với 1 con trỏ, hãy dùng 2 con trỏ trong 1 lần duyệt. Con trỏ 1 duyệt tuần tự từng nút, con trỏ 2 duyệt nhảy cóc 2 nút một lần. Như vậy, khi con trỏ 1 dừng lại, con trỏ 2 sẽ duyệt đế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 vòng?
Với 2 con trỏ có bước nhảy khác nhau, ta có thể xác định được một danh sách liên kết có phải là danh sách liên kết vòng hay không.
Khi 2 con trỏ có bước nhảy khác nhau (một nút và hai nút), nếu sau một số lượt duyệt nhất định, chúng trỏ tới cùng một nút thì danh sách đó là danh sách liên kết 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)
Câu hỏi này được liệt hạng ez.
Bạn sẽ làm kiểu xôi thịt, so sánh từng cặp một phải không? Được đấy, nhưng không hay. Nếu áp dụng cách này, độ phức tạp của thuật toán bạn đang chọn sẽ là O(n^2), không ổn!
Thay vào đó, ta sẽ tính tổng của cả dãy, rồi 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 lựa chọn này, độ phức tạp còn O(n).
#4 Đảo một xâu ký tự trong Java
Đây là một trong nhiều câu hỏi yêu thích của tôi.
String là một kiểu dữ liệu quan trọng trong lập trình, chắc chắn buổi phỏng vấn của bạn sẽ có kha khá vấn đề liên quan đến String. Và quan trọng hơn, người phỏng vấn bạn sẽ không cho sử dụng các API liên quan đến String, ví dụ hàm reverse() sẽ bị cấm sử dụng… Họ cũng có thể bắt bạn trình bày cách đảo String kiểu đệ quy.
#5 Stack vs Queue?
Stack hoạt động theo nguyên lý LIFO – Last In First Out
Queue thì là FIFO – First In First Out
Tuy đây là kiến thức căn bản nhưng tôi đã gặp không ít thanh niên ngắc ngứ ở câu hỏi này.
#6 Xác định nhiều phần tử trùng giá trị trong mảng số nguyên?
Câu hỏi này là một level khác của câu #4.
Một cách để giải quyết vấn đề này là dùng một trong hai cấu trúc dữ liệu Hashtable hoặc Hashmap.
Với Hashmap, ta duyệt mảng, lưu mỗi giá trị ứng với một key và số lần xuất hiện của chúng ứng với values. Sau khi duyệt hết mảng, ta dễ dàng kiểm tra được phần tử trùng nhau thông qua giá trị của các values tương ứng trong Hashmap.
Trong Java, với cấu trúc dữ liệu Hashmap, nếu tồn tại các giá trị trùng nhau thì method 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
Lại một câu hỏi kinh điển khác về cấu trúc dữ liệu.
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 các phần tử thuộc danh sách.
Với danh sách liên kết đơn, đó là nguyên tắc một đi không trở lại, tại một nút xác định, chỉ tồn tại một con trỏ tới nút kế tiếp. Do đó, ta chỉ có thể đi tới nút kế tiếp, không thể quay lại nút trước nó.
Với danh sách liên kết kép, tại một nút tồn tại 2 con trỏ, nhờ 2 con trỏ này ta có thể đi đến nút trước và nút sau.
#8 Viết một chương trình in ra màn hình dãy Fibonacci
Đây không phải là một câu hỏi liên quan tới Cấu trúc dữ liệu nhưng luôn xuất hiện ở các buổi phỏng vấn về cầu trúc dữ liệu!
Fibonacci là một dãy số đặc biệt với tính chất số sau bằng tổng hai số trước nó. Trong buổi phỏng vấn, người ta sẽ xoáy vào 2 thứ, một là hàm trả về số thứ i trong dãy, hai là cách viết hàm đó bằng đệ quy trong Java.
Mặc dù câu hỏi này không khó nhưng các thanh niên gà mờ sẽ lúng túng ở phần đệ quy.
#9 Viết chương trình kiểm tra một số có phải là Palindrome không?
Số Palindrome là số trước sau như một – viết xuôi hay ngược đều giống nhau.
Đây cũng là câu hỏi không liên quan tới Cấu trúc dữ liệu tương tự như câu số 9. Tất nhiên, bạn không được tiếp cận với các sự trợ giúp từ API, trong tay bạn chỉ có các phép toán số học, các lệnh rẽ nhánh và lặp.
Gợi ý: 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 là một cấu trúc dữ liệu. Mọi nút của cây nhị phân có tối đa 2 nút con, các node bên phải luôn lớn hơn root node, còn các nút bên trái thì nhỏ hơn root node. Giá trị các node không trùng nhau”
Điều quan trọng là nhà tuyển dụng sẽ bắt bạn cài đặt cây nhị phân và viết thêm vài đoạn code để duyệt các node thay vì nghe bạn chém lý thuyết.
#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ự?
Một câu hỏi cơ bản nhưng cũng tương đối thú vị về cấu trúc dữ liệu.
Hãy tham khảo ở đây
#12 Cài đặt Stack
Bạn có thể cài đặt Stack thông qua array – mảng hoặc Linked List – Danh sách liên kết. Các hàm cơ bản như push() vàpop() là bắt buộc. Việc thêm các hàm tiện ích như contains() hay isEmpty() cũng rất cần thiết. JDK có hẳn một class về Stack: java.util.Stack, bạn có thể tham khảo code của class này.
Một lưu ý nho nhỏ, việc cài đặt stack sai cách có thể gây ra memory leak trong Java, hãy tham khảo cuốn Effective Java book của Josh Bloch để hiểu rõ hơn và tránh được lỗi này.
