Алгоритмическая секция | Live-coding - как проходить?

Очень мало компаний, которые выделяют алгоритмы (или лайвкодинг, далее все это будет алгоритмами😎) в отдельную секцию. Обычно данные секции вставляют вместе с вопросами по ML или по питону. Но идея везде одна, и она поможет вам проходить алгоритмический секции максимально эффективно. Более того, данный подход уместен на практике и взять ровно оттуда.

Что проверяет алгоритмическая секция?

Дело в том, что алгосекция не проверяет ваши знания алгоритмов. Она проверяет, можете ли вы написать несложную программу с первого раза. Она проверяет, можете ли вы думать, прежде чем делать. И все. Не нужно иметь колоссальных познаний о алгоритмах и типах данных. Достаточно быть внимательным и предусмотрительным.

Но как?

В программировании есть шикарная техника разработки TDD(Test Driven Development). Идея метода состоит в том, что сначала мы пишем тесты для программы, а потом сам функционал.

Эта техника является ключевой для правильного решения задачи, и сейчас расскажу подробнее.

Рассмотрим на примере:

В магазине есть подарочные карты заданного номинала, по одной штуке на каждый номинал. Покупатель хочет приобрести 2 карты, чтобы их суммарный номинал был равен N. Написать алгоритм, который бы определил номиналы карт, который бы ему подошел.

cards_1 = [1, 2, 3, 4, 5]
cards_2 = [20, 5, 10, 15, 30]
nominal = 20

Алгоритм решения:

Читаем условие задачи и пытаемся придумать примеры, которые могут быть критичны. Например:
- А что если миниммальная сумма стоимости карт меньше номинала?[10, 20], [30, 40], 5 -> ?
- А если один из списков пустой?
- А если подходящих номиналов несколько?
Сразу фиксируем данные тесты для последующей проверки. Если есть тесты, которые вызывают вопросы, спрашиваем у интервьюера.

Проговариваем решение вслух.
Как только мы учли все случаи, которые нам пришли в голову переходим к решению. Сначала придумываем самое простое решение, которое вы можете придумать:


"В данной задаче можно пройтись сначала по первому списку, потом по второму и считать, когда сумма будет равняться номиналу, но данное решение будет работать за O(N * M) и кажется слишком простым, возможно, получится быстрее решить задачу."
PS N и M длины первого и второго списка соответственно.

И потом начинаем рассуждать над его улучшением:

"На каждом шаге основного цикла мы просто проверяем вхождение элемента в список за O(M) N раз, возможно, можно оптимизировать этот процесс. Есть смысл использовать словарь для второго списка, так как скорость проверки наличия элемента в словаре равен O(1). Таким образом, нам удастся снизить время выполнения до O(max(M, N)), что вполне себе линейно"

Пытаемся понять, можно ли быстрее:

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

И учитываем тонкости новой реализации:

"Так как нас попросили посчитать все возможные комбинации таких карт, нужно не забыть учесть дубли"

И тут дописываем еще один тест на этот случай.
Все, теперь мы готовы написать код программы!

Пишем само решение и после прогоняем несколько тестов.
Вы великолепны!

Немного общих советов

- В таких собеседованиях программу оформляем в виде функции, поэтому не забывайте писать тайпинги, подробнее про них можно прочитать тут
- Всегда проговаривайте, что вы делаете, чтобы у экзаменатора всегда было ощущение, что вы понимаете, что делаете
- Тесты стоит писать между условием и решением, чтобы они были перед глазами. Пишите тесты в одном формате
- Используйте короткие тесты. Очень тяжело и опасно прогонять длинные тесты (обычно в условии задачи именно такие). Пишите минимальные тесты, закрывающие конкретную проблему
- Когда прогоняете тесты, фиксируйте в блокноте промежуточные значения, иначе вероятность того, что вы запутаетесь, возрастет в разы
- Не забывайте про нейминг!

Желаю удачи!

Раскатываем ML кабины