LRU cache как generic container: edge cases
Какие edge cases появляются, если LRU cache должен хранить любые пользовательские значения?
Ответить самому
Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.
Короткий ответ
Нельзя смешивать “нет значения” и пользовательские значения вроде None. Нужны sentinel, точный API get/put, обработка capacity и стабильная O(1) структура.
Полный разбор
Если cache хранит любые значения, None может быть нормальным значением. Поэтому get не должен возвращать None как единственный сигнал отсутствия ключа. Используют sentinel object, exception, pair found/value или API с explicit default.
Другие edge cases: capacity 0, повторный put существующего ключа, eviction самого старого элемента, hashability ключей, NaN как ключ/значение, порядок обновления при get и put. Для O(1) обычно нужен dict плюс doubly linked list или OrderedDict-подобная структура.