Какие вопросы задают на собеседовании в Яндекс (frontend, middle)?

Question

Маяк · Accepted Answer

1. Напишите функцию, которая проверяет, является ли строка палиндромом, с учётом того, что в строке могут быть строчные и заглавные буквы (регистр не учитывается) и нужно игнорировать все небуквенные символы (пробелы, знаки препинания). Решение должно быть максимально эффективным по памяти — O(1).
2. Что такое алгоритмическая сложность по времени и по памяти, что означает O(1) и O(n), какие алгоритмы линейные, а какие нелинейные?
3. Как определить, является ли символ буквой, не используя регулярное выражение? (приведение символа к нижнему и верхнему регистру и сравнение)
4. Почему в цикле условие на указатели start строго меньше end, а не start <= end? Что будет, если они равны друг другу?
5. Сравните расход памяти решения с двумя указателями и однострочника через replace/reverse (toLowerCase + разворот строки). Какой расход памяти у каждого — константный или линейный?
6. Напишите асинхронную функцию findPath(from, to, getFlights), где getFlights — асинхронная функция, принимающая город и возвращающая массив городов, куда можно из него долететь. Функция должна вернуть отклонённый промис, если пути нет, либо resolved-промис с маршрутом от начальной до конечной точки. Известно, что маршрут единственный, без петель.
7. Какой обход графа использовать для поиска пути — в ширину (BFS) или в глубину (DFS), и почему?
8. Оцените сложность вашего решения задачи findPath по памяти.
9. Предложите входные данные (худший случай), которые убьют это решение по памяти — так чтобы на сервере не хватило памяти.
10. Верно ли утверждение, что если решение требует квадратичного количества памяти, то оно требует не менее квадратичного количества CPU?
11. Предложите более оптимальное решение задачи findPath: как избавиться от хранения полных маршрутов для каждой точки? (хранить для каждой точки только предка — откуда пришли)
12. Восстановите маршрут из словаря предков (для каждой точки известно, откуда пришли), пройдя от конечной точки к начальной.
13. В каких крайних случаях ваше решение восстановления маршрута не будет работать?
14. Как избавиться от квадратичной сложности при восстановлении маршрута, если вы вставляете элементы в начало массива (spread/unshift)? (формировать массив в обратном порядке и развернуть его в конце)
15. Какова сложность операции shift у массива, используемого как очередь, и как обрабатывать очередь, чтобы избежать копирования всех элементов при извлечении из начала?