Приведи пример типовой задачи

Типовая задача: Реализация LRU Cache

Это одна из самых часто встречающихся на интервью и в production коде задач. LRU (Least Recently Used) кэш является хорошей иллюстрацией баланса между производительностью и простотой, требует знания структур данных и многопоточности.

Описание задачи

Нужно реализовать кэш фиксированной ёмкости, где:

• Добавляем пары (ключ, значение)
• При доступе к элементу — он переходит в "самый свежий" статус
• Когда кэш переполняется — удаляем давно не используемый элемент
• Операции должны быть O(1)
• Должен быть потокобезопасным

Версия 1: Однопоточная (Базовая)

#include <unordered_map>
#include <list>
#include <iostream>

template <typename Key, typename Value>
class SimpleLRUCache {
private:
    struct Node {
        Key key;
        Value value;
    };
    
    int capacity;
    // Хранит (key -> итератор на список)
    std::unordered_map<Key, typename std::list<Node>::iterator> cache_map;
    // Список, где самый свежий элемент в начале
    std::list<Node> lru_list;
    
public:
    SimpleLRUCache(int cap) : capacity(cap) {}
    
    Value get(const Key& key) {
        auto it = cache_map.find(key);
        if (it == cache_map.end()) {
            throw std::out_of_range("Key not found");
        }
        
        // Перемещаем элемент в начало (самый свежий)
        lru_list.splice(lru_list.begin(), lru_list, it->second);
        return it->second->value;
    }
    
    void put(const Key& key, const Value& value) {
        auto it = cache_map.find(key);
        
        if (it != cache_map.end()) {
            // Элемент уже существует — обновляем и перемещаем
            it->second->value = value;
            lru_list.splice(lru_list.begin(), lru_list, it->second);
            return;
        }
        
        // Новый элемент
        if (cache_map.size() >= capacity) {
            // Удаляем самый старый элемент (в конце списка)
            Node& last = lru_list.back();
            cache_map.erase(last.key);
            lru_list.pop_back();
        }
        
        // Добавляем новый элемент в начало
        lru_list.emplace_front(Node{key, value});
        cache_map[key] = lru_list.begin();
    }
    
    void print_cache() const {
        for (const auto& node : lru_list) {
            std::cout << "(" << node.key << ": " << node.value << ") ";
        }
        std::cout << std::endl;
    }
};

int main() {
    SimpleLRUCache<int, std::string> cache(3);
    
    cache.put(1, "one");
    cache.put(2, "two");
    cache.put(3, "three");
    cache.print_cache();     // (3: three) (2: two) (1: one)
    
    cache.get(1);            // Обращаемся к 1
    cache.print_cache();     // (1: one) (3: three) (2: two)
    
    cache.put(4, "four");    // Кэш переполнен, удаляем 2
    cache.print_cache();     // (4: four) (1: one) (3: three)
    
    return 0;
}

Сложность:

• get(): O(1)
• put(): O(1)
• Память: O(capacity)

Версия 2: Потокобезопасная

#include <unordered_map>
#include <list>
#include <mutex>
#include <shared_mutex>

template <typename Key, typename Value>
class ThreadSafeLRUCache {
private:
    struct Node {
        Key key;
        Value value;
    };
    
    int capacity;
    mutable std::shared_mutex cache_mutex;  // Читатели и писатели
    std::unordered_map<Key, typename std::list<Node>::iterator> cache_map;
    std::list<Node> lru_list;
    
public:
    ThreadSafeLRUCache(int cap) : capacity(cap) {}
    
    bool try_get(const Key& key, Value& result) {
        // Читающая блокировка — много потоков могут читать одновременно
        std::shared_lock<std::shared_mutex> read_lock(cache_mutex);
        
        auto it = cache_map.find(key);
        if (it == cache_map.end()) {
            return false;
        }
        
        result = it->second->value;
        return true;
        // Необходимо переместить? Нужна писатель блокировка
    }
    
    bool get(const Key& key, Value& result) {
        std::unique_lock<std::shared_mutex> write_lock(cache_mutex);
        
        auto it = cache_map.find(key);
        if (it == cache_map.end()) {
            return false;
        }
        
        // Перемещаем в начало (требует exclusive lock)
        lru_list.splice(lru_list.begin(), lru_list, it->second);
        result = it->second->value;
        return true;
    }
    
    void put(const Key& key, const Value& value) {
        std::unique_lock<std::shared_mutex> write_lock(cache_mutex);
        
        auto it = cache_map.find(key);
        if (it != cache_map.end()) {
            it->second->value = value;
            lru_list.splice(lru_list.begin(), lru_list, it->second);
            return;
        }
        
        if (cache_map.size() >= capacity) {
            Node& last = lru_list.back();
            cache_map.erase(last.key);
            lru_list.pop_back();
        }
        
        lru_list.emplace_front(Node{key, value});
        cache_map[key] = lru_list.begin();
    }
};

int main() {
    ThreadSafeLRUCache<int, std::string> cache(100);
    
    // Несколько писателей
    std::vector<std::thread> writers;
    for (int i = 0; i < 4; ++i) {
        writers.emplace_back([&cache, i]() {
            for (int j = 0; j < 25; ++j) {
                cache.put(i * 25 + j, "value_" + std::to_string(j));
            }
        });
    }
    
    // Несколько читателей
    std::vector<std::thread> readers;
    for (int i = 0; i < 4; ++i) {
        readers.emplace_back([&cache]() {
            std::string result;
            for (int j = 0; j < 50; ++j) {
                cache.get(j % 100, result);
            }
        });
    }
    
    for (auto& t : writers) t.join();
    for (auto& t : readers) t.join();
    
    std::cout << "Cache operations completed safely" << std::endl;
    return 0;
}

Версия 3: С внешней бизнес-логикой (Real-world)

#include <unordered_map>
#include <list>
#include <mutex>
#include <functional>
#include <chrono>

template <typename Key, typename Value>
class AdvancedLRUCache {
private:
    struct Node {
        Key key;
        Value value;
        std::chrono::system_clock::time_point timestamp;
    };
    
    int capacity;
    int ttl_seconds;  // Time to live
    mutable std::mutex cache_mutex;
    std::unordered_map<Key, typename std::list<Node>::iterator> cache_map;
    std::list<Node> lru_list;
    
    // Колбэк при удалении из кэша
    std::function<void(const Key&, const Value&)> on_evict;
    
    void evict_expired() {
        auto now = std::chrono::system_clock::now();
        auto it = lru_list.rbegin();
        
        while (it != lru_list.rend()) {
            auto age = std::chrono::duration_cast<std::chrono::seconds>
                      (now - it->timestamp).count();
            
            if (age > ttl_seconds) {
                if (on_evict) {
                    on_evict(it->key, it->value);
                }
                cache_map.erase(it->key);
                it = std::list<Node>::reverse_iterator(lru_list.erase(std::next(it).base()));
            } else {
                break;  // Остальные ещё свежие
            }
        }
    }
    
public:
    AdvancedLRUCache(int cap, int ttl = 3600)
        : capacity(cap), ttl_seconds(ttl) {}
    
    void set_eviction_callback(std::function<void(const Key&, const Value&)> cb) {
        on_evict = cb;
    }
    
    bool get(const Key& key, Value& result) {
        std::lock_guard<std::mutex> lock(cache_mutex);
        evict_expired();
        
        auto it = cache_map.find(key);
        if (it == cache_map.end()) {
            return false;
        }
        
        auto age = std::chrono::duration_cast<std::chrono::seconds>
                  (std::chrono::system_clock::now() - it->second->timestamp).count();
        
        if (age > ttl_seconds) {
            cache_map.erase(it);
            return false;
        }
        
        lru_list.splice(lru_list.begin(), lru_list, it->second);
        result = it->second->value;
        return true;
    }
    
    void put(const Key& key, const Value& value) {
        std::lock_guard<std::mutex> lock(cache_mutex);
        evict_expired();
        
        auto it = cache_map.find(key);
        if (it != cache_map.end()) {
            it->second->value = value;
            it->second->timestamp = std::chrono::system_clock::now();
            lru_list.splice(lru_list.begin(), lru_list, it->second);
            return;
        }
        
        if (cache_map.size() >= capacity) {
            Node& last = lru_list.back();
            if (on_evict) {
                on_evict(last.key, last.value);
            }
            cache_map.erase(last.key);
            lru_list.pop_back();
        }
        
        lru_list.emplace_front(Node{key, value, std::chrono::system_clock::now()});
        cache_map[key] = lru_list.begin();
    }
    
    size_t size() const {
        std::lock_guard<std::mutex> lock(cache_mutex);
        return cache_map.size();
    }
};

int main() {
    AdvancedLRUCache<std::string, std::string> cache(10, 60);  // TTL 60 сек
    
    cache.set_eviction_callback([](const std::string& key, const std::string& value) {
        std::cout << "Evicting: " << key << " = " << value << std::endl;
    });
    
    for (int i = 0; i < 15; ++i) {
        cache.put("key_" + std::to_string(i), "value_" + std::to_string(i));
    }
    
    std::cout << "Cache size: " << cache.size() << std::endl;  // 10
    
    std::string result;
    if (cache.get("key_5", result)) {
        std::cout << "Found: " << result << std::endl;
    }
    
    return 0;
}

Ключевые концепции

1. Структуры данных:

• std::list для быстрого перемещения элементов (O(1))
• std::unordered_map для быстрого поиска (O(1))
• Комбинация даёт O(1) для всех операций

2. Многопоточность:

• std::shared_mutex для оптимизации читателей
• std::lock_guard и std::unique_lock для RAII

3. Advanced техники:

• TTL (Time To Live) для автоматического удаления
• Callbacks при удалении
• Профилирование и статистика

Интервью советы

• Начните с простого — однопоточная версия
• Уточняйте требования — нужна ли потокобезопасность?
• Обсуждайте компромиссы — trade-off между памятью и скоростью
• Оптимизируйте постепенно — не усложняйте сразу
• Тестируйте граничные случаи — пустой кэш, полный кэш

LRU кэш применяется в реальных системах: CPU кэши, веб-серверы, CDN, БД кэширование. Понимание её реализации показывает solid инженерные навыки.