Algorytmy i struktury danych · Middle · Pytanie 27 z 75
Jak zwykle buduje się cache LRU z get i put w O(1)?
- 1Min-kopiec uporządkowany według czasu dodania klucza
- ✓Poprawna odpowiedź: Mapa plus lista dwukierunkowa uporządkowana według ostatniego użycia
- 3Posortowana tablica kluczy z wyszukiwaniem binarnym
Wyjaśnienie
Mapa znajduje węzeł po kluczu, lista przenosi go na początek w O(1) i usuwa ogon, gdy cache jest pełny. W JavaScripcie wystarczy sam Map: zachowuje kolejność wstawiania, więc przy dostępie usuń i dodaj klucz ponownie, a wyrzucaj map.keys().next().value.