Назад к задачам
ЯндексПолучайте помощь с лайвкодингом в реальном времени с Sobes Copilot
Junior — Senior
6
Обнаружьте и исправьте дефекты в реализации LRU‑кэша
Компании, где спрашивали:
Условие задачи
Найдите недочёты в следующем классе, из‑за которых его нельзя использовать в продакшн‑окружении.
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];
}
};