Программистские собеседования в 2024

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

Я собрал некоторые из них для разбора.

1. Map

Условие

Необходимо написать класс, который хранит в себе по уникальному ключу некоторый набор значений и наиболее эффективно реализует четыре операции: set, get, remove и is_all_values_unique.

Решение

Для упрощения задачи представим, что все ключи и значения могут быть хэшируемы.

Т. к. у нас есть операции set и get и уникальный набор ключей, то в качестве контейнера для данных лучше всего выбрать класс dict. У него операции вставки и поиска по ключу происходят за O(1).

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

Для реализации последнего условия можно пойти двумя путями:

1. Реализовать метод "в лоб" просто добавлением всех значий словаря в set и потом проверить равна ли длина множества значений количеству ключей словаря. Сложность по времени O(n) и по памяти тоже O(n).
2. Добавить в класс Map еще один словарь, в котором будут инвертированы ключи и счетчик значений, чтобы можно было быстро отвечать на вопрос: "Все ли добавленные значения уникальны?". Дополнительно необходимо добавить в методы обновления и удаления дополнинельные операции с новым словарем. В таком случае мы получим сложность по времени O(1) и по памяти O(n)

В данной реализации можно вынести в отдельный метод удаление старого значения из второго словаря, но, в целом, это уже неплохое решение, в котором все операции работают за O(1).

2. Поиск симметрии

Эту задачу в разных формулировкх получал на 4-х собеседованиях минимум.

Условие

Дан набор точек на плоскости с координатами (x,y), необходимо найти такую точку на оси X, через которую можно провести ось симметрии параллельную оси Y.

Решение

Если ось симметрии можно провести, то она должна лежать ровно по середине между самой левой и самой правой точками. Для того чтобы их найти, можно отсортировать массив точек по X sorted(a, key=lambda point: point[0]) сложность O(n log n). Или просто в цикле найти min/max, в таком случае сложность будет O(n).

После нахождения потенциальной точки симметрии по X необходимо проверить, действительно есть ли для каждой точки в массиве своя симметричная пара. Решение в лоб - перебор массива вложенным циклом и поиск для каждой точки (x+/-symmetric_x;y). Чтобы уменьшить сложность алгоритма, можем воспользоваться множеством - поиск элемента во множестве O(1).

Решение целиком выглядит так:

3. Больше половины

Условие

Дан массив элементов. Гарантируется, что в этом массиве есть такой элемент, который встречается больше n / 2 раз. Необходимо найти этот элемент.

Решение

Здесь можно пойти двумя путями:

1. Отсортировать массив и выбрать центральный элемент. Сложность по времени O(n log n), потребление памяти - O(1).
2. Через счетчик элементов в виде словаря. Сложность по времени O(n), потребление памяти - O(n).

4. Дороги

Условие

Дан массив однонаправленных дорог. Гарантируется, что нет циклов. Сколькими способами можно добраться из пункта 1 в пункт N.

>>> ([[1,2], [2,4], [1,3], [3,4], [1,4]], 4) => 3

Решение

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