Алгоритми та структури даних · Middle · Запитання 27 з 75
Як зазвичай будують LRU-кеш із get і put за O(1)?
- 1Min-купа, впорядкована за часом додавання ключа
- ✓Правильна відповідь: Хеш-таблиця плюс двозв'язний список за давністю використання
- 3Відсортований масив ключів із бінарним пошуком
Пояснення
Map знаходить вузол за ключем, список переносить його на початок за O(1) і викидає хвіст, коли кеш повний. У JavaScript вистачить самого Map: він зберігає порядок додавання, тож при доступі видаліть і заново додайте ключ, а витісняйте map.keys().next().value.