Codility 风格编程测试练习

正式测试通常是什么样

Codility 并没有统一的测试。 Codility 是一个平台：每家雇主都会为自己的测试选择任务、允许使用的编程语言和时限。雇主发来的邀请是了解你将参加的测试的最佳参考。

Codility 的介绍。 Codility 表示，每项任务都会根据固定标准自动评分 (Codility)。面向程序员的免费课程 (Codility) 展示了任务的形式：一道简短的问题、需要编写的函数，以及明确列出的输入限制。例如，BinaryGap 课程任务要求针对最大为 2,147,483,647 的输入编写“高效算法” (Codility)，还有一门课程名为 Time Complexity (Codility)。

关于 Codility 测试的常见说法（来自考生和指南，并非我们能打开的 Codility 页面上确认的信息）：

• 在同一个计时器时限内完成几道任务，整个测试通常为 30 分钟至 2 小时。
• **隐藏的正确性测试：**系统会用你看不到的测试用例检查代码，任务中的示例之外还会有其他用例。
• **算法任务对大规模输入的性能要求：**解法即使正确，但速度太慢，也可能失分。
• 你在时限内所用的时间不会计入分数。

我们的模拟测试涵盖的内容。每套完整模拟测试包含三道编程任务，限时 90 分钟，难度从易到难。你可以用 Python、JavaScript、Java 或 C++ 编写并运行解法，系统会根据隐藏测试用例进行检查，并按通过的用例逐一计分。建议使用笔记本电脑。提交前，你可以返回并修改解法。

**我们的模拟测试有哪些不同。**据常见说法，Codility 的实际任务会检查正确性，许多任务还会检查大规模输入下的性能。我们的隐藏用例规模较小，用于检查正确性和边界情况，因此解法不会因为太慢而超时；每道任务的解析都会说明处理大规模输入所需的复杂度。10 道免费题为选择题，考查正确性、复杂度、边界情况和速度，以及通过这些检查所需的思路。

附详细解答的题型示例

每种题型各举一个例子，并指出大多数人容易掉进的陷阱。

1. 哪种解法正确。 任务：返回列表中不同值的数量。解法：len(set(A))。这个解法适用于所有列表，包括空列表，空列表会返回 0。陷阱： 自己写循环处理已排序列表时，漏掉第一个或最后一个元素。如果内置函数就能解决问题，确认它能处理边界情况后再使用。

2. 时间复杂度。 一种解法遍历 A，并在循环中调用 max(A[:i])。切片和 max 每次最多都会处理 i 个元素，因此总步数约为 N 的平方除以 2，复杂度为 O(N 的平方)。改为持续记录当前最大值，复杂度就会变为 O(N)。陷阱： 看到一个循环就认为复杂度是 O(N)。还要检查循环内部是否有切片、求和、计数和查找操作。

3. 哪种输入会导致错误。 任务：返回不在 A 中的最小正整数。一种解法返回 max(A) + 1。试试 A = [1, 2, 3]：结果是 4，正确。试试 A = [1, 3]：结果是 4，但缺少的是 2，因此答案应为 2。试试 A = [-3, -1]：结果是 0，但答案应为 1。陷阱： 找到一个有效案例就停下来。应有意列出边界情况：存在间隔、全是负数、规则允许时的空列表、只有一个元素、所有值相同，以及允许的最大值。

4. N 最大为 100,000 时，解法是否足够快。 粗略来说，这种规模下应争取达到 O(N) 或 O(N log N)。O(N 的平方) 意味着大约 10 billion 步，远超常见时间限制。陷阱： 只用十个元素测试，这时任何方法看起来都很快。想想 N 增大时，工作量会如何增长。

5. 阅读限制条件。 如果数值最大可达 1,000,000,000，且 N 为 100,000，总和可能达到 100 trillion。Python 的整数可以处理这么大的数，但使用定长整数的语言会发生溢出。陷阱： 忽略数值范围。数值范围会告诉你是否可能发生溢出，也会影响某些技巧是否可行，例如使用计数数组。

如何准备

1. **先阅读邀请信息。**留意任务数量、总时长和允许使用的语言。这些由雇主设定，不要想当然。
2. **使用一种你熟悉的语言。**熟练掌握它的列表、字典、集合、排序和字符串方法，不用查阅资料也能使用。
3. **编写代码前先阅读限制条件。**任务中的输入规模和值范围会告诉你解法需要多快，以及哪些边界情况需要考虑，就像 Codility 自己的课程练习一样 (Codility)。
4. **先确保正确，再提高速度。**先写出简单且正确的版本。如果它的复杂度是 O(N squared)，而 N 可能达到 100,000，就试试用运行总和、字典、集合或排序来降低复杂度。
5. **自己测试边界情况。**任务中的示例只是其中一种情况。如果允许，试试空输入、只有一个项目、所有值都相同、负数、最小值和最大值，以及最大的 N。
6. **学习常见模式。**前缀和、滑动窗口、用字典计数、双指针、先排序和简单的贪心选择，能应对大量简短的算法任务。Codility 的免费课程是了解这类题目风格的好地方 (Codility)。
7. **限时完成完整解题。**我们的完整模拟测试会让你编写并运行代码，通过隐藏测试用例进行检验；你也可以用自己找的任务进行同样的练习，让限时编写代码变得习以为常。
8. **按照真实节奏练习。**参加完整的限时模拟测试，熟悉在同一计时器下完成三道任务，这样到了考试当天就能从容应对。

评分通常如何进行

**评分规则由各雇主设定。**Codility 表示，每项任务都会按照固定标准自动评分（Codility），而每位雇主会自行决定什么结果才算合格。没有通用的及格线。

关于这些评分标准的运作方式，常见说法是：任务分数来自隐藏的正确性测试；对于许多算法任务，还会根据大规模输入进行性能测试。两者会合并为该任务的百分比得分，再汇总为整场测试的得分。某个解法在小规模输入下正确，但处理大规模输入时速度太慢，可能会失去性能分；如果解法无法通过某个边界情况，则会失去部分正确性分数。这就是为什么我们的模拟测试会分别问“它正确吗？”和“它够快吗？”。

我们的练习分数是你答对的自编题目数量，并按任务列出明细，帮助你了解该重点练习哪些内容。这只是练习分数，不是 Codility 分数或任何雇主给出的结果，也无法预测你能否通过测试。

常见错误

• 相信示例。 任务中的示例只是众多隐藏测试用例中的一个。解决方案可能通过示例，却仍然在大多数评分项上失分。
• 忽略 N。 正确的 O(N 平方) 解法也可能无法通过 N = 100,000 时的性能检查。先查看限制条件。
• 循环中隐藏的工作。 在循环中对列表进行切片、求和、计数、查找索引或使用 "in"，都会增加运算成本。
• 漏掉最后一项。 范围边界差一位，以及运行到列表末尾时出错，是很常见的问题。手动推演最后一步。
• 起始值错误。 将最大值初始设为 0，或将最小值设为一个随意设定的大数，在遇到负数或非常大的值时就会出错。用第一项作为起始值。
• 改变任务所依赖的顺序。 排序是个好工具，但如果答案取决于位置或"列表中的第一项"，就不适用了。
• 把所有时间花在一个任务上。 先确保每个任务都提交了正确的版本，然后再利用剩余时间提升速度。