**Контекст:** задача LeetCode #146 — классический **system design interview**. Спрашивают везде: Яндекс, Сбер ML, Тинькофф, Netflix, Google. Проверяет глубокое понимание структур данных.
## Условие
Реализовать класс `LRUCache` — **Least Recently Used cache** с двумя операциями:
- `get(key) -> int` — возвращает значение по ключу или -1 если нет
- `put(key, value)` — добавляет или обновляет значение
**Ограничение:** кэш имеет **фиксированную capacity**. Когда capacity превышена — **вытесняется least recently used** элемент (тот к которому давно не обращались через get или put).
**КРИТИЧНО:** обе операции должны работать за **O(1)**.
## API пример
[см. код в задании]
## Зачем нужен LRU Cache в реальности
- **Web browser:** кэш последних страниц
- **CDN (Cloudflare, Cloudfront):** кэш файлов на edge node
- **Database:** buffer pool (PostgreSQL, MySQL)
- **Redis / Memcached:** политика eviction
- **Pandas:** внутренний кэш для expensive operations
- **Python:** `@functools.lru_cache` — именно это
## Требования
1. Реализовать класс `LRUCache` с методами `__init__(capacity)`, `get(key)`, `put(key, value)`
2. **Обе операции: O(1)** амортизированно
3. Обработать edge case: capacity = 0, update существующего ключа
4. Объяснить почему именно **hash map + doubly linked list** работает за O(1)
5. **Bonus:** реализовать через `collections.OrderedDict` одной строкой
## Подсказки по структурам данных
- Hash map alone: O(1) get/put, но **не знаем порядок использования** → нельзя найти LRU
- Linked list alone: можем отслеживать порядок, но **O(n) lookup**
- **Комбинация:** hash map для O(1) доступа к узлу, doubly linked list для O(1) перемещения и удаления
algorithms data-structures linked-list hash-map OOP
Это задание для уровня Senior. Senior-уровень — глубокое понимание темы, опыт решения нестандартных задач, обсуждение trade-off на собеседовании.
Подобные задания в категории «Python» регулярно дают на собеседованиях аналитика данных в Яндекс, Сбер, Ozon, Авито, Тинькофф, Wildberries, T-Bank, X5, ВТБ и других крупных IT-компаниях. Тематика: algorithms, data-structures, linked-list, hash-map, OOP.
На реальном собеседовании на подобную задачу отводится 30-60 минут с обсуждением подходов, оптимизаций и trade-off. Для тренировки рекомендуем сначала решить самостоятельно, потом сверить с эталонным решением и подсказками.
На zasqlpython.ru есть 482 Python задачи с проверкой через Pyodide, конспекты Python и pandas, AI мок-собеседование с разбором ваших ответов.
← Все задания