Câu hỏi phỏng vấn lập trình AI: Ví dụ và luyện tập

Biết tên các thuật toán vẫn có thể khiến bạn không chắc nên tiếp cận một bài toán mới như thế nào. Những câu hỏi luyện tập này kết nối dữ liệu đầu vào cụ thể với lựa chọn lời giải, giới hạn độ phức tạp và các trường hợp biên mà bạn nên giải thích thành lời.

• Two Sum: trả về hai chỉ số khác nhau có các giá trị cộng lại bằng một mục tiêu. Với [3, 3] và mục tiêu 6, đáp án sử dụng cả hai vị trí. Hãy duyệt bằng bảng băm chứa các giá trị đã gặp, kiểm tra phần bù trước khi lưu giá trị hiện tại. Cách này ngăn việc tái sử dụng một chỉ số. Thời gian kỳ vọng là O(n), với O(n) bộ nhớ bổ sung. Hãy làm rõ cần trả về gì nếu không tồn tại cặp phù hợp.
• Tìm chuỗi con dài nhất không có ký tự lặp lại. Với 'abba', độ dài là 2. Theo dõi vị trí cuối cùng của từng ký tự và duy trì một cửa sổ không có phần tử trùng lặp. Biên trái tuyệt đối không được lùi lại khi một lần xuất hiện cũ nằm ngoài cửa sổ hiện tại. Thời gian kỳ vọng là O(n) với các phép tra cứu bảng băm. Hãy làm rõ thế nào được tính là một ký tự.
• Gộp các khoảng đóng chồng lấn. Với [1, 3], [3, 5] và [8, 10], trả về [1, 5] và [8, 10]. Sắp xếp theo điểm đầu, sau đó mở rộng khoảng hiện tại hoặc bắt đầu một khoảng khác. Việc sắp xếp cho độ phức tạp thời gian O(n log n). Các khoảng đóng có chung đầu mút được xem là chồng lấn; hãy hỏi xem điều đó có khớp với định nghĩa của bài toán không.
• Đảo ngược một danh sách liên kết đơn không có chu trình. Lưu nút tiếp theo trước khi thay đổi con trỏ next của nút hiện tại. Lời giải lặp mất O(n) thời gian và O(1) bộ nhớ bổ sung. Hãy lần theo một danh sách rỗng, danh sách có một nút và danh sách có hai nút. Giải thích phần nào của danh sách đã được đảo ngược sau mỗi vòng lặp.
• Trả về các giá trị của cây nhị phân theo từng tầng. Dùng hàng đợi và xử lý số nút của tầng hiện tại trước khi bắt đầu tầng tiếp theo. Thời gian là O(n); bộ nhớ hàng đợi phụ trợ là O(w), trong đó w là chiều rộng tầng lớn nhất, không tính kết quả trả về. Kiểm thử cây rỗng và cây chỉ có một nút con ở mỗi tầng.
• Xác định liệu mọi khóa học có thể hoàn thành với các điều kiện tiên quyết đã cho hay không. Mô hình hóa các điều kiện tiên quyết thành đồ thị có hướng và dùng sắp xếp tô-pô. Nếu xử lý được ít hơn V đỉnh, đồ thị vẫn còn một chu trình có hướng. Thời gian là O(V + E). Kiểm thử các thành phần không liên thông, một khóa học cô lập và một quan hệ tự phụ thuộc.
• Tìm số đồng xu ít nhất cần dùng để đạt một số tiền. Giả sử số lượng đồng xu không giới hạn và mệnh giá là số nguyên dương. Với [1, 3, 4] và số tiền 6, nếu luôn chọn đồng xu lớn nhất trước thì cần ba đồng xu; 3 + 3 chỉ cần hai. Định nghĩa trạng thái quy hoạch động là số đồng xu tối thiểu cho từng số tiền, bắt đầu với không đồng xu cho số tiền bằng không. Với mục tiêu A và c mệnh giá, phương pháp tiêu chuẩn mất O(Ac) thời gian và O(A) bộ nhớ. Hãy xử lý rõ ràng các số tiền không thể đạt được.

Để luyện tập thêm theo vai trò và chủ đề, hãy khám phá thư viện câu hỏi phỏng vấn.

Hãy xem đề bài sau: Đếm các mảng con liên tiếp không rỗng có tổng bằng một mục tiêu, cho phép giá trị âm. Với [1, -1, 1] và mục tiêu 1, đáp án là 3: một trong hai mảng con [1] chỉ có một phần tử, hoặc toàn bộ mảng.

Bắt đầu bằng phương án cơ sở: chọn từng vị trí bắt đầu rồi mở rộng vị trí kết thúc trong khi duy trì tổng hiện hành. Cách này mất O(n²) thời gian và O(1) bộ nhớ bổ sung. Phương pháp cửa sổ co lại thông thường không đáng tin cậy ở đây vì giá trị âm phá vỡ giả định rằng mở rộng cửa sổ sẽ làm tăng tổng.

Phương pháp nhanh hơn sử dụng tổng tiền tố và bản đồ tần suất. Nếu tổng tiền tố hiện tại là s, mỗi tiền tố trước đó bằng s - mục tiêu sẽ xác định một mảng con có tổng cần tìm. Khởi tạo bản đồ với một lần xuất hiện của tổng tiền tố bằng không, đại diện cho tiền tố rỗng trước khi mảng bắt đầu.

• Thứ tự xử lý: Cộng giá trị hiện tại vào tổng tiền tố, đếm các tiền tố trước đó phù hợp, rồi ghi nhận tiền tố hiện tại. Nếu ghi nhận nó trước, ta sẽ đếm sai một mảng con rỗng khi mục tiêu bằng không.
• Bất biến: Trước khi ghi nhận tiền tố hiện tại, bản đồ chứa tần suất của tất cả tiền tố kết thúc trước vị trí hiện tại.
• Độ phức tạp: Mỗi phần tử thực hiện một số lượng không đổi các thao tác trên bản đồ. Thời gian kỳ vọng là O(n), với giả định các thao tác băm có thời gian kỳ vọng không đổi; bộ nhớ bổ sung là O(n).
• Kiểm tra: Mảng rỗng trả về 0. Với [0, 0] và mục tiêu 0, trả về 3. Khi dùng kiểu số nguyên có độ rộng cố định, hãy xem xét hiện tượng tràn ở cả tổng tích lũy và số lượng kết quả.

Một câu hỏi mở rộng hữu ích là bài toán yêu cầu số lượng hay chính các mảng con. Việc trả về mọi mảng con phù hợp làm phát sinh chi phí đầu ra: một mảng toàn số không có n(n + 1)/2 mảng con không rỗng phù hợp khi mục tiêu bằng không.

Hãy tự thử trước khi yêu cầu trợ giúp, sau đó xin mức can thiệp nhỏ nhất đủ để bạn tiếp tục. Những lời nhắc sau biến cuộc trò chuyện với AI thành bài luyện tập mà bạn có thể kiểm chứng.

• Yêu cầu một gợi ý: Hãy cho tôi một gợi ý về thông tin cần lưu trữ. Chưa cung cấp mã hoặc nêu tên đầy đủ của thuật toán.
• Thử thách lập luận: Đây là bất biến vòng lặp của tôi. Hãy tìm một đầu vào khiến phần triển khai của tôi vi phạm nó, hoặc giải thích tại sao mỗi lần cập nhật đều bảo toàn nó. Hãy tự kiểm tra câu trả lời; sự đồng ý của mô hình không phải là bằng chứng về tính đúng đắn.
• Kiểm tra độ phức tạp: Hãy tính lượng công việc do các thao tác cắt lát, sắp xếp, thao tác trên vùng chứa và lời gọi đệ quy thực hiện trong phần triển khai này. Tên của một thuật toán quen thuộc không xác lập độ phức tạp của mã thực tế.
• Tạo ca kiểm thử: Hãy đề xuất các trường hợp cho đầu vào rỗng, giá trị trùng lặp, giá trị biên và kết quả bất khả thi. Giải thích đáp án kỳ vọng cho từng trường hợp. Hãy tự suy ra các đáp án đó trước khi dùng chúng làm chuẩn kiểm thử.
• Thay đổi một ràng buộc: Lời giải thay đổi thế nào nếu đầu vào đã được sắp xếp, không thể sửa đổi hoặc đến dưới dạng luồng? Giải thích sự đánh đổi mới trước khi viết lại mã.

Hãy hình dung một kỹ sư backend đang chuẩn bị cho vị trí cấp cao tại một nhà cung cấp dịch vụ đám mây. Sau khi giải bài toán đồ thị điều kiện tiên quyết, cô ấy yêu cầu một đối tác luyện tập AI tạo đồ thị không liên thông có chứa chu trình. Sau đó, cô lần theo hàng đợi và giải thích tại sao số đỉnh đã xử lý làm lộ chu trình mà không tham khảo gợi ý.

Sau khi đọc một lời giải đầy đủ, hãy đóng nó lại rồi dựng lại thuật toán, bất biến và các ca kiểm thử từ trí nhớ. Có thể tái tạo mã kém hữu ích hơn khả năng giải thích tại sao mã hoạt động và điều chỉnh nó theo một ràng buộc đã thay đổi.

Để diễn tập cách giải thích lập luận trong hội thoại, hãy truy cập trang phỏng vấn thử.

SubcueAI cung cấp hai giao diện hỗ trợ trực tiếp. Ứng dụng gốc chủ lực dành cho macOS và Windows thu âm thanh hệ thống và micrô của bạn, đồng thời hiển thị hỗ trợ trong một lớp phủ nổi cục bộ. Ứng dụng hoạt động với các ứng dụng họp trên máy tính, bao gồm Zoom và Microsoft Teams.

Tiện ích trình duyệt cũng cung cấp hỗ trợ trực tiếp qua Side Panel trên các trình duyệt Chromium, bao gồm Chrome và Edge. Tiện ích chỉ thu âm thanh của thẻ cuộc họp, hỗ trợ các cuộc gọi trong thẻ trình duyệt như Google Meet. Tiện ích nghe người phỏng vấn qua thẻ đó, không bao giờ thu micrô của bạn và không phiên âm lời ứng viên. Bản dựng Firefox chỉ dành cho luyện tập phỏng vấn thử.

Không giao diện nào thêm bot họp vào cuộc gọi hoặc chèn tập lệnh nội dung vào trang cuộc họp. Với câu hỏi lập trình, hãy phân biệt ngữ cảnh được nói với ngữ cảnh được viết: chỉ thu âm thanh không thể cung cấp đề bài hoặc mã chỉ hiển thị trong trình soạn thảo. Hãy kiểm tra mọi đề xuất dựa trên đúng đề bài, ràng buộc và phần triển khai.

Hãy xác nhận quy định của cuộc phỏng vấn trước khi sử dụng hỗ trợ trực tiếp. SubcueAI không thể ẩn một cách tuyệt đối trong mọi trường hợp. Chia sẻ màn hình, ghi hình, bài đánh giá có giám sát và thiết bị do công ty quản lý nằm ngoài phạm vi bảo đảm về khả năng che giấu. Màn hình được chia sẻ hoặc ghi lại có thể làm lộ lớp phủ hoặc Side Panel, còn các biện pháp kiểm soát thiết bị hoặc giám sát có thể theo dõi hoạt động.

Để xem hướng dẫn thiết lập các giao diện hiện có, hãy đọc hướng dẫn SubcueAI.