Least Recently Used Cache - Amazon Top Interview Questions

                        Solution in C++ :

class LRUCache {
    public:
    LRUCache(int capacity) : cap(capacity) {
    }

    int get(int key) {
        auto it = m.find(key);
        if (it == m.end()) return -1;
        auto lit = it->second;
        int val = lit->second;
        lst.erase(lit);
        lst.push_front({key, val});
        it->second = lst.begin();
        return val;
    }

    void set(int key, int val) {
        auto it = m.find(key);
        if (it == m.end()) {
            lst.push_front({key, val});
            m.insert({key, lst.begin()});
        } else {
            auto lit = it->second;
            lst.erase(lit);
            lst.push_front({key, val});
            it->second = lst.begin();
        }

        if (lst.size() > cap) {
            auto p = lst.back();
            m.erase(p.first);
            lst.pop_back();
        }
    }

    private:
    int cap;
    list<pair<int, int>> lst;
    unordered_map<int, list<pair<int, int>>::iterator> m;
};
                    

                        Solution in Python : 
                            
class DLLNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None


class DLL:
    def __init__(self):
        """
        initialize Doubly Linked List with 2 dummy nodes to
        get first and last nodes in O(1) time because our operations
        require us to either push to the front or pop from the end.
        """
        self.head = DLLNode(0, 0)
        self.tail = DLLNode(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head
        self.size = 0

    def delete(self, node):
        """
        Delete a DLL node, given its pointer. we just update the
        2 pointers that point to this node and we're done
        """
        node.next.prev, node.prev.next = node.prev, node.next
        self.size -= 1

    def push_front(self, node):
        """
        since we already have the pointer to the head of DLL, we just push this
        node to the next of the head
        """
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def get_last(self):
        return self.tail.prev


class LRUCache:
    def __init__(self, capacity):
        self.dll = DLL()
        self.mapping = {}
        self.capacity = capacity

    def get(self, key):
        """
        If the key is not present in mapping, we simply return -1.
        Else we get the pointer to that node in the DLL and move the node
        to the front and return its value
        """
        if key not in self.mapping:
            return -1
        node = self.mapping[key]

        # now move this node to the front of the array
        self.dll.delete(node)
        self.dll.push_front(node)

        return node.val

    def set(self, key, val):
        """
        If key already has a value set, we get the DLL node and delete it.
        We don't remove from the mapping since we will overwrite it anyway.

        then we create a new node and insert to the front of the DLL and update
        the mapping with this new node.

        If the size is more than the capacity, we get the last element and pop it
        """
        if key in self.mapping:
            node = self.mapping[key]
            self.dll.delete(node)

        # add a new entry to the front
        node = DLLNode(key, val)
        self.dll.push_front(node)
        self.mapping[key] = node

        # if the size is more than the capacity, pop last
        if len(self.mapping) > self.capacity:
            last_node = self.dll.get_last()
            self.dll.delete(last_node)
            del self.mapping[last_node.key]