Можно ли привести решение задачи поиска k наибольших чисел к линейной сложности

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

Отличаете ли вы «отсортировать и взять k» от «найти k наибольших», и умеете ли считать сложность, отделяя средний случай от худшего. Заодно смотрят, спросите ли вы про условия задачи до того, как начнёте писать код.

Как отвечать

Начните с базы: сортировка это O(n log n), куча размера k это O(n log k), и второе уже заметно лучше при малом k. Линейного времени добиться можно, но с оговорками.

Основной ответ это Quickselect. Выбираем опорный элемент, разбиваем массив на меньшие и большие, и спускаемся рекурсией только в ту часть, где лежит нужная граница. Ожидаемое время O(n), потому что обрабатываемый кусок в среднем убывает вдвое. Худший случай O(n^2), и лечится он случайным выбором опорного или алгоритмом медианы медиан, который даёт линейность гарантированно, но с большой константой.

Второй честный вариант: если значения целые и лежат в известном диапазоне, работает подсчёт. Считаем частоты, идём по ним с конца и набираем k штук, это O(n + m), где m это размер диапазона.

Полезно сразу уточнить условие: нужен ли порядок внутри ответа. Если да, то к линейному времени добавится O(k log k) на сортировку самих k элементов.

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

Говорят «Quickselect работает за O(n)», опуская слова «в среднем». Интервьюер почти всегда спросит про худший случай, и ответ про случайный опорный элемент его закрывает, а молчание нет.

Второе: путают «найти k-й по величине» и «вернуть все k». Quickselect отдаёт одно значение и попутно раскладывает массив так, что искомые k лежат по одну сторону от границы. Забыв взять этот срез, возвращают число там, где ждали список.

Третье: не считают память и мутацию. Реализация через фильтры создаёт новые массивы на каждом уровне рекурсии: время линейное, а память уже нет. Классический Quickselect переставляет элементы на месте, и если входной массив чужой, копию надо делать осознанно.