""" I learned this answer from @tusizi; rewrote it. Let's analyze the problem If we need get() to be O(1), we must definitely use a hashmap(dictionary) to store the key value. put() is not a problem, since we are only setting value. The problem is when we excceed the capacity. How do we find the least-used key and remove it from the hashmap? We need something for us to sort from most-frequent-used to least-used. So what else common data structure do we know? Array? no, we will need to iterate to the whole array to find what we need. and it is not easy to add or remove. Tree? not likely. Min-heap? even though we can get the least-used, but it need O(LogN) to set the most-frequent-used. Link list? Bingo! We also need it to be a double link list, so we can remove the tail. We also need the node to store the key when we remove the tail, we can also remove it in the hashmap We also need the node to store the val when we get(). It would be like: head<->node1<->node2<->node3 ... nodeN<->tail (most-frequent-used to least-used) So the main idea now is to use hashmap to store the key:Node pair [0] If we put or get any key-value pair, we move its node to the front of the line (I call this promote()) [1] The front of the line means we put it just after head. If we excced the capacity, we remove the node at the end of the line [2] The end of the line means the node just before tail. The head and tail is just a dummy, [3] for us to keep track of the first and the last of the linklist and don't have worry about the edge case. """ class Node(object): def __init__(self, key, val): self.key = key self.val = val self.next = None self.prev = None class LRUCache(object): def __init__(self, capacity): self.capacity = capacity self.dic = {} #[0] self.head = Node(0, 0) #[3] self.tail = Node(0, 0) #[3] self.head.next = self.tail self.tail.prev = self.head def remove(self, node): node.prev.next = node.next node.next.prev = node.prev def promote(self, node): #[1] #set the node next to head temp = self.head.next node.next = temp temp.prev = node self.head.next = node node.prev = self.head def get(self, key): if key in self.dic: node = self.dic[key] self.remove(node) self.promote(node) return node.val return -1 def put(self, key, value): if key in self.dic: self.remove(self.dic[key]) node = Node(key, value) self.promote(node) self.dic[key] = node if len(self.dic)>self.capacity: #[2] del self.dic[self.tail.prev.key] self.remove(self.tail.prev) #using OrderedDict() class LRUCache(object): def __init__(self, capacity): self.dic = collections.OrderedDict() self.remain = capacity def get(self, key): if key not in self.dic: return -1 v = self.dic.pop(key) self.dic[key] = v # set key as the newest one return v def set(self, key, value): if key in self.dic: self.dic.pop(key) else: if self.remain > 0: self.remain -= 1 else: # self.dic is full self.dic.popitem(last=False) self.dic[key] = value