Объясни top-K через кучу
Вопрос
Объясни, как найти k самых частых элементов массива и какая сложность у вариантов.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Сначала считает частоты в Map
Предлагает min-кучу размера k по частоте: O(n log k)
Объясняет выбор min-кучи для k наибольших
Упоминает bucket sort по частоте за O(n) как альтернативу
Говорит, что в JS кучу пишут сами
Что могут спросить следом
- Когда сортировка проще и достаточно хороша?
- Как поступить с одинаковыми частотами?
- Что если данные не помещаются в память?
Разбор
Первым шагом считаю частоты в Map, это O(n). Дальше есть варианты. Самый простой: отсортировать пары по частоте и взять первые k, это O(m log m), где m число уникальных. Лучше min-куча размера k: иду по парам, кладу в кучу, и если размер превысил k, извлекаю минимум. В куче остаются k самых частых, в вершине наименее частый из них, его и вытесняем. Это O(m log k), память O(m + k). Есть и линейный вариант: корзины по частоте, массив длины n + 1, где индекс это частота; идём от конца и собираем k элементов, O(n). В JS кучи нет в стандартной библиотеке, поэтому либо пишу свою на массиве, либо договариваюсь с интервьюером использовать сортировку при малых данных.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.