В настоящее время работа программиста все чаще становится удаленной, основанной на фрилансе. Это удобно как нанимателю, так и работнику. В этих условиях работодатели часто прибегают к он-лайн тесту, чтобы проверить уровень нанимаемого сотрудника. Типичным примером такой тестовой системы является codility.com, где уровень сложности задач варьируется в зависимости от требований нанимающей компании.
Обычно в таком тесте язык программирования выбирает тестируемый. Мы будем использовать Python 3.x, как наиболее востребованный в наше время.
Давайте с вами разберем несколько типичных задач по программированию разной сложности. Для успешного прохождения теста необходимо свободно владеть основами синтаксиса и базовыми структурами языка (типы данных, операции с ними, классы, списки, строки, множества, словари и т.д.), а также хорошо знать математику в части комбинаторики, статистики и иногда теории вероятности. Хорошее знание математики часто позволяет выбрать оптимальный алгоритм решения, что сильно упрощает программный код и делает его очень эффективным.
Задания обычно оцениваются с точки зрения точности решения (безошибочности ответов при разных входных данных) и производительности (как долго выполняется код, особенно на больших массивах данных, какой ресурс памяти при этом необходим), а также в условиях ограничения времени, отведенного для кодирования.
Точность решения. Это самый важный критерий, задача может решаться долго, но решение должно быть правильным. Помимо основного алгоритма, важно правильно отработать пограничные условия. Правильно ли код работает на границах интервалов, при аномально больших, малых или повторяющихся значениях? Все ли исключения предусмотрены?
Производительность. Главный параметр, это время работы (time complexity) алгоритма в зависимости от размера массива входных данных. Наиболее частое требование к алгоритму, это обеспечить не более, чем линейную зависимость времени процессирования от размера данных.
Обозначается это как O(N). Это значит, что для решения задачи можно использовать один или несколько не вложенных циклов. При вложении двух циклов, вы уже получаете O(N^2) и т.д. Этого надо избегать, по возможности применяя циклы последовательно. Также надо учитывать временную затратность встроенных функций языка. В частности команда count(x) имеет time complexity O(N), а sort() – O(NlogN). Также учитывайте, что использование рекурсивных алгоритмов приводит к степенному росту времени работы программы.
Оптимальным временным критерием является достижение константной характеристики O(1), что означает отсутствие зависимости времени работы алгоритма от размера входящих данных. Очевидно, что этого невозможно добиться для всех задач.
Давайте рассмотрим ряд задач, и начнем с самых простых.
Задача 1 (Пропущенное целое).
Задан проиндексированный с нуля (zero indexed) массив целых чисел A размерности N. Надо найти минимальное целое число n, отсутствующее в массиве A.
Например, пусть A = [1, 3, 2, 10, 4, 7, 6]. В этом случае правильным ответом будет 5.
- N меняется в пределах [1, … 1,000,000,000]
- Если массив не имеет пропуска, программа должна вернуть значение N+1
Решение
Наиболее простой способ, который сразу приходит в голову, это сделать цикл по целым числам и найти минимальное отсутствующее число. При этом, размер цикла достаточно задать в пределах N+1, учитывая что массив задан из N целых чисел.
Данное решение является простым и корректным, но не производительным. Очевидно, что time complexity O(N^2), что неудовлетворительно.
Для улучшения производительности, давайте вспомним о структуре множеств в Python и воспользуемся этим, задав и сравнив два множества.
Такое решение во много раз эффективнее по производительности и близко к константному O(1).
Задача 2 (Минимальный периметр).
Задан прямоугольник площади N, где N – целое число. Необходимо найти цело-численные стороны прямоугольника с минимально возможным периметром.
Решение
Такую задачу можно довольно просто решить простым перебором возможных сторон, задав цикл от 1 до N. И это решение будет O(N), что хорошо. Но решение можно и оптимизировать, вспомнив из курса школьной геометрии, что прямоугольник с минимальным периметром это квадрат. Поэтому, минимальным периметром будет вариант со стороной максимально близкой к sqrt(N).
Очень элегантное решение с time complexity O(sqrt(N)).
Задача 3 (Числа Фибоначчи)
Классическая задача вычисления n-го числа из последовательности Фибоначчи. Последовательность задается следующим правилом:
F[0] = 0, F[1] = 1, F[n] = F[n-1] + F[n-2]
Первые числа последовательности:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 …
Также будет полезно вспомнить формулу Бине.
А также матричный вариант расчета:
[ [1, 1] , [1, 0] ] ^ n = [ [F[n+1], F[n]] , [F[n], F[n-1]] ]
Давайте рассмотрим несколько реализаций.
Вариант 1 (рекурсивный) – O(2^N)
Вариант 2 (итеративный) – O(N)
Вариант 3 (по формуле Бине) – O(1)
Вариант 4 (матричный) – O(1)
Заметим, что матричная реализация требует загрузки библиотеки numpy, что часто не приветствуется или просто не разрешается при тестировании. В отличие от библиотеки math, которой пользоваться можно.
Также применение формулы Бине означает, что вы использовали внешний источник (например, Wikipedia).
Поэтому, для целей тестирования предпочтительным вариантом является итеративный алгоритм.
Вот так различается время выполнения различных алгоритмов:
(to be continued…)
