Назад к задачам
Junior — Senior
6

Обнаружьте и исправьте дефекты в реализации LRU‑кэша

Компании, где спрашивали:

ЯндексЯндекс
Получайте помощь с лайвкодингом в реальном времени с Sobes Copilot
Условие задачи

Найдите недочёты в следующем классе, из‑за которых его нельзя использовать в продакшн‑окружении.

class TLruCache {
private:
    int maxSize = 0;
    int timestamp = 0;
    unordered_map<int, int> lastAccess;
    unordered_map<int, int> storage;
    set<pair<int, int>> orderSet;

public:
    TLruCache(int sizeLimit) : maxSize(sizeLimit) {}

    void Erase(int key) {
        if (!storage.count(key)) {
            throw runtime_error("key not found");
        }
        orderSet.erase({lastAccess[key], key});
        lastAccess.erase(key);
        storage.erase(key);
    }

    void Set(int key, int value) {
        if (storage.count(key)) {
            orderSet.erase({lastAccess[key], key});
            storage.erase(key);
            lastAccess.erase(key);
        }
        if (orderSet.size() == maxSize) {
            auto [_, evictKey] = *orderSet.begin();
            Erase(evictKey);
        }
        lastAccess[key] = timestamp++;
        storage[key] = value;
        orderSet.insert({lastAccess[key], key});
    }

    int Get(int key) {
        if (!storage.count(key)) {
            throw runtime_error("key not found");
        }
        orderSet.erase({lastAccess[key], key});
        lastAccess[key] = timestamp++;
        orderSet.insert({lastAccess[key], key});
        return storage[key];
    }
};