## Условие Дан массив `prices`, где `prices[i]` — цена акции в день `i`. Можно совершить **одну** покупку и одну продажу (продать позже, чем купить). Найди максимальную прибыль. **Формат входа:** - `prices` — массив целых положительных чисел, $1 \leq len(prices) \leq 10^5$. - $0 \leq prices[i] \leq 10^4$. **Формат выхода:** - Целое число — максимальная прибыль. Если прибыль невозможна, верни 0. **Пример 1:** ``` Вход: prices = [7, 1, 5, 3, 6, 4] Выход: 5 ``` Объяснение: купить в день 2 (price=1), продать в день 5 (price=6). Прибыль = 6 − 1 = 5. **Пример 2:** ``` Вход: prices = [7, 6, 4, 3, 1] Выход: 0 ``` Объяснение: цена только падает — лучше не покупать. **Ограничения:** - За один проход. Time: $O(n)$, Space: $O(1)$.

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

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

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

Что дальше

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