Алгоритмическая секция | 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 кабины