C++ with STL list and hash table (unordered_map), 35 lines, 85 ms


  • 0
    C
    • A O(1) average time lookup is possible with a hash table for the get(key) function
    • To manage the LRU order a list is good because it allows to remove/rearrange single elements in all positions in O(1) if you have a hold on them.
    • The idea is to store the linked-list item reference/pointer as values in the hash table. In c++ these are iterators to the linked list. In the LL the pair key/value is stored, so one can remove the key from the HT if an item needs to be dropped due to capacity reasons.
    • the put operation checks if the key is in the map, if so, it moves the referenced item to the front of the list O(1) and sets the value for the case it had changed. If the key wasn't already in the map, it adds an item to the list and an iterator to the list of that newly added item. If the capacity now exceeds (by 1 element), take the last element from the list, get it's key, remove the key from the HT and the element from the list.
    • the get operation is like the first part of the put but it will retrieve the value instead overwriting it (note, it needs to get the hit item in front of the list as well).
    class LRUCache {
    private:
    	std::list<std::pair<int, int>> list_;
    	std::unordered_map<int, decltype(list_)::iterator> map_;
    	int capacity_;
    
    public:
    	LRUCache(int capacity) : capacity_(capacity) { }
    
    	int get(int key) { return getValueInFrontIfExists(key); }
    
    	void put(int key,int value) {
    		if (getValueInFrontIfExists(key) != -1) { // key existed, patch value
    			list_.front().second = value;
    		} else { // key does not exist, add to list and map
    			list_.push_front(std::pair<int,int>(key,value));
    			map_[key] = list_.begin();
    			if (list_.size() > capacity_) { // capacity exceeded, remove least used
    				map_.erase(list_.back().first); // patch map first
    				list_.pop_back(); // remove least used element
    			}
    		}
    	}
    
    private:
    	// gets the value and moves value to front of list if exists otherwise returns -1
    	int getValueInFrontIfExists(int key) {
    		auto it = map_.find(key);
    		if (it != map_.end()) {			
    			int value = it->second->second; // get the value
    			list_.splice(list_.begin(), list_, it->second);
    			return value;
    		}
    		return -1;
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.