## Условие Дан массив целых чисел `nums` и число `k`. Верни `k` наиболее часто встречающихся элементов в любом порядке. **Формат входа:** - `nums` — массив, $1 \leq len(nums) \leq 10^5$, $-10^4 \leq nums[i] \leq 10^4$. - `k` — целое, $1 \leq k \leq$ число уникальных значений. **Формат выхода:** - Массив из `k` чисел. **Пример 1:** ``` Вход: nums = [1, 1, 1, 2, 2, 3], k = 2 Выход: [1, 2] ``` **Пример 2:** ``` Вход: nums = [1], k = 1 Выход: [1] ``` **Ограничения:** - Лучше чем $O(n \log n)$. Time: $O(n \log k)$ или $O(n)$.

Вопрос с собеседования аналитика по теме «Алгоритмы».

Разбор ответа

Получить доступ к ответам — все вопросы →

Что дальше

• Раздел практики →
• Все 3000+ вопросов с разбором →

Похожие вопросы из категории «Алгоритмы»

• Дан массив [5, 2, 8, 1, 9]. Нужно отсортировать без встроенного sort(). Самый простой алгоритм — bubble sort. Реализуй на Python, разбери worst/avg/best case. Где bubble sort реально применяется (хинт: Timsort использует его как fallback на коротких подмассивах)?
• Тебе на собесе дают массив на ~50 элементов почти отсортированный (последние 3 элемента не на месте) и просят отсортировать максимально быстро. Какой алгоритм выберешь и почему insertion sort даст O(n) в этом случае? Реализуй и покажи где Python Timsort использует insertion как часть алгоритма.
• Тебе задают вопрос: «У меня quick sort работает за O(n log n) на random data, но на отсортированном входе тормозит. Почему?» Объясни worst case O(n²) и причину. Какие 3 техники защищают (random pivot, median-of-three, introsort)? Реализуй quick sort с random pivot и обоснуй стабильность.
• Дан массив на 10M элементов которые не помещаются в RAM. Тебя просят отсортировать их на диске (external sort). Какой алгоритм базовый? Реализуй classical merge sort и объясни почему он подходит для external sort (chunks + merge), стабилен, параллелизуется. Сравни с quick sort в этом сценарии.
• У тебя приоритетная очередь задач (job scheduler). Тебе нужно постоянно вытаскивать самую важную и добавлять новые. Какая структура подходит за O(log n) на каждую операцию? Реализуй min-heap (приоритет = меньшее число) через heapq. Покажи top-K largest и median maintenance.
• Дан отсортированный массив на 1M элементов и target. Linear search будет O(n) = слишком медленно. Реализуй binary search за O(log n). Бонус: какая граница (lo<hi vs lo<=hi) корректна? Покажи bisect.bisect_left и bisect_right в Python. Когда применим binary search «по ответу»?
• Тебя просят объяснить как работает Python dict под капотом. Какая средняя/худшая сложность? Расскажи про collision resolution: chaining (linked list в bucket) vs open addressing (linear probing). На каком load factor Python ресайзит (хинт: ~2/3)? Что такое hash flooding attack?
• Дан невзвешенный граф (список друзей в соцсети). Найди кратчайший путь от пользователя A до пользователя B. Если пути нет — верни -1. Восстанови сам путь (последовательность вершин).