Яндекс.Собеседование

Собрал коллекцию задач, которые довелось решать во время прохождения собеседования в Яндекс на позицию Python разработчика.

  1. Симметрия. Дано множество точек {(x,y)}. Требуется узнать, возможно ли провести такую вертикальную прямую, которая разделяла бы множество этих точек на два симметричных относительно этой прямой подмножества.
  2. Лабиринт. На старте вы находитесь в комнате Room, в ней множество ключей Room.keys() и множество дверей Room.doors(), есть возможность попробовать открыть дверь door.open(key) ключом, а затем проверить открылась ли она door.is_open(). Ключ от двери не обязательно находится в той же комнате, что и дверь. Требуется найти такую комнату room, что room.is_final() = True или None, если не существует.
  3. Размен монетами. На вход дается массив доступных в обороте монет coins ( пр. [1,2,5,10]), а также сумма денег money (пр. 23), которую требуется разменять монетами, используя минимально возможное их количество (пр. [10, 10, 2, 1] = 23).
  4. Частичная сумма. На вход дается массив целых чисел A и число X. Требуется выяснить, существует ли такой подмассив B, сумма элементов которых равна X.
  5. OrderedDict. Реализовать класс OrderedDict, который за O(1) осуществлял вставку set(key,val), получение get(key) и удаление del(key) элементов, при этом сохраняя порядок вставки ключей. Можно пользоваться стандартным dict в качестве базы.
  6. Пробелы. На вход дается строка S, которая может содержать два или более подряд идущих пробелов abc___a______с, требуется реализовать функцию, которая бы удаляла лишний пробелы из этой строки abc_a_с за O(n).
  7. “Сжатие” последовательности чисел. На вход дается список целых чисел без повторений больше нуля (пр. [3, 1, 5,6,7, 2, 10]), на выходе необходимо вернуть эту же последовательность, но заданную списком диапазонов, из которых она состоит (пр. [1–3,5–7,10]).
  8. Абсолютный минимум разности. На вход дается два отсортированных списка целых чисел A и B, на выходе необходимо вернуть такие индексы i, j, что абсолютная разность этих двух элементов минимальна среди всех остальных, т.е. , необходимо найти min(abs(A[i]-B[j])) среди всех пар (i,j).
  9. Нормализация путей. Реализовать функцию стандартной библиотеки Python os.path.normpath(path), которая нормализует указанный путь path. Пример нормализации: normpath('/a/c/../../b')-> /b, normpath(./cfg/../etc)-> etc