# 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 :

                        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.tail = DLLNode(0, 0)
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
"""
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]
`

## 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

## 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

## 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

## 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

## Subsequence Weighting

A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =