Сортировки 😕 база
Какая сложность у «наивных» сортировок (пузырьком, вставками)?
O(n²): два вложенных цикла по элементам. На тысячах элементов уже заметно тормозят.
Сортировки 😕 база
Какая сложность у быстрых сортировок (merge, quick)?
O(n log n) — принципиально быстрее: миллион элементов сортируется за миллионы операций, а не за триллионы.
Сортировки 🤓 уверенно
Что использует Collections.sort() в Java?
TimSort — гибрид merge sort и insertion sort, оптимизированный под частично отсортированные данные.
Сортировки 🤓 уверенно
Что такое стабильная сортировка?
Равные элементы сохраняют исходный порядок. Важно при сортировке по нескольким полям подряд.
Сортировки 🧐 глубоко
Опиши идею merge sort — почему получается n log n?
Сортировки 🧐 глубоко
В чём слабое место quick sort и когда он деградирует до O(n²)?
Сортировки 😎 про
Почему сортировка сравнениями не может быть быстрее O(n log n)?
Сортировки 😎 про
Что такое counting sort и когда сортировать можно за O(n)?
Бинарный поиск 😕 база
В чём идея бинарного поиска?
В отсортированном массиве смотрим середину: искомое меньше — идём влево, больше — вправо. Каждый шаг отсекает половину.
Бинарный поиск 😕 база
Какая сложность у бинарного поиска?
O(log n): в массиве из миллиона элементов — максимум 20 шагов.
Бинарный поиск 🤓 уверенно
Какое главное условие для бинарного поиска?
Данные должны быть отсортированы — иначе половину отсекать нельзя.
Бинарный поиск 🤓 уверенно
Где идея бинарного поиска встречается в реальных системах?
Индексы баз данных (B-tree), TreeMap, поиск версии с багом (git bisect).
Бинарный поиск 🧐 глубоко
Какие классические ошибки допускают при реализации бинарного поиска?
Бинарный поиск 🧐 глубоко
Что такое «бинарный поиск по ответу»?
Бинарный поиск 😎 про
Как найти первый/последний вхождение элемента с дубликатами?
Бинарный поиск 😎 про
Как искать в повёрнутом отсортированном массиве?
Two pointers / sliding window 😕 база
В чём идея метода двух указателей?
Два индекса идут по массиву навстречу или друг за другом — многие задачи решаются за один проход O(n) вместо O(n²).
Two pointers / sliding window 😕 база
Что такое sliding window?
«Окно» из двух границ скользит по массиву: правая расширяет, левая сужает. Для задач про подотрезки: максимальная сумма, уникальные символы.
Two pointers / sliding window 🤓 уверенно
Приведи классическую задачу на два указателя.
Найти пару с заданной суммой в отсортированном массиве: указатели с концов, сумма мала — двигаем левый, велика — правый.
Two pointers / sliding window 🤓 уверенно
Как HashMap помогает свести O(n²) к O(n)?
Вместо вложенного перебора «видели ли мы такое» — кладём увиденное в map и проверяем за O(1). Классика — задача Two Sum.
Two pointers / sliding window 🧐 глубоко
Как понять по условию задачи, что подойдёт sliding window?
Two pointers / sliding window 🧐 глубоко
Что такое prefix sum и какие задачи он ускоряет?
Two pointers / sliding window 😎 про
Расскажи идею решения «максимум в каждом окне размера k» за O(n).
Two pointers / sliding window 😎 про
Как связаны two pointers и задача о слиянии отсортированных списков?