[LeetCode HARD] 146 LRU Cache

LeetCode has become the de facto go-to website for tech interviews. As a former competitive programmer, the LeetCode “hard”, “medium”, and “easy” problems are more like “easy”, “very easy”, “extremely easy” for me. I think it would be a good idea for me to put my solutions of some of the LeetCode hard problems here. Hope it would be helpful for people who are preparing for tech interviews.

This is my 5th LeetCode solution article, for LeetCode Problem 146, LRU Cache. This problem is not interesting but I found it a very useful interview problem because it works well to weed out people who cannot use basic data structures naturally.

Problem

Write a key-value cache which has a maximum size and keeps the most recent used items.

Solution

The most simple solution is to have a hash table with the key-value pairs and their last operation time. And then we also keep a queue of operations.

Every time a key is access, we put the key into the back of the queue and then update the last operation time in the hash table. When the cache is oversize, we keep looking at the front of the queue to get the oldest operations, then compare it to the hash table to see if that operation is the latest operation for that element. If so, we should remove that element.

Source Code (C++)

#include 
#include 

class LRUCache {
public:
    LRUCache(int capacity) {
        _capacity = capacity;
        _front = _back = 0;
    }
    
    int get(int key) {
        auto ret = _data.find(key);
        if (ret == _data.end()) {
            return -1;
        }
        
        _lastOperation[key] = _back++;
        _operations.push(key);
        return ret->second;
    }
    
    void put(int key, int value) {
        _data[key] = value;
        _operations.push(key);
        _lastOperation[key] = _back++;
        
        while (_data.size() > _capacity && _operations.size() > 0) {
            auto deleteKey = _operations.front();
            // check if the oldest operation in the queue is the latest operation
            // for the corresponding key.
            if (_front == _lastOperation[deleteKey]) {
                _data.erase(deleteKey);
                _lastOperation.erase(deleteKey);
            }
            _front++;
            _operations.pop();
        }
    }
    
private:
    int _capacity;
    std::unordered_map<int, int> _data;
    std::unordered_map<int, long long> _lastOperation;
    std::queue _operations;
    long long _front, _back;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

Complexity

Let n be the number of operations. Then the total time complexity is O(n) because hash table operation is O(1) and there are at most O(n) elements in the queue. Therefore the average time complexity for each operation is O(1).

The space complexity is O(n) because the length of the queue is n in the worst case. In the worst case, an operation can takes up to O(n) if the queue is very long and we need to go over all the elements before we can reduce the size of the cache. In some special use case, for example if this cache is used by a web server, it is important to keep the latency low for every operation, and there are a lot of read operations and not so much write operations, this approach may not be ideal.

A Better Solution

To have better space complexity and better worst case single operation time complexity, we can have a sorted list of keys, ordered by last operation time.

To do this, we should use a doubly-linked list instead of a queue. Every time a key is accessed, we take it out of the list and put it to the back of the list. To do this, for each key, we need to store a pointer to that key in the linked list in the hash table.

This way the time complexity is guaranteed O(1) for every single operation and the space complexity is O(capacity) instead of O(n).

However, this solution is a little bit harder to write because there are pointers. Also it is actually a little bit slower on LeetCode because of the doubly-linked list operations.

Source Code (C++)

#include <list>
#include <unordered_map>

struct LRUCacheNode {
    int value;
    std::list<int>::iterator operation;
};

class LRUCache {
public:
    LRUCache(int capacity) {
        _capacity = capacity;
    }
    
    int get(int key) {
        auto pt = _data.find(key);
        if (pt == _data.end()) {
            return -1;
        }
        _operations.erase(pt->second.operation);
        pt->second.operation = _operations.insert(_operations.end(), key);
        return pt->second.value;
    }
    
    void put(int key, int value) {
        auto pt = _data.find(key);
        if (pt != _data.end())
            _operations.erase(pt->second.operation);
        _data[key] = {value, _operations.insert(_operations.end(), key)};
        
        while (_data.size() > _capacity) {
            _data.erase(*_operations.begin());
            _operations.pop_front();
        }
    }
    
private:    
    int _capacity;
    std::unordered_map<int, LRUCacheNode> _data;
    std::list<int> _operations;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */