LRU Cache

Problem

We are given a class called LRUCache and we have to implement the logic for the methods get and put.

Intuition

We can think of the entries in the cache as key-value paris in a Map or a Node in a LinkedList. When we insert or update an entry, it should be marked as recently used. If you iterate through your Map Object, the entries are iterated by their insertion order. So, the last thing you insert, will be the last item seen by the operator. That means that if an entry exists in the collection, which we need to update using our put method, all we have to do is delete that entry and insert it. Which marks it as a recently used entry. If we were to do the same operation using a doubly linked list, we would need to store that entry in a dictionary, and use field called previous and next in that entry to remove it from the linked list.

Solution

 
var LRUCache = function(capacity) {
    this.capacity = capacity
    this.cache = new Map()
};
 
LRUCache.prototype.get = function(key) {
    if (!this.cache.has(key)) return -1
 
    const val = this.cache.get(key)
    this.cache.delete(key)
    this.cache.set(key,val)
    return val
};
 
LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
        this.cache.delete(key,value)
        this.cache.set(key,value)
        return
    }
    if (this.cache.size >= this.capacity) {
        this.cache.delete(this.cache.keys().next().value)
    }
    this.cache.set(key,value)
};
 

Complexity

• Time: O(1) — assuming we dont rebuild the collection
• Space: O(n) — where m is the size of the collection

Key Takeaway

Two different approaches either using a linked list or a map constructor depending what we are allowed to use in the interview