50 câu hỏi phỏng vấn về giải thuật và cấu trúc dữ liệu dành cho lập trình viên

Bài viết này được đăng trên Harkenoon và được ITguru lược dịch với mong muốn mang lại cho bạn một số câu hỏi phỏng vấn thường gặp về cấu trúc dữ liệu và giải thuật. Những câu hỏi này sẽ thích hợp cho những bạn mới ra trường hoặc 1-2 năm kinh nghiệm cần chuẩn bị cho các buổi phỏng vấn về lập trình. Theo tác giả, mục tiêu của bài viết là giúp cho những ai muốn ứng tuyển vào các công ty như Uber, Netflix, Amazon, Microsoft, Google… Tuy nhiên, theo chúng tôi các câu hỏi này cũng giúp cho các lập trình viên chưa có nhiều kinh nghiệm có thể chuẩn bị tốt cho các buổi phỏng vấn, bất kể đó là công ty nào. Lưu ý là tất cả các giải pháp cho các câu hỏi phỏng vấn trong bài này đều được thực hiện trên ngôn ngữ lập trình Java. Nếu bạn muốn tìm hiểu các câu hỏi phỏng vấn về lập trình Python có thể xem ở đây

1. Các câu hỏi phỏng vấn về mảng (Array)

Mảng là cấu trúc dữ liệu cơ bản nhất của mọi ngôn ngữ lập trình, đươc lưu trong các ô nhớ liên tiếp nhau trong bộ nhớ. Có rất nhiều câu hỏi phỏng vấn xoay quanh chủ đề này trong các buổi phỏng vấn về lập trình.

Lợi ích lớn nhất của mảng là nó cho phép tìm kiếm nhanh với độ phức tạp O(1), tức cần một thời gian cố định để xử lý nếu bạn biết được các chỉ mục (index). Tuy nhiên việc thêm bớt các phẩn tử lại khá chậm do bạn không thể thay đổi kích thước của mảng một khi nó được tạo.

Để tạo một mảng ngắn hơn hay dài hơn, bạn cần phải tạo một mảng mới và copy tất cả các phần tử từ mảng cũ sang mảng mới.

Điều mấu chốt để có thể trả lời các câu hỏi về mảng khi phỏng vấn lập trình là bạn cần phải nắm vững kiến thức về cấu trúc dữ liệu mảng cũng như các hàm (programming constructors) căn bản như vòng lặp, đệ qui và các toán tử cơ bản.

Bạn có thể tìm hiểu thêm: Mảng là gì và các tác vụ trên mảng

Dưới đây là các các câu hỏi phỏng vấn thông dụng liên quan đến array trong các buổi phỏng vấn về lập trình. (Lưu ý là các tài liệu về các giải pháp cho câu trả lời đều là tiếng Anh)

1. Làm thế nào để tìm số còn thiếu trong một mảng số nguyên cho trước từ 1 đến 100 (trả lời)
2. Làm sao bạn có thể tìm số bị trùng lắp một mảng số nguyên cho trước? (Trả lời)
3. Làm thế nào để bạn có thể tìm số lớn nhất và nhỏ nhất trong một mảng chưa được sắp xếp (Trả lời)
4. Làm thế nào để tìm tất cả các cặp số trong một mảng số nguyên có tổng bằng với một số cho trước (Trả lời)
5. Cách nào để tìm tất cả các số bị trùng lắp (duplicate) trong một mảng nếu nó chứa nhiều số bị lặp lại? (Trả lời)
6. Trong Java, làm thế nào để loại bỏ các phần tử trùng lắp (duplicates) trong một mảng cho trước (Trả lời)
7. Làm thế nào để có thể sắp xếp một mảng số nguyên theo thứ tự sử dụng giải thuật quicksort? (Trả lời)
8. Làm thế nào để loại bỏ các phần tử bị trùng lắp trong một mảng? (Trả lời)
9. Làm thế nào để bạn có thể đảo ngược thứ tự các phần tử trong một mảng trong Java? (Trả lời)
10. Bạn làm thế nào để loại bỏ các phần tử trùng lắp trong một mảng mà không sử dụng bất kỳ thư viện (library) nào? (Trả lời)

Những câu hỏi trên không chỉ giúp bạn cải thiện kỹ năng giải quyết vấn đề (problem solving) mà còn nâng cao kiến thức về cấu trúc dữ liệu mảng (array data structure). Nếu bạn thấy 10 câu trên là chưa đủ thì đây, có thêm 30 câu hỏi khác liên quan đến mảng dành cho bạn

Ngoài ra, nếu bạn muốn tìm hiểu thêm các câu hỏi phỏng vấn về giải thuật nâng cao liên quan đến mảng, bạn cũng có thể mua thêm khóa học này The Coding Interview Bootcamp: Algorithms + Data Structures.  Đây là một khóa học về giải thuật được thiết kế giúp bạn chuẩn bị tốt các các buổi phỏng vấn vào các công ty công nghệ lớn như Google, Microsoftm Apple, Facebook, etc.

2. Các câu hỏi phỏng vấn về danh sách liên kết (linked list)

Danh sách liên kết là một loại cấu trúc dữ liệu khác bổ sung cho cấu trúc dữ liệu mảng đề cập bên trên. Tương tự như mảng, nó là cấu trúc dữ liệu tuyến tính và chứa các phần tử theo kiểu tuyến tính. Khác với mảng, danh sách liên kết không chứa các phần tử theo các vị trí liền kề nhau. Thay vào đó nó chứa các phần tử tại nhiều nơi trong bộ nhớ. Mỗi phần tử này bao gồm dữ liệu cần chứa và địa chỉ của phần tử tiếp theo.

Do có cấu trúc như vậy nên ta có thể dễ dàng thêm hay bớt các phần tử trong danh sách liên kết bằng cách thay đổi liên kết thay vì tạo lại mảng. Tuy nhiên, độ phức tạp của việc tìm một tử trong một danh sách liên kết đơn là O(n). 

Trong tài liệu này bạn có thể tìm thông tin về sự khác nhau giữa mảng và danh sách liên kết. Bạn cũng có thể tìm thấy thông tin về liên kết đơn (singly linked list), tức danh sách liên kết chỉ có kết nối từ phần tử trước đến phần tử sau, và liên kết đôi (doubly-linked list), tức danh sách liên kết có sự kết nối giữa các phần tử phía trước và phía sau. Và cuối cùng là các danh sách liên kết vòng (circular linked list), là danh sách liên kết có thêm sự kết nối giữa 2 phần tử đầu tiên và phần tử cuối cùng để tạo thành vòng khép kín.

Để có thể trả lời các câu hỏi về danh sách liên kết bạn cần có kiến thúc tốt về đệ quy. Lý do đơn giản là một danh sách liên kết là một cấu trúc dữ liệu đệ quy. Nếu bạn lấy ra một phầ tử (node) từ một linked list, cấu trúc còn lại cũng vẫn là một danh sách liên kết. Và vì vậy rất nhiều các vấn đề liên quan đến cấu danh sách liên kết được giải quyết bằng đệ quy.

Dưới đây là các câu hỏi phỏng vấn liên quan đến danh sách liên kết bạn hay gặp phải cùng các giải pháp cho câu trả lời:

1. Làm thế nào để tìm một phần tử ở giữa trong một mảng liên kết đơn chỉ trong một lần tìm? (Trả lời)
2. Làm sao bạn có thể kiểm tra để biết một danh sách liên kết cho trước có có chứa một vòng? Làm thế nào để bạn có thể tìm được node đầu của vòng đó? (Trả lời)
3. Làm thế nào để đảo ngược một danh sách liên kết? (Trả lời)
4. Làm thế nào để đảo ngược một danh sách liên kết đơn mà không dùng đệ quy? (Trả lời)
5. Làm thế nào để loại bỏ các node trùng lắp trong một danh sách chưa được sắp xếp (Trả lời)
6. Làm thế nào để tìm chiều dài của một danh sách liên kết đơn (Trả lời)
7. Làm thế nào để tìm node thứ ba từ node cuối của một danh sách liên kết đơn? (Trả lời)
8. Tìm tổng của hai danh sách liên kết sử dụng Stack (Trả lời)

Các câu hỏi này cũng giúp bạn phát triển kỹ năng giải quyết vấn đề cũng như cải thiện kiến thức về cấu trúc dữ liệu danh sách liên kết.

Bạn có thể xem thêm 30 câu hỏi phỏng vấn về danh sách liên kết để học hỏi thêm. Ngoài ra bạn cũng có thể tham gia khóa học Cấu Trúc Dữ liệu và Giải thuật chuyên sâu sử dụng Java cũng khá bổ ích.

3. Các câu hỏi phỏng vấn liên quan đến chuỗi (String)

Cùng với mảng và danh sách liên kết, chuỗi cũng là một chủ đề khá thông dụng trong các buổi phóng vấn về lập trình. Khó có thể tìm buổi phỏng vấn về coding nào mà không có câu hỏi về string.

Một điều tốt về string là nếu bạn đã nắm rõ về array, bạn có thể dễ dàng trả lời các câu hỏi về string vì thực ra chuỗi chính là một mảng ký tự (character array). Các kỹ thuật bạn học để giải quyết các câu hỏi về mảng cũng có thể áp dụng cho chuỗi.

Dưới đây là danh sách các câu hỏi về chuỗi thường gặp trong các buổi phỏng vấn về lập trình:

1. Làm thế nào để in các ký tự trùng lắp trong một chuỗi (Trả lời)
2. Làm thế nào để kiểm tra xem một chuỗi có phải là đảo của một chuỗi khác? (Trả lời)
3. Trình bày cách in ký tự không bị lặp lại đầu tiên(ví dụ swiss thì w là ký tự không bị lặp lại đầu tiên trong từ) trong một chuỗi? (Trả lời)
4. Làm thế nào để đảo ngược một chuỗi cho trước sử dụng đệ quy? (Trả lời)
5. Làm thế nào để kiểm tra nếu một chuỗi chỉ chứa các số? (Trả lời)
6. Làm thế nào để tìm các ký tự trùng lắp trong một chuỗi (Trả lời)
7. Làm thế nào để đếm số các nguyên âm và phụ âm trong một chuỗi cho trước? (Trả lời)
8. Làm thế nào để đếm số lần xuất hiện của một ký tự cho trước trong một chuỗi (Trả lời)
9. Làm thế nào để tìm tất cả các hoán vị của một chuỗi (Trả lời)
10. Làm thế nào bạn có thể đảo các từ của một câu mà không dùng bất kỳ thư viện có sẵn nào? (Trả lời)
11. Làm thế nào để kiểm tra nếu một chuỗi là một rotation (xem ví dụ trong link về giải pháp để hiểu ý nghĩa của rotation) của chuỗi còn lại? (Trả lời)
12. Làm thế nào bạn có thể kiểm tra nếu một chuỗi cho trước là xâu đối xứng, tức có thể đọc xuôi ngược gì cũng giống nhau (palindrome)? (Trả lời)

Các câu hỏi trên sẽ giúp bạn nâng cao kiến thức về chuỗi. Nếu bạn có thể trả lời mà không cần xem các hướng dẫn thì bạn đã nắm rất vững về chuỗi rồi đấy. Tuy nhiên nếu bạn muốn luyện thêm thì có 20 câu hỏi phỏng vấn về string bạn có thể xem.

Có cuốn sách khá khó nhằn về các câu hỏi về giải thuật bạn có thể tìm hiểu thêm nếu muốn: Cẩm nang thiết kế giải thuật của Steven Skiena.

4. Các câu hỏi phỏng vấn về cây nhị phân (Binary Tree)

Cho đến lúc này chúng ta mới chỉ tìm hiểu các câu hỏi về cấu trúc dữ liệu tuyến tính. Tuy nhiên trong thực tế thông tin không phải lúc nào cũng được biễu diễn dưới dạng tuyến tính. Và khi đó cấu trúc dữ liệu cây được sử dụng.

Cấu trúc dữ liệu cây là một cấu trúc dữ liệu cho phép bạn lưu dữ liệu một cách có thứ bậc (hierarchical). Tùy vào cách bạn lưu dữ liệu mà có nhiều loại cây và một trong số đó là cây nhị phân. Trong cây nhị phân mỗi nút (node) có nhiều nhất hai nút con.

Cây nhị phân còn có một người em họ là Cây nhị phân tìm kiếm (binary search tree), cũng là một cấu trúc dữ liệu cây thông dụng. Như vậy bạn có thể sẽ phải gặp rất nhiều câu hỏi xoay quanh chủ đề này, chẳng hạn duyệt cây, đếm số node, tìm độ sâu và kiểm tra xem cây nhị phân có cân bằng hay không..

• Xem thêm: Sự giống và khác giữa Cây nhị phân và cây nhị phân tìm kiếm.

Điều tiên quyết để giải quyết các câu hỏi về cây nhị phân là bạn phải nắm vững lý thuyết. Ví dụ các kiến thực về độ lớn hay độ sâu của của cây nhị phân, lá của cây nhị phân là gì, node là gì cũng như nắm rõ các giải thuật duyệt cây, chẳng hạn duyệt tiền thứ tự (pre-order traverse, tức duyệt Root – Left – Right), duyệt hậu thứ tự (post-order traverse, tức duyệt Left – Right – Root), hay duyệt trung thứ tự (in-order traverse, tức duyệt Left – Root – Right).  

Dưới đây là các câu hỏi phổ biến liên quan đến cây nhị phân mà bạn có thể gặp trong các buổi phỏng vấn cho vị trí kỹ sư phần mềm hay developer:

1. Làm thế nào để tạo một cây nhị phân tìm kiếm? (Trả lời)
2. Làm thế nào để thực hiện việc duyệt tiền thứ tự (Preorder travelsal) trong một cây nhị phân cho sẵn?  (Trả lời)
3. Làm thế nào để duyệt một cây nhị phân cho sẵn theo kiểu tiền thứ tự mà không dùng đệ quy? (Trả lời)
4. Làm thế nào để bạn có thể duyệt một cây nhị phân cho sẵn theo kiểu trung thứ tự (inorder traversal)? (Trả lời)
5. Làm thế nào để in ra tất các các node trong một cây nhị phân có sẵn dùng phương pháp duyện trung tự (in-order traversal) mà không dùng đệ quy? (Trả lời)
6. Làm thế nào để bạn thực hiện được một giải thuật duyệt cây nhị phân theo phương pháp hậu thứ tự (postorder traversal)?  (Trả lời)
7. Làm thế nào để duyệt cây nhị phân theo cách hậu thứ tự (postorder traversal) mà không dùng đệ quy? (Trả lời)
8. Làm thế nào để in ra tất cả cá lá của một cây nhị phân tìm kiếm? (Trả lời)
9. Làm thế nào để đếm số các leaf node (các node không có node con) của một cây nhị phân có sẵn? (Trả lời)
10. Làm thế nào để thực hiện việc tìm kiếm nhị phân trong một mảng (array) cho sẵn (Trả lời)

Nếu bạn thấy mình còn nhiều lỗ hổng kiến thức về cây nhị phân và không thể giải quyết các bài toán trên thì bạn nên tham gia các khóa học để cải thiện, chẳng hạn khóa này: Grokking the Coding Interview: Patterns for Coding Questions trên nền tảng học trực tuyến Educative. Ngoài ra còn có một danh sách các sách về cấu trúc dữ liệu và giải thuật cùng một số khóa học bạn có thể tham khảo.

5. Những câu hỏi phỏng vấn khác về coding

Ngoài những câu hỏi phỏng vấn về cấu trúc dữ liệu, trong các buổi phỏng vấn về lập trình bạn còn được hỏi về giải thuật, thiết kế, các thao tác bit (bit manipulation), các câu hỏi về logic… Dưới đây là một số câu hỏi dạng này.  Điếu quan trọng là bạn phải thực hành các khái niệm này vì đôi lúc chúng khá lắt léo để có thể nhanh chóng giải quyết trong các buổi phỏng vấn. Luyện tập không chỉ giúp bạn quen thuộc mà còn giúp bạn tự tin hơn khi giải thích về giải pháp của mình cho các những người phỏng vấn bạn.

1. Làm thế nào để thực hiện giải thuật sắp xếp nổi bọt (bubble sort)? (Trả lời)
2. Làm thế nào để thực hiện giải thuật sắp xếp nhanh (quicksort) bằng phương pháp lặp (iterative)? (Trả lời)
3. Làm thế nào để thực hiện giải thuật sắp xếp chèn (insertion sort)? (Trả lời)
4. Làm thế nào để thực hiện giải thuật sắp xếp trộn (merge sort)? (Trả lời)
5. Làm thế nào để thực hiện thuật toán bucket sort? (Trả lời)
6. Làm thế nào để thực hiện thuật toán đếm phân phối (Counting sort)? (Trả lời)
7. Hãy thực hiện thuật toán radix sort (sắp xếp theo cơ số)? (Trả lời)
8. Làm sao để bạn swap hai số mà không dùng biến thứ ba? (Trả lời)
9. Làm sao để kiểm tra nếu hai hình chữ nhật không trùng nhau? (Trả lời)
10. Làm thế nào để thiết kế một máy bán hàng tự động (vending machine)? (Trả lời)

Nếu bạn cần tìm hiểu thêm những câu hỏi phỏng vấn về lập trình không chỉ đối với Java có thể xem trong các cuốn sách như Cracking The Code Interview của Gayle Laakmann McDowell với hơn 189+ câu hỏi về lập trình cùng các hướng dẫn trả lời.

Bạn càng luyện tập, bạn càng chuẩn bị được kỹ càng cho buổi phỏng vấn. Vì vậy bạn có thể xem thêm 50 câu hỏi phỏng vấn về lập trình cùng những cuốn sách hoặc khóa học để chuẩn bị tốt nhất.

6. Bạn đã sẵn sàng tham dự cuộc phỏng vấn về lập trình?

Ngoài những câu hỏi phỏng vấn liên quan đến cấu trúc dữ liệu và giải thuật thì còn có những câu hỏi khác thông dụng bạn nên tìm hiểu. Những câu hỏi đó ban có tìm thấy ở blog này.

Chúc bạn may mắn!

Bạn có thể đọc bài viết gốc tại đây

Bạn có biết?

tham gia cộng đồng ITguru trên Linkedin, Facebook và các kênh mạng xã hội khác có thể giúp bạn nhanh chóng tìm được những chủ đề phát triển nghề nghiệp và cập nhật thông tin về việc làm IT mới nhất

Linkedin Page:
Facebook Group:
cơ hội việc làm IT : ITguru.vn