Least Recently Used Cache - Amazon Top Interview Questions


Problem Statement :


Implement a least recently used cache with the following methods:

LRUCache(int capacity) constructs a new instance of a LRU cache with the given capacity.
get(int key) retrieves the value associated with the key key. If it does not exist, return -1. As a side effect, this key now becomes the most recently used key.
set(int key, int val) updates the key key with value val. If updating this key-value pair exceeds capacity, then evicts the least recently used key-value pair.
Each method should be done in \mathcal{O}(1)O(1) time.

Constraints


n ≤ 100,000 where n is the number of calls to get and set.

Example 1

Input

methods = ["constructor", "set", "get", "set", "set", "set", "get", "get"]
arguments = [[3], [1, 10], [1], [2, 20], [3, 30], [4, 40], [1], [4]]`

Output

[None, None, 10, None, None, None, -1, 40]

Explanation

We create an LRUCache of capacity 3.

Set key of 1 to value 10. Size of cache is now 1
We get 1 which has value of 10
Set key of 2 to value 20. Size of cache is now 2
Set key of 3 to value 30. Size of cache is now 3
Set key of 4 to value 40. Size exceeds capacity, so now we evict the least recently used key which is 1.
We get 1 which has been evicted so we return -1
We get 4 which has value of 40



Solution :



title-img




                        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]
                    


View More Similar Problems

Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

View Solution →

Super Maximum Cost Queries

Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and

View Solution →

Contacts

We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co

View Solution →

No Prefix Set

There is a given list of strings where each string contains only lowercase letters from a - j, inclusive. The set of strings is said to be a GOOD SET if no string is a prefix of another string. In this case, print GOOD SET. Otherwise, print BAD SET on the first line followed by the string being checked. Note If two strings are identical, they are prefixes of each other. Function Descriptio

View Solution →

Cube Summation

You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries. UPDATE x y z W updates the value of block (x,y,z) to W. QUERY x1 y1 z1 x2 y2 z2 calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coor

View Solution →

Direct Connections

Enter-View ( EV ) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the x -axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points. Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) do

View Solution →