Какие вопросы обычно задают на собеседованиях по алгоритмам

Что проверяют

Хотят понять, решаете ли вы задачи вслух и умеете ли оценить своё решение, а не помните ли наизусть сотню задач. Следом почти всегда просят написать код на Kotlin прямо в редакторе и назвать сложность по времени и памяти.

Как отвечать

Покажите, что знаете карту тем и как они всплывают в Android-работе:

• сложность: O-нотация, разница между O(n log n) и O(n²), амортизированная O(1) у ArrayList.add и HashMap.get;
• массивы и строки: два указателя, скользящее окно, префиксные суммы. Классика: подстрока без повторов, слияние интервалов, палиндромы;
• хэш-таблицы: подсчёт частот, пара с заданной суммой, группировка анаграмм. Спросят, как устроен HashMap и зачем согласовывать equals и hashCode;
• стек и очередь: проверка скобок, ArrayDeque вместо устаревшего Stack;
• списки и деревья: разворот списка, поиск цикла, обходы дерева, проверка BST;
• графы: BFS для кратчайшего пути в невзвешенном графе, DFS и топологическая сортировка для зависимостей;
• поиск и сортировка: бинарный поиск, Arrays.sort для примитивов на Dual-Pivot Quicksort, для объектов стабильный TimSort, на нём же держится sortedBy в Kotlin на JVM;
• динамика: лестница, размен монет, наибольшая общая подпоследовательность.

Отдельно бывают задачи с Android-начинкой: написать LRU-кэш (как LruCache, через LinkedHashMap с accessOrder = true), объяснить, что DiffUtil считает разницу списков алгоритмом Майерса, зачем SparseArray вместо HashMap<Int, T> (нет упаковки ключей, но поиск бинарный, O(log n)).

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

Где спотыкаются

Молча пишут код. Интервьюер оценивает ход мысли, и верное решение без объяснений ценится меньше, чем проговорённое неидеальное.

Называют сложность наугад: забывают, что contains у List линейный, и получают O(n²) внутри цикла.

Игнорируют крайние случаи: пустой массив, один элемент, отрицательные числа, переполнение Int при сумме.