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

Question

Маяк · Accepted Answer

1. Найти максимальный по длине строго монотонный (строго возрастающий или строго убывающий) подотрезок массива чисел.
2. Оцените сложность вашего решения первой задачи по времени и по памяти.
3. Дан массив целых чисел (возможны отрицательные). Найти непустой подотрезок с заданной суммой X, либо сказать, что такого нет (вывести индексы начала и конца или -1 -1).
4. Почему решение второй задачи через префиксные суммы с линейным поиском работает за O(n^2)? Объясните, откуда берётся квадрат.
5. Как ускорить решение с O(n^2) до O(n) по времени, используя хеш-таблицу (map значений префиксных сумм)? Как при этом изменится потребление памяти?
6. Можно ли решить задачу про подотрезок с суммой X, ограничив себя константной O(1) дополнительной памятью, и за какое время (например, за O(n^2))?
7. Как бы вы тестировали такой код? На каких входных данных?