Câu hỏi phỏng vấn DSA

Bạn đã giải vài trăm bài toán mà vẫn thấy chưa sẵn sàng, điều này thường có nghĩa là bạn đã luyện sai nửa của bài tập. Phần này chỉ ra điều thực sự được chấm điểm, để việc luyện tập có thể đi đúng hướng.

Một vòng phỏng vấn trực tiếp về cấu trúc dữ liệu và giải thuật đo lường bốn thứ cùng lúc: bạn có nhận ra bài toán thuộc khuôn mẫu nào không, bạn có nêu được cách làm trước khi viết code không, phần triển khai có đúng ở các trường hợp biên không, và bạn có thể lập luận về độ phức tạp thành lời không. Ứng viên tối ưu điều thứ ba và bỏ qua điều thứ hai, rồi bị trừ điểm vì một lời giải đúng nhưng đến mà không có giải thích.

Bước nhận diện này chính là lý do luyện khuôn mẫu tốt hơn luyện số lượng. Bài toán hiếm khi thực sự mới; chúng là những tổ hợp lại. Ngay khi bạn có thể nói đây là cửa sổ trượt trên một bản đồ tần suất trong phút đầu tiên, phần còn lại chỉ là triển khai. Các bộ câu hỏi liên quan theo ngôn ngữ và vị trí nằm ở trung tâm câu hỏi phỏng vấn.

Những khuôn mẫu này chiếm phần lớn những gì được hỏi. Hãy học cách nhận ra tín hiệu chỉ đến từng khuôn mẫu.

• Hai con trỏ. Đầu vào đã sắp xếp, tổng của cặp số, phân vùng tại chỗ, kiểm tra chuỗi đối xứng.
• Cửa sổ trượt. Mảng con liên tiếp dài nhất hoặc ngắn nhất thỏa một ràng buộc.
• Đếm bằng bảng băm. Từ đảo chữ, phần tử trùng lặp, so sánh tần suất, phần tử duy nhất đầu tiên.
• Tìm kiếm nhị phân. Mảng đã sắp xếp, và tìm kiếm trên không gian đáp án khi mảng chưa được sắp xếp.
• Tìm kiếm theo chiều rộng và chiều sâu. Cây, lưới, thành phần liên thông, đường đi ngắn nhất không trọng số.
• Heap và hàng đợi ưu tiên. Bài toán top-k, gộp các luồng đã sắp xếp, tính trung vị liên tục.
• Khoảng. Gộp, chèn và phát hiện chồng lấn sau khi sắp xếp theo điểm bắt đầu.
• Quy hoạch động. Bài toán con chồng lấn: leo cầu thang, đổi tiền xu, khoảng cách chỉnh sửa, dãy con.
• Quay lui. Hoán vị, tổ hợp, tập con, các bài toán ràng buộc.
• Thuật toán đồ thị. Sắp xếp tô pô, hợp - tìm, đường đi ngắn nhất có trọng số.

Các đề bài tiêu biểu, diễn đạt theo cách người phỏng vấn thường dùng:

• Tìm hai số trong một mảng có tổng bằng một giá trị mục tiêu, sau đó làm điều đó mà không dùng thêm bộ nhớ.
• Trả về độ dài của chuỗi con dài nhất không chứa ký tự lặp lại.
• Cho một mảng đã sắp xếp rồi xoay, tìm một giá trị mục tiêu trong thời gian logarit.
• Gộp các khoảng chồng lấn và giải thích tại sao việc sắp xếp là đáng công.
• Đảo ngược một cây nhị phân, sau đó tìm độ sâu lớn nhất của nó.
• Kiểm tra tính hợp lệ của một cây tìm kiếm nhị phân, và nói xem một cách kiểm tra ngây thơ bỏ sót điều gì.
• Đếm số đảo trong một lưới, sau đó nói bạn sẽ xử lý thế nào với một lưới quá lớn so với bộ nhớ.
• Tìm k phần tử xuất hiện nhiều nhất và giải thích lý do chọn cấu trúc dữ liệu của bạn.
• Tính số lượng đồng xu tối thiểu cho một số tiền, và nêu công thức truy hồi.
• Phát hiện một chu trình trong danh sách liên kết, sau đó trả về nút nơi nó bắt đầu.
• Chuyển một cây nhị phân thành chuỗi và ngược lại.
• Cho các điều kiện tiên quyết của môn học, xác định xem lịch học có khả thi hay không.

Một sinh viên mới ra trường phỏng vấn cho vị trí backend nhận được bài toán chuỗi con và bắt đầu gõ code ngay lập tức. Code gần như đúng, nhưng người phỏng vấn dành cả vòng để hỏi nó đang làm gì, và điểm số phản ánh sự im lặng chứ không phải lỗi. Một ứng viên dành bốn mươi giây để nói cửa sổ trên một bản đồ ký tự, mở rộng bên phải, thu hẹp bên trái khi gặp phần tử trùng, theo dõi giá trị lớn nhất đã vượt qua phần khó cứu vãn nhất.

Giải trong im lặng tạo ra phản xạ sai. Vòng phỏng vấn trực tiếp đòi hỏi vừa thuyết trình vừa viết code cùng lúc, và đó là một kỹ năng riêng biệt so với từng cái một.

Hãy thay đổi cách luyện tập chứ không phải bộ đề. Trước khi viết bất cứ điều gì, hãy nói to khuôn mẫu, cách làm và độ phức tạp dự kiến. Viết code trong khi tiếp tục thuyết trình. Khi xong, hãy nêu lại độ phức tạp và nêu tên một trường hợp biên bạn đã xử lý cùng một trường hợp bạn sẽ hỏi thêm. Làm điều này với mười bài toán sẽ xây dựng năng lực phỏng vấn tốt hơn là giải năm mươi bài trong im lặng.

Một buổi phỏng vấn thử cung cấp các câu hỏi tiếp nối, phần không thể tự luyện một mình, và cho bạn bản ghi âm lời thuyết trình của chính bạn để xem lại. Một giới hạn trung thực luôn áp dụng: một bài đánh giá code gõ tay trên trình duyệt có giám sát không phải là một cuộc trò chuyện, và không trợ lý trực tiếp nào nên xuất hiện ở đó. Trung tâm các loại phỏng vấn cho biết định dạng code nào là trực tiếp và định dạng nào được tự động hóa.