Подготовка к тесту по программированию в стиле Codility

Как обычно выглядит настоящий тест

Единого теста Codility не существует. Codility - это платформа: каждый работодатель сам выбирает задания, разрешённые языки программирования и лимит времени для своего теста. Приглашение от работодателя - лучший ориентир для вашего теста.

Что сообщает Codility. Codility пишет, что каждое задание автоматически оценивается по фиксированным критериям (Codility). Бесплатные уроки для программистов (Codility) показывают формат заданий: краткая задача, функция, которую нужно написать, и указанные ограничения на входные данные. Например, задание из урока BinaryGap предлагает найти «эффективный алгоритм» для входных данных до 2,147,483,647 (Codility), а один из уроков называется «Временная сложность» (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 миллиардов шагов - намного больше, чем обычно позволяет ограничение по времени. Ловушка: проверять решение на десяти элементах, когда все подходы кажутся мгновенными. Подумайте, как растёт объём работы при увеличении N.

5. Чтение ограничений. Если значения могут достигать 1,000,000,000, а N равно 100,000, сумма может достигнуть 100 триллионов. Целые числа Python с этим справятся, но в языках с целыми числами фиксированного размера произойдёт переполнение. Ловушка: не учитывать диапазон значений. Он помогает понять, возможно ли переполнение и какие приёмы доступны, например массив подсчётов.

Как подготовиться

1. Сначала внимательно прочитайте приглашение. Отметьте число заданий, общее время и доступные языки программирования. Эти условия устанавливает работодатель, поэтому не делайте предположений.
2. Выберите один хорошо знакомый язык. Наизусть знайте его списки, словари, множества, сортировку и методы работы со строками, чтобы не искать их в справочнике.
3. Перед написанием кода изучите ограничения. Размер входных данных и диапазоны значений в задании подскажут, насколько быстро должно работать решение и какие граничные случаи важны, как и в заданиях из уроков Codility (Codility).
4. Сначала добейтесь правильности, затем ускорьте решение. Сперва напишите простое и правильное решение. Если его сложность - O(N в квадрате), а N может достигать 100,000, попробуйте использовать накопительную сумму, словарь, множество или сортировку, чтобы уменьшить сложность.
5. Самостоятельно проверьте граничные случаи. Пример в задании - лишь один случай. Если это допускается, проверьте пустой ввод, один элемент, одинаковые значения, отрицательные числа, минимальные и максимальные значения и максимальное N.
6. Изучите распространённые шаблоны. Префиксные суммы, скользящее окно, подсчёт с помощью словаря, два указателя, предварительная сортировка и простые жадные решения подходят для многих коротких алгоритмических заданий. Бесплатные уроки Codility помогут познакомиться с форматом (Codility).
7. Пишите полные решения на время. В наших полных пробных тестах вы пишете и запускаете код, проверяемый на скрытых случаях. Тренируйтесь так же на собственных задачах, чтобы привыкнуть писать код на время.
8. Тренируйтесь в реальном темпе. Проходите полные пробные тесты с таймером, чтобы в день теста вам было привычно решать три задания за один отведённый промежуток времени.。

Как обычно оценивают результаты

Систему оценивания устанавливает каждый работодатель. Codility сообщает, что каждое задание автоматически оценивается по фиксированным критериям (Codility), а каждый работодатель сам решает, какой результат считать достаточным. Универсального проходного балла нет.

Согласно распространённым сведениям, критерии работают так: балл за задание складывается из проверок правильности, которые участник не видит, а для многих алгоритмических заданий - ещё и из проверок производительности на больших входных данных. Их результаты объединяются в процентный балл за задание, а затем за тест. Решение, которое верно для небольших входных данных, но работает слишком медленно на больших, может потерять баллы за производительность. А решение, которое не справляется с граничным случаем, теряет часть баллов за правильность. Поэтому в наших пробных тестах мы отдельно спрашиваем: «Оно правильное?» и «Оно достаточно быстрое?».

Наш тренировочный результат - это количество заданий из наших материалов, на которые вы ответили правильно, с разбивкой по заданиям. Так вы увидите, на чём сосредоточиться. Это тренировочный результат: он не является результатом Codility или какого-либо работодателя и не предсказывает, пройдёте ли вы тест.

Типичные ошибки

• Доверие примеру. Пример в задании - лишь один из множества скрытых тестов. Решение может пройти его и всё равно не набрать большую часть баллов.
• Игнорирование N. Правильное решение со сложностью O(N в квадрате) может не пройти проверки производительности при N = 100,000. Сначала проверьте ограничения.
• Скрытые операции внутри цикла. Срез, сумма, подсчёт, поиск индекса или оператор "in" для списка внутри цикла увеличивают затраты.
• Пропуск последнего элемента. Ошибки на единицу и циклы, которые заканчиваются на конце списка, - классическая проблема. Проверьте последний шаг вручную.
• Неверные начальные значения. Если задать максимум равным 0 или минимуму - произвольное большое число, решение даст сбой на отрицательных или очень больших значениях. Начинайте с первого элемента.
• Изменение порядка, от которого зависит задание. Сортировка - отличный инструмент, но не тогда, когда ответ зависит от позиций или от того, какой элемент «первый в списке».
• Всё время уходит на одно задание. Сначала отправьте правильное решение для каждого задания, а затем, если останется время, повышайте скорость.