Алгоритмические задачи на 90 минут

Реальные задачи с собеседования "светить" некорректно, поэтому я буду рассказывать только о пробных задачах или найденных в интернете.

Задания надо выполнять на сайте hackerrank.com или аналогичном.

Пример простой задачи: "есть массив целых чисел, надо найти пропущенное число и вернуть его. Если что-то не так, то вернуть null". Несколько наборов данных для тестирования полностью открыты, несколько закрыты (показано только тест "прошел", "не прошел", "ошибка выполнения", "упал по памяти", "упал по времени" - можно исправить программу и запустить тесты заново).

• Сначала как в анекдоте "чё тут думать - прыгать надо". Брутфорс: пройти по массиву, чтобы найти минимальное и максимальное значения; пройти еще раз, чтобы найти минимальное+1; пройти еще раз, чтобы найти минимальное+2; и т.д.
• Запускаю тесты - один "упал по timeout". Догадаться о причине легко - сложность такого алгоритма O(n^2). Для простого теста с десятком чисел получится 10^2 = 100 операций, алгоритм сработает. А вот для миллиона чисел уже будет 10^12 операций, программа "упадет". Надо оптимизировать.
• Вспомнил школьную математику: сумма прогрессии равна (a1 + an) * n / 2. Достаточно пройти массив один раз, подсчитывая сумму, минимальное и максимальное значения. 10 строчек кода. Сложность алгоритма O(n), такой даже на миллионе чисел будет работать быстро.
• Теперь ни один тест не "упал", но многие "не прошли". Проблема в том, что не прошли только закрытые тесты, поэтому причина непонятна. Можно только догадываться. Чтобы найти проблему, надо мыслить как тестировщик.
• Добавил проверку, что пропущенное число 0 - это вовсе не 0, а "ничего не пропущено". Значит, надо вернуть null.
• Добавил проверку, что в массиве два или более значений.
• Добавил проверку проверку, что числа целые.
• Добавил проверку, что минимальное число больше нуля.
• Добавил проверку, что пропущенное число меньше максимального, иначе означает, что пропущено не одно число, а несколько.
• Ура! Теперь все тесты "прошли"
• Эти тесты проверяют ваше мышление, знание нюансов конкретного языка (тем более, что вы сами его выбрали), обработку исключений и еще многое, что нужно любому программисту. В том числе внимательность и память, потому что в видео по вышеуказанной ссылке рассказывали про некоторые из оптимизаций и тестов.

Пример сложной задачи: "Есть массив из 3х элементов с линейными размерами кузова грузовика. И есть многомерный массив с линейными размерами посылок. Можно ли разместить все посылки в машине? Посылки можно поворачивать и ставить друг на друга." Если перебирать все варианты, то каждую посылку можно поставить на ее любую сторону (n^3), повернуть (n^3^2 = n^6), ставить сбоку-спереди-сверху (n^6^3 = n^18). Принципиально перебора не избежать, но можно и нужно оптимизировать: после каждого шага проверять, что если этот вариант хуже предыдущего, то не продолжать его. Можно один раз перебрать все посылки, чтобы найти лучшие и худшие варианты, их рассматривать отдельно, а не каждый-с-каждым. Проверить, что посылка не больше грузовика. Сначала грузить самые большие коробки. И т.д.

Таких оптимизаций много, и они не всегда очевидные. По-моему, идеально решить эту задачу за час невозможно - в реальности я бы оценил ее сложность в неделю, а вместе со всеми тестирования и улучшениями - в месяц.

Я решал другую задачу, но аналогичной сложности. Многие тесты падали по нехватки памяти или timeout, но мне это решение все равно зачли.

Тут хорошо подходит аналогия со спортивными соревнованиями "рогейн", когда физически невозможно выполнить всё, но надо сделать как можно больше.