## Условие Реализуй структуру данных `LRUCache` с операциями: - `get(key)` — вернуть значение, если ключ есть; `-1` иначе. Считается «использованием» ключа. - `put(key, value)` — добавить или обновить. При превышении capacity — выкинуть **наименее недавно использованный** ключ. **Формат входа:** - `capacity` — целое, $1 \leq capacity \leq 3000$. - До $2 \cdot 10^5$ операций `get` / `put`. - $0 \leq key, value \leq 10^4$. **Формат выхода:** - Для каждого `get` — значение или `-1`. **Пример:** ``` LRUCache cache(2) cache.put(1, 1) cache.put(2, 2) cache.get(1) → 1 cache.put(3, 3) # выкинул ключ 2 (LRU) cache.get(2) → -1 cache.put(4, 4) # выкинул ключ 1 cache.get(1) → -1 cache.get(3) → 3 cache.get(4) → 4 ``` **Ограничения:** - `get` и `put` — оба должны быть **$O(1)$ average**.

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

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

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

Что дальше

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