Luyện tập bài kiểm tra lập trình theo phong cách Codility

Bài kiểm tra thực tế thường có dạng như thế nào

Không có một bài kiểm tra Codility duy nhất. Codility là một nền tảng: mỗi nhà tuyển dụng chọn các nhiệm vụ, ngôn ngữ được phép sử dụng và thời gian làm bài. Thư mời từ nhà tuyển dụng là hướng dẫn tốt nhất để bạn biết bài kiểm tra của mình sẽ như thế nào.

Thông tin Codility công bố. Codility cho biết mỗi nhiệm vụ được chấm tự động theo các tiêu chí cố định (Codility). Các bài học miễn phí dành cho lập trình viên (Codility) cho thấy dạng nhiệm vụ: một bài toán ngắn, một hàm cần viết và các giới hạn đầu vào được nêu rõ. Chẳng hạn, bài học BinaryGap yêu cầu tìm "một thuật toán hiệu quả" cho đầu vào tối đa là 2,147,483,647 (Codility); một bài học khác có tên Time Complexity (Codility).

Thông tin thường được chia sẻ về bài kiểm tra Codility (từ ứng viên và các tài liệu hướng dẫn, chưa được xác nhận trên trang Codility mà chúng tôi truy cập được):

• Một số nhiệm vụ trong cùng một khoảng thời gian dành cho toàn bộ bài kiểm tra, thường từ 30 phút đến 2 giờ.
• Các bài kiểm tra tính đúng đắn ẩn: mã của bạn được kiểm tra với những trường hợp bạn không nhìn thấy, ngoài ví dụ trong nhiệm vụ.
• Hiệu suất với đầu vào lớn trong các nhiệm vụ thuật toán: một lời giải đúng nhưng chậm có thể bị mất điểm.
• Thời gian bạn làm bài trong giới hạn cho phép không được tính vào điểm số.

Các bài mô phỏng của chúng tôi bao gồm những gì. Mỗi bài mô phỏng đầy đủ có ba nhiệm vụ lập trình trong 90 phút, từ nhiệm vụ dễ hơn đến khó hơn. Bạn viết và chạy lời giải bằng Python, JavaScript, Java hoặc C++; lời giải được kiểm tra với các trường hợp kiểm thử ẩn và bạn nhận điểm cho mỗi trường hợp vượt qua. Nên sử dụng máy tính xách tay. Bạn có thể quay lại và sửa lời giải cho đến khi nộp bài.

Các bài mô phỏng của chúng tôi khác ở điểm nào. Theo thông tin thường được chia sẻ, các nhiệm vụ Codility thực tế được kiểm tra về tính đúng đắn và, với nhiều nhiệm vụ, về hiệu suất khi xử lý đầu vào lớn. Các trường hợp ẩn của chúng tôi có quy mô nhỏ và kiểm tra tính đúng đắn cùng các trường hợp biên, vì vậy lời giải chậm sẽ không bị hết giờ; phần giải thích của mỗi nhiệm vụ cho biết độ phức tạp cần thiết khi đầu vào lớn. 10 câu hỏi miễn phí là dạng trắc nghiệm về tính đúng đắn, độ phức tạp, các trường hợp biên và tốc độ - những kiến thức cần có để vượt qua các bước kiểm tra đó.

Các dạng câu hỏi kèm ví dụ có lời giải

Mỗi dạng câu hỏi có một ví dụ có lời giải, kèm theo lỗi nhiều người dễ mắc phải.

1. Lời giải nào đúng. Nhiệm vụ: trả về số lượng giá trị riêng biệt trong một danh sách. Lời giải: len(set(A)). Cách này đúng với mọi danh sách, kể cả danh sách rỗng, khi kết quả là 0. Lỗi dễ mắc: tự viết vòng lặp với danh sách đã sắp xếp rồi quên phần tử đầu tiên hoặc cuối cùng. Khi một hàm dựng sẵn có thể xử lý công việc, hãy kiểm tra xem hàm đó có xử lý được các trường hợp biên hay không, rồi sử dụng nó.

2. Độ phức tạp thời gian. Một lời giải lặp qua A và gọi max(A[:i]) bên trong vòng lặp. Thao tác cắt lát và max đều xử lý tối đa i phần tử, nên tổng số bước vào khoảng N bình phương chia 2, tức O(N bình phương). Thay vào đó, duy trì giá trị lớn nhất hiện tại sẽ giảm độ phức tạp xuống O(N). Lỗi dễ mắc: thấy một vòng lặp rồi cho rằng độ phức tạp là O(N). Hãy kiểm tra bên trong vòng lặp xem có thao tác cắt lát, tính tổng, đếm hay tìm kiếm nào không.

3. Đầu vào nào khiến chương trình lỗi. Nhiệm vụ: trả về số nguyên dương nhỏ nhất không có trong A. Một lời giải trả về max(A) + 1. Thử A = [1, 2, 3]: kết quả là 4, đúng. Thử A = [1, 3]: kết quả là 4, nhưng số 2 bị thiếu nên đáp án là 2. Thử A = [-3, -1]: kết quả là 0, nhưng đáp án là 1. Lỗi dễ mắc: dừng lại sau khi thử một trường hợp cho kết quả đúng. Hãy chủ động liệt kê các trường hợp biên: có khoảng trống, toàn số âm, rỗng nếu được phép, một phần tử, tất cả các phần tử bằng nhau và các giá trị lớn nhất được phép.

4. Đủ nhanh với N tối đa 100,000. Theo nguyên tắc chung, hãy hướng đến O(N) hoặc O(N log N) với kích thước này. O(N bình phương) tương đương khoảng 10 billion bước, vượt xa giới hạn thời gian thông thường. Lỗi dễ mắc: thử với mười phần tử, khi cách nào cũng có vẻ chạy tức thì. Hãy tự hỏi khối lượng công việc tăng như thế nào khi N tăng.

5. Đọc giới hạn. Nếu giá trị có thể lên tới 1,000,000,000 và N là 100,000, tổng có thể lên đến 100 trillion. Số nguyên của Python xử lý được mức này, nhưng trong các ngôn ngữ có số nguyên kích thước cố định, phép tính sẽ bị tràn. Lỗi dễ mắc: bỏ qua phạm vi giá trị. Phạm vi này cho biết khả năng xảy ra tràn số và những kỹ thuật nào có thể dùng được, chẳng hạn như mảng đếm.

Cách chuẩn bị

1. Trước tiên, hãy đọc thư mời. Ghi lại số nhiệm vụ, tổng thời gian và các ngôn ngữ được phép sử dụng. Nhà tuyển dụng quyết định những điều này, vì vậy đừng tự suy đoán.
2. Dùng một ngôn ngữ bạn thành thạo. Hãy nắm vững danh sách, từ điển, tập hợp, cách sắp xếp và các phương thức xử lý chuỗi trong ngôn ngữ đó để không phải tra cứu.
3. Đọc giới hạn trước khi viết mã. Kích thước đầu vào và khoảng giá trị trong nhiệm vụ cho bạn biết lời giải cần nhanh đến mức nào và cần chú ý đến những trường hợp biên nào, như trong các bài học của Codility (Codility).
4. Đảm bảo lời giải đúng, rồi tối ưu tốc độ. Trước tiên, hãy viết một phiên bản đơn giản nhưng đúng. Nếu độ phức tạp là O(N bình phương) và N có thể lên đến 100,000, hãy tìm cách dùng tổng tích lũy, từ điển, tập hợp hoặc sắp xếp để giảm độ phức tạp.
5. Tự kiểm tra các trường hợp biên. Ví dụ trong đề chỉ là một trường hợp. Hãy thử đầu vào rỗng nếu được phép, một phần tử, tất cả giá trị giống nhau, số âm, giá trị nhỏ nhất và lớn nhất, cũng như N lớn nhất.
6. Học các dạng bài thường gặp. Tổng tiền tố, cửa sổ trượt, đếm bằng từ điển, hai con trỏ, sắp xếp trước và các lựa chọn tham lam đơn giản xuất hiện trong phần lớn bài toán thuật toán ngắn. Các bài học miễn phí của Codility là nơi phù hợp để làm quen với dạng bài (Codility).
7. Viết lời giải hoàn chỉnh trong điều kiện giới hạn thời gian. Trong các bài mô phỏng đầy đủ, bạn sẽ viết và chạy mã với các trường hợp ẩn; hãy luyện tập tương tự với các bài của riêng bạn để việc viết mã trong thời gian giới hạn trở nên quen thuộc.
8. Luyện tập với nhịp độ thực tế. Làm các bài mô phỏng đầy đủ có bấm giờ để việc giải ba nhiệm vụ trong cùng một khoảng thời gian trở nên quen thuộc vào ngày thi.

Cách tính điểm thường gặp

Mỗi nhà tuyển dụng thiết lập cách chấm điểm riêng. Codility cho biết mỗi bài được chấm tự động theo các tiêu chí cố định (Codility), còn mỗi nhà tuyển dụng tự quyết định kết quả nào là đủ tốt. Không có một mức điểm đậu chung cho tất cả.

Theo thông tin thường được ghi nhận về cách áp dụng các tiêu chí đó: điểm của một bài được tính dựa trên các kiểm thử tính đúng đắn ẩn và, với nhiều bài thuật toán, cả các kiểm thử hiệu năng trên dữ liệu đầu vào lớn. Các kết quả này được tổng hợp thành tỷ lệ phần trăm cho từng bài, rồi cho toàn bộ bài kiểm tra. Một lời giải đúng với dữ liệu nhỏ nhưng quá chậm với dữ liệu lớn có thể mất điểm hiệu năng; lời giải không xử lý được một trường hợp biên sẽ mất một phần điểm tính đúng đắn. Vì vậy, các câu hỏi trong bài thi thử của chúng tôi thường hỏi riêng "Lời giải có đúng không?" và "Lời giải có đủ nhanh không?".

Điểm luyện tập của chúng tôi là số câu hỏi do chúng tôi biên soạn mà bạn trả lời đúng, kèm kết quả phân tích theo từng bài để bạn biết nên tập trung vào đâu. Đây là điểm luyện tập, không phải điểm Codility hay kết quả của bất kỳ nhà tuyển dụng nào, và không dự đoán liệu bạn có vượt qua bài kiểm tra hay không.

Những lỗi thường gặp

• Tin vào ví dụ. Ví dụ của một bài chỉ là một trong nhiều trường hợp ẩn. Lời giải có thể vượt qua ví dụ đó nhưng vẫn mất phần lớn điểm.
• Bỏ qua N. Một lời giải đúng có độ phức tạp O(N squared) vẫn có thể không vượt qua kiểm tra hiệu năng khi N = 100,000. Hãy kiểm tra giới hạn trước.
• Thao tác ẩn bên trong vòng lặp. Dùng lát cắt, sum, count, index hoặc "in" trên danh sách bên trong vòng lặp sẽ làm tăng chi phí xử lý.
• Bỏ sót phần tử cuối cùng. Phạm vi bị lệch một đơn vị và vòng lặp kết thúc ở cuối danh sách là những lỗi thường gặp. Hãy tự lần theo bước cuối cùng.
• Chọn giá trị khởi đầu sai. Bắt đầu tìm giá trị lớn nhất từ 0 hoặc giá trị nhỏ nhất từ một số lớn tự đặt sẽ gây lỗi với số âm hoặc số rất lớn. Hãy bắt đầu từ phần tử đầu tiên.
• Thay đổi thứ tự mà bài toán phụ thuộc vào. Sắp xếp là công cụ hữu ích, nhưng không phù hợp khi đáp án phụ thuộc vào vị trí hoặc "phần tử đầu tiên trong danh sách".
• Dành toàn bộ thời gian cho một bài. Hãy nộp một phiên bản đúng cho mỗi bài trước, sau đó cải thiện tốc độ nếu còn thời gian.