Дан массив на 100M элементов, нужен 50000-й по величине (medianish). Sort O(n log n) — overkill. Quickselect даёт O(n) average. Реализуй на основе partition из quick sort. Какой worst case O(n²) и как защититься (median-of-medians даёт guarantee O(n) но slow constants).

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

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

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

Что дальше

• Раздел практики →
• Все 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. Восстанови сам путь (последовательность вершин).