Leetcode 146. LRU Cache

medium — apple interview problem

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Follow up:
Could you do get and put in O(1) time complexity?

Example

Idea

My implementation.

• std::unordered_map is O(1) complexity — unique key, not sorted key
• std::map is O(logN) complexity — unique key, sorted key.

Use unordered_map for constant time O(1) since we don’t need sorted keys.

unordered_map usage performance

O(1) result with unordered_map

map usage performance

O(logN) result with map

using namespace std;
class LRUCache {
    list<int> history;
    unordered_map<int, pair<int, list<int>::iterator>> cache;    
    int mCapacity;
public:
    LRUCache(int capacity) : mCapacity(capacity){        
    }
    
    ~LRUCache() {
    }
    
    int get(int key) {
        auto itr = cache.find(key);
        if (itr != cache.end()) {
            // if found, update history 
            // so that current key can go to the end of the list
            auto oldPos = (itr->second).second;
            history.erase(oldPos);
            auto newPos = history.insert(history.end(), key);
            // update iterator to history in map 
            cache[key].second = newPos;
            // return value
            return cache[key].first;
        } else {
            return -1;
        }        
    }
    
    void put(int key, int value) {   
        auto itr = cache.find(key);
        if (itr != cache.end()) {
            // if found, update history
            // so that current key can go to the end of the list
            auto oldPos = (itr->second).second;
            history.erase(oldPos);
            auto newPos = history.insert(history.end(), key);
            
            // if key/value alreay in cache, remove it
            cache.erase(itr);
            cache[key] = make_pair(value, newPos);
        } else {
            auto listItr = history.insert(history.end(), key);
            cache[key] = make_pair(value, listItr);
        }
        
        // size check after insert - "after" is important
        if (cache.size() > mCapacity) {
            // remove the first one in the history
            int oldestKey = history.front();
            history.pop_front();
            auto oldestKeyItr = cache.find(oldestKey);
            cache.erase(oldestKeyItr);
        }       
    }
};