Nội dung chính
Phần lớn các câu hỏi phỏng vấn IT có độ khó từ trung bình đến cực kỳ khó. Và thậm chí sẽ còn khó hơn khi bạn ứng tuyển vào các công ty nổi tiếng như Amazon và Google. Tuy nhiên, vẫn có cách để chinh phục các câu hỏi phỏng vấn IT đó.
Nếu bạn đang làm trong ngành IT và viết code là công việc yêu thích của bạn, hẳn bạn đã quen thuộc với các buổi phỏng vấn code và cả mức độ “khó khăn” để vượt qua một cuộc phỏng vấn thành công như thế nào.
Còn nếu bạn chưa quen thuộc với những buổi phỏng vấn chuyên môn như vậy thì hãy nghĩ một buổi phỏng vấn code về cơ bản giống như đưa ra một bài kiểm tra. Nhà tuyển dụng sẽ đưa ra một vấn đề cụ thể mà bạn sẽ phải trình bày giải pháp dưới dạng code. Nếu bạn may mắn, các buổi phỏng vấn code sẽ diễn ra rất dễ dàng còn phần lớn các câu hỏi phỏng vấn code lại có độ khó từ trung bình đến cực kỳ khó. Nhưng nếu bạn hiểu được nhà tuyển dụng mong đợi gì từ phía bạn, bạn sẽ có cơ hội thành công cao hơn.
Read the full English version: Two of the Most Famous Coding Interview Questions Explained
Công thức chinh phục tất cả các câu hỏi phỏng vấn IT
Tìm kiếm câu trả lời cho các câu hỏi phỏng vấn IT không khó đối với lập trình viên. Thử thách thật sự chính là hiểu được nhà tuyển dụng đang tìm kiếm một câu trả lời như thế nào. Theo tôi, nhà tuyển dụng muốn nhận về những giải pháp phải thỏa được ít nhất 3 tiêu chí cơ bản này:
- Hiệu quả
- Tối ưu
- Sáng tạo
Tất nhiên, họ cũng quan tâm đến nhiều yếu tố khác nữa nhưng đây là những điều cơ bản.
“Tối ưu” ở đây mang nghĩa về hiệu suất, hay nói cách khác là về độ phức tạp của thời gian (time complexity) và bộ nhớ (space complexity). Độ phức tạp của thời gian biểu thị hiệu suất của chương trình và thời gian máy tính hoàn thành hoặc chạy các thuật toán được viết. Độ phức tạp của bộ nhớ cũng hoạt động một cách tương tự; tuy nhiên, đó là một biểu thức tóm tắt lượng bộ nhớ cần thiết để chạy thuật toán.
Về cơ bản, khi bạn phải một vấn đề mà đòi hỏi bạn cần phải thực hiện nhiều “nhiệm vụ phụ” khác mới có thể tạo ra một giải pháp thành công cho nhiệm vụ chính, việc đảm bảo cả độ phức tạp của thời gian và bộ nhớ sẽ gặp nhiều thử thách vì sẽ có nhiều quy trình cần xem xét.
Mức độ “hiệu quả” của giải pháp được dựa trên độ rõ ràng và súc tích của giải pháp. Điều này có nghĩa các giải pháp không nên thiết kế quá “cồng kềnh”. Ví dụ: Chúng ta đang phải giải quyết một vấn đề toán học. Viết chi chít các chú thích và đoạn diễn giải không cần thiết về lý do tại sao chúng ta lại thực hiện từng bước (chẳng hạn như phép cộng) sẽ làm cho câu trả lời lộn xộn và thừa mứa thông tin, khiến nó khó hiểu và khó đọc (giả định rằng đây là một câu trả lời dài). Điều tương tự cũng áp dụng cho việc viết code.
Tuy nhiên, giống như “tính thực tế” mà tôi đã có đề cập ở trên, khi cần tìm giải pháp cho các câu hỏi phỏng vấn IT lớn, bạn cần thực hiện nhiều thuật toán phụ khác nhau để lập trình, thì sẽ khó có thể viết code sạch và súc tích bởi vì theo lẽ thường, bạn cần phải giải thích với nhà tuyển dụng về những giải pháp và đa quy trình mà bạn sử dụng cho giải pháp (đây đồng thời cũng là một yếu tố khác mà ứng viên nên quan tâm, bạn có thể giải thích code bạn viết rành mạch như thế nào). Đó chính là lý do vì sao các lập trình viên cần liên tục thực hành trong nhiều tháng để chuẩn bị cho các buổi phỏng vấn.
Xem thêm: Việc làm Developer “chất” toàn quốc
Giải đáp hai trong các câu hỏi phỏng vấn IT phổ biến về cấu trúc dữ liệu cây
Trong bài viết này, tôi sẽ thảo luận về hai trong những các câu hỏi phỏng vấn IT yêu thích của cá nhân tôi và một trong những câu hỏi mã hóa phổ biến nhất liên quan đến cây. Đó là câu hỏi về chiều rộng và chiều sâu tối đa của cây. Đây là hai trong các câu hỏi phỏng vấn IT thường được hỏi nhất tại các công ty công nghệ lớn, ví dụ như Google, Amazon, v.v.
Thoạt đầu, những vấn đề này nghe có vẻ khá dễ dàng để giải quyết, vậy thì lý do tại sao câu hỏi này hấp dẫn nhiều developer và tôi đến như vậy? Đó là nhờ vào các giải pháp trừu tượng mà vấn đề này mang lại. Có nhiều cách để tạo các thuật toán thực tế và hiệu quả mà vẫn thực sự kiểm tra được khả năng suy nghĩ và cách giải quyết vấn đề của lập trình viên. Những vấn đề đơn giản này lại có thể giúp lập trình viên có cơ hội “tỏa sáng” và làm nổi bật khả năng giải quyết vấn đề của họ.
Tự bản thân câu hỏi phỏng vấn này khá đơn giản và dễ hiểu: Cho một cây nhị phân, tìm chiều rộng và chiều sâu tối đa.
Xét về mặt khái niệm thì mặc dù không có gì khó trong việc hiểu đề bài, nhưng bạn sẽ phải mất một chút thời gian (không chỉ vài giây mà là một vài phút) để tìm ra cách code nên một giải pháp thích hợp.
Giải pháp mà tôi sẽ trình bày dưới đây có vẻ sẽ hơi kỳ quặc. Và tại sao tôi lại diễn tả bằng từ “kỳ quặc”? Bởi vì theo định nghĩa, một thuật toán tìm kiếm theo chiều rộng hoạt động tốt nhất khi duyệt các đỉnh kề theo chiều ngang, và một thuật toán tìm kiếm theo chiều sâu hoạt động tốt nhất khi duyệt theo chiều dài của cây. Do đó, bạn có thể hiểu được rằng thuật toán nào nên đi với vấn đề nào.
Thông thường, thuật toán tìm kiếm theo chiều rộng (Breath-First Search – BFS) mang lại hiệu quả tốt nhất khi tìm chiều rộng tối đa của cây và thuật toán tìm kiếm theo chiều sâu (Depth-First Search – DFS) sẽ hoạt động tốt nhất khi tìm độ sâu tối đa. Cả hai thuật toán đều chạy theo thời gian tuyến tính khi xét về hiệu suất thời gian, điều đó có nghĩa là chúng ta không phải xem xét các thuật toán phức tạp khác khi duyệt cây nhị phân.
Tuy nhiên, đối với giải pháp của tôi, tôi đã làm ngược lại. Để tìm chiều rộng tối đa của cây, tôi đã sử dụng thuật toán tìm kiếm theo chiều sâu và để tìm độ sâu tối đa, tôi áp dụng thuật toán tìm kiếm theo chiều rộng. Mặc dù giải pháp của tôi có vẻ trái ngược so với giải pháp được số đông chấp nhận, cả hai thuật toán vẫn hoạt động tốt tại thời điểm tuyến tính.
Tôi sẽ diễn giải về chiều rộng tối đa trước. Tôi sẽ đi chi tiết hơn về giải pháp của mình cho vấn đề đó và cách tôi đã tận dụng độ sâu tối đa như thế nào.
Tìm kiếm chiều rộng tối đa của cây nhị phân
Tham khảo đầy đủ đoạn code dành cho giải pháp chiều rộng tối đa của cây tại đây.
Với thuật toán tìm kiếm theo chiều sâu, tôi tìm tất cả các hoán vị khác nhau có thể tồn tại mỗi cạnh nối của mỗi đỉnh bằng cách tìm kiếm qua cây theo độ sâu đệ quy. Sau đó, tôi đã thêm từng hoán vị vào một array riêng biệt vì chúng ta sẽ giả sử rằng mỗi chỉ số của mảng thể hiện một bậc nhất định. Ví dụ: Để [A, B, C] là một array của một hoán vị nhất định được trả về bởi thuật toán tìm kiếm theo chiều sâu. Chúng ta có thể xem từng chỉ số như một bậc nhất định của cây:
Về cơ bản, tôi đi theo hướng này bởi vì thuật toán tìm kiếm theo chiều sâu trả về độ sâu mà đường dẫn tìm kiếm. Do đó, nếu thuật toán đi qua mỗi cạnh đến khi gặp nút không có con, mỗi đường dẫn phải đối xứng về mặt chỉ số đại diện cho mỗi bậc.
Chúng ta cũng có thể chứng minh điều này bằng hàm thứ hai .width_counter () . Với tập hợp tất cả các hoán vị được định dạng thành một array 2D, sau đó tôi tách từng phần tử trong mỗi danh sách dựa trên các chỉ số tương tự nhau. Ví dụ: Tất cả các phần tử ở chỉ số 0 sẽ được đặt trong danh sách ở chỉ số 0, sau đó tất cả các phần tử ở chỉ số 1 sẽ được đặt trong danh sách ở chỉ số 1, v.v. Đây được gọi là phân vùng – một khái niệm khoa học máy tính tiên tiến, là cách mà chúng ta chia một array hoặc một chuỗi giá trị dựa trên một điều kiện nhất định.
Sau quá trình phân vùng, chúng ta sẽ thấy một array được trả về với các array con có các phần tử được sắp xếp dựa trên các chỉ số. Chúng ta có thể kiểm tra lại xem array được trả về có đúng hay không bằng cách so sánh sơ đồ cây với các phần tử trong danh sách. Nếu mỗi lớp của cây có các nút giống với mỗi danh sách trong chính chỉ số đó (giả sử một lần nữa rằng các chỉ số là các bậc), vậy thì ta biết rằng ta đã làm đúng vì array chỉ đơn giản là một cây được định dạng khác đi.
Bước cuối cùng trong thuật toán này để tìm độ sâu tối đa là so sánh độ dài của mỗi array trong array 2D và array lớn nhất (array có độ dài lớn nhất) sẽ là bậc rộng nhất. Trong trường hợp này, vì tôi đang so sánh từng chỉ số trong array 2D, nên tôi chỉ trả về chỉ số một cách đơn giản. Điều này vẫn đưa ra câu trả lời đúng vì định nghĩa tôi đã nêu trước đó về các bậc giống như các chỉ số của mỗi array hoán vị. Về mặt hiệu suất tổng thể, tôi đã có thể cho thuật toán tìm kiếm theo chiều sâu chạy cùng quãng thời gian O(n) và .width_counter () với quãng thời gian O(n^2) do các lần lặp lồng nhau để tạo array 2D.
Xem thêm: Việc làm Developer “chất” tại TP. HCM
Tìm kiếm chiều sâu tối đa của cây nhị phân
Tiếp theo là câu hỏi phỏng vấn IT yêu thích của tôi.
Đối với chiều sâu tối đa, phương pháp tìm độ sâu tối đa rất giống với giải pháp tìm chiều rộng tối đa đã giới thiệu ở phía trước. Tuy nhiên, như đã nói trước đây, thay vì sử dụng tìm kiếm theo chiều sâu, tôi sử dụng tìm kiếm theo chiều rộng để xác định chiều sâu. Lý do tại sao tôi sử dụng tìm kiếm theo chiều rộng ngay từ đầu là để đếm số lần nó đi xuống một bậc do bản chất hành vi tìm kiếm theo chiều ngang của thuật toán.
Điều thú vị về phương pháp này là không giống như cách tôi so sánh từng bậc để tìm chiều rộng tối đa ở giải pháp trước đó, tôi không so sánh bất kỳ array hoặc bất kỳ đường dẫn nào. Thay vào đó, tôi tiếp cận theo chiều ngang.
Tham khảo đầy đủ đoạn code cho giải pháp tìm chiều sâu tối đa của cây tại đây.
Khi bạn nhìn vào giải pháp của tôi, bạn sẽ thấy chẳng có điều gì đặc biệt cả – đó chỉ là một phiên bản sửa đổi của thuật toán tìm kiếm theo chiều sâu cổ điển. Thay vì tìm kiếm trên cây cho đến khi nó đáp ứng một giá trị mục tiêu cụ thể, giải pháp của tôi sẽ tìm kiếm trên cây cho đến khi gặp một nút không có con. Hơn nữa, để giữ một chính xác số lượng độ sâu, chúng tôi chỉ thêm 1 vào counter (đây là biến để giữ số lượng cho độ sâu) khi chúng tôi tiếp cận một chỉ số cha.
Để nhận biết khi nào gặp chỉ số cha, tôi sử dụng định nghĩa cơ bản của cây nhị phân nêu rằng: Mỗi cha phải có tối đa hai nút con. Do đó, trong lúc chạy lặp, tôi chỉ thêm 1 vào counter khi tôi đang ở trên nút gốc trong lần lặp đầu tiên (để bao gồm luôn nút gốc trong số lượng) hoặc nếu độ dài của hàng đợi sau khi xuất hiện giá trị gần đây tương đương với 2.
Một cách khác dễ dàng hơn để tìm thấy chỉ số cha là nối thêm từng nút vào một array. Sử dụng phương trình heap để tìm chỉ số cha, chỉ số // 2, chúng ta có thể theo dõi chính xác nút nào là nút cha. Do đó, chúng ta có thể lặp lại cây một lần nữa và thêm 1 vào counter mỗi khi chúng ta tìm gặp một nút cha mẹ nhờ sử dụng phương trình. Đây là một giải pháp tuyệt vời; tuy nhiên, so với giải pháp đơn giản của chúng tôi chỉ sửa đổi thuật toán tìm kiếm theo chiều sâu vốn chạy theo thời gian tuyến tính, thì giải pháp thay thế sẽ chạy theo thời gian bậc hai.
Xem thêm: Việc làm Developer “chất” tại Hà Nội
Lời kết
Xét về mức độ “khó nhằn” cũng như căng thẳng, một buổi phỏng vấn code sẽ tương tự như bài thi tuyển sinh vào đại học vậy. Chỉ có khác là mức độ khó dễ của đề thi tùy thuộc vào “danh tiếng” của trường đại học đó – Nếu bạn nộp đơn vào trường đại học danh tiếng hơn thì bài thi – các câu hỏi phỏng vấn IT, sẽ càng phức tạp và càng khó đậu hơn. Do đó, hãy chuẩn bị thật nhiều trước khi tham gia phỏng vấn nhé.
Và bạn cũng đừng lo lắng quá, vẫn có hàng nghìn developer làm việc tại những công ty công nghệ lớn và cả start-up nữa. Điều đó có nghĩa là việc có thể chinh phục các buổi phỏng vấn code tại bất kỳ công ty nào không phải là điều hoang đường.
Bạn thấy bài viết hay và cần thiết với nhiều người? Đừng ngại nhấn nút Share bên dưới nhé.
Và đừng quên tham khảo việc làm IT trên ITviec!