Design a data structure that works like a LRU Cache. Here cap denotes the capacity of the cache and Q denotes the number of queries. Query can be of two types:
	SET x y: sets the value of the key x with value y 
	GET x: gets the key of x if present else returns -1.
The LRUCache class has two methods get() and set() which are defined as follows.
	get(key): returns the value of the key if it already exists in the cache otherwise returns -1.
	set(key, value): if the key is already present, update its value. If not present, add the key-value pair to the cache. If the cache reaches its capacity it should invalidate the least recently used item before inserting the new item.
	In the constructor of the class the capacity of the cache should be initialized.
 
Example 1:
Input:
cap = 2
Q = 2
Queries = SET 1 2 GET 1
Output: 2
Explanation: 
Cache Size = 2
SET 1 2 GET 1
SET 1 2 : 1 -> 2
GET 1 : Print the value corresponding
to Key 1, ie 2.
Example 2:
Input:
cap = 2
Q = 8
Queries = SET 1 2 SET 2 3 SET 1 5
SET 4 5 SET 6 7 GET 4 SET 1 2 GET 3
Output: 5 -1
Explanation: 
Cache Size = 2
SET 1 2 : 1 -> 2
SET 2 3 : 1 -> 2, 2 -> 3 (the most recently 
used one is kept at the rightmost position) 
SET 1 5 : 2 -> 3, 1 -> 5
SET 4 5 : 1 -> 5, 4 -> 5 (Cache size is 2, hence 
we delete the least recently used key-value pair)
SET 6 7 : 4 -> 5, 6 -> 7 
GET 4 : Prints 5 (The cache now looks like
6 -> 7, 4->5)
SET 1 2 : 4 -> 5, 1 -> 2 
(Cache size is 2, hence we delete the least 
recently used key-value pair)
GET 3 : No key value pair having 
key = 3. Hence, -1 is printed.
Your Task:
You don't need to read input or print anything. Complete the constructor and get(), and set() methods of the class LRUcache. 
Expected Time Complexity: O(1) for both get() and set().
Expected Auxiliary Space: O(1) for both get() and set(). 
(Although, you may use extra space for cache storage and implementation purposes).
Constraints:
1 <= cap <= 10^3
1 <= Q <= 10^5
1 <= x, y <= 10^4

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



# design the class in the most optimal way



class LRUCache:

      

    #Constructor for initializing the cache capacity with the given value.  

    def __init__(self,cap):

        #code here

        

        

    #Function to return value corresponding to the key.

    def get(self, key):

        #code here

        

        

    #Function for storing key-value pair.   

    def set(self, key, value):

        #code here





Solutions:
class Node:

	def __init__(self, key=None, value=None):
		self.key = key
		self.value = value
		self.prev = None
		self.next = None

class LRUCache:

	def __init__(self, capacity):
		self.capacity = capacity
		self.cache = {}
		self.head = Node()
		self.tail = Node()
		self.head.next = self.tail
		self.tail.prev = self.head

	def get(self, key):
		if key in self.cache:
			node = self.cache[key]
			self._remove(node)
			self._add(node)
			return node.value
		return -1

	def set(self, key, value):
		if key in self.cache:
			node = self.cache[key]
			self._remove(node)
		elif len(self.cache) == self.capacity:
			node = self.tail.prev
			self._remove(node)
			del self.cache[node.key]
		node = Node(key, value)
		self.cache[key] = node
		self._add(node)

	def _add(self, node):
		next_node = self.head.next
		self.head.next = node
		node.prev = self.head
		node.next = next_node
		next_node.prev = node

	def _remove(self, node):
		prev_node = node.prev
		next_node = node.next
		prev_node.next = next_node
		next_node.prev = prev_node


class Node:

	def __init__(self, key, val):
		(self.key, self.val) = (key, val)
		(self.prev, self.next) = (None, None)

class LRUCache:

	def __init__(self, cap):
		self.capacity = cap
		self.cache = {}
		(self.head, self.tail) = (Node(0, 0), Node(0, 0))
		self.head.next = self.tail
		self.tail.prev = self.head

	def insert(self, node):
		(prev, nxt) = (self.tail.prev, self.tail)
		prev.next = nxt.prev = node
		node.next = nxt
		node.prev = prev

	def remove(self, node):
		(prev, nxt) = (node.prev, node.next)
		prev.next = nxt
		nxt.prev = prev

	def get(self, key):
		if key in self.cache:
			self.remove(self.cache[key])
			self.insert(self.cache[key])
			return self.cache[key].val
		return -1

	def set(self, key, value):
		if key in self.cache:
			self.remove(self.cache[key])
		self.cache[key] = Node(key, value)
		self.insert(self.cache[key])
		if len(self.cache) > self.capacity:
			lru = self.head.next
			self.remove(lru)
			del self.cache[lru.key]


class Node:

	def __init__(self, key, val):
		self.key = key
		self.val = val
		self.prev = None
		self.next = None

class LRUCache:

	def __init__(self, capacity: int):
		self.capacity = capacity
		self.cache = {}
		self.head = Node(0, 0)
		self.tail = Node(0, 0)
		self.head.next = self.tail
		self.tail.prev = self.head

	def get(self, key: int) -> int:
		if key in self.cache:
			node = self.cache[key]
			self._remove(node)
			self._add(node)
			return node.val
		else:
			return -1

	def set(self, key: int, value: int) -> None:
		if key in self.cache:
			self._remove(self.cache[key])
		node = Node(key, value)
		self.cache[key] = node
		self._add(node)
		if len(self.cache) > self.capacity:
			node = self.head.next
			self._remove(node)
			del self.cache[node.key]

	def _remove(self, node):
		prev = node.prev
		next = node.next
		prev.next = next
		next.prev = prev

	def _add(self, node):
		prev = self.tail.prev
		prev.next = node
		node.prev = prev
		node.next = self.tail
		self.tail.prev = node


class Node:

	def __init__(self, key, value):
		self.key = key
		self.value = value
		self.next = None
		self.prev = None

class DoublyLinkedList:

	def __init__(self):
		self.head = None
		self.tail = None

	def remove_lru(self):
		if self.head is None:
			print('The linked list is empty. Cannot remove!')
		prev = self.tail.prev
		temp = self.tail
		if prev is None:
			self.head = None
			self.tail = None
		else:
			self.tail.prev = None
			prev.next = None
			self.tail = prev
		key = temp.key
		del temp
		return key

	def add(self, key, value):
		node = Node(key, value)
		if self.head is None:
			self.head = node
			self.tail = node
		else:
			node.next = self.head
			self.head.prev = node
			self.head = node
		return node

	def update(self, key, new_value, node):
		node.value = new_value
		if self.head == node:
			return
		elif self.tail == node:
			prev = self.tail.prev
			prev.next = None
			node.prev = None
			self.tail = prev
		elif self.tail != node and self.head != node:
			prev = node.prev
			prev.next = node.next
			node.next.prev = prev
			node.prev = None
			node.next = None
		node.next = self.head
		self.head.prev = node
		self.head = node

class LRUCache:

	def __init__(self, cap):
		self.capacity = cap
		self.size = 0
		self.key_to_node_map = dict()
		self.dll = DoublyLinkedList()

	def get(self, key):
		if key not in self.key_to_node_map:
			return -1
		node = self.key_to_node_map[key]
		self.dll.update(key, node.value, node)
		return node.value

	def set(self, key, value):
		if key in self.key_to_node_map:
			node = self.key_to_node_map[key]
			self.dll.update(key, value, node)
		else:
			if self.size == self.capacity:
				lru_key = self.dll.remove_lru()
				self.size -= 1
				del self.key_to_node_map[lru_key]
			node = self.dll.add(key, value)
			self.key_to_node_map[key] = node
			self.size += 1


from collections import OrderedDict

class LRUCache:

	def __init__(self, cap):
		self.capacity = cap
		self.cache = OrderedDict()

	def get(self, key):
		if key in self.cache:
			value = self.cache.pop(key)
			self.cache[key] = value
			return value
		return -1

	def set(self, key, value):
		if key in self.cache:
			self.cache.pop(key)
		elif len(self.cache) == self.capacity:
			self.cache.popitem(last=False)
		self.cache[key] = value


class Node:

	def __init__(self, key, val):
		self.key = key
		self.val = val
		self.prev = None
		self.next = None

class LRUCache:

	def __init__(self, cap):
		self.cap = cap
		self.cache = {}
		self.head = Node(-1, -1)
		self.tail = Node(-1, -1)
		self.head.next = self.tail
		self.tail.prev = self.head

	def insert(self, node):
		temp = self.head.next
		node.next = temp
		node.prev = self.head
		self.head.next = node
		temp.prev = node

	def remove(self, node):
		delprev = node.prev
		delnext = node.next
		delprev.next = delnext
		delnext.prev = delprev

	def get(self, key):
		if key in self.cache:
			self.remove(self.cache[key])
			self.insert(self.cache[key])
			return self.cache[key].val
		return -1

	def set(self, key, value):
		if key in self.cache:
			self.remove(self.cache[key])
		self.cache[key] = Node(key, value)
		self.insert(self.cache[key])
		if len(self.cache) > self.cap:
			lru = self.tail.prev
			self.remove(lru)
			del self.cache[lru.key]


class LRUCache:

	def __init__(self, cap):
		self.cap = cap
		self.cache = {}
		self.head = {}
		self.tail = {}
		self.head['next'] = self.tail
		self.tail['prev'] = self.head
		self.size = 0

	def _add(self, node):
		node['prev'] = self.head
		node['next'] = self.head['next']
		self.head['next']['prev'] = node
		self.head['next'] = node

	def _remove(self, node):
		node['prev']['next'] = node['next']
		node['next']['prev'] = node['prev']

	def get(self, key):
		if key not in self.cache:
			return -1
		node = self.cache[key]
		self._remove(node)
		self._add(node)
		return node['val']

	def set(self, key, value):
		if key in self.cache:
			node = self.cache[key]
			node['val'] = value
			self._remove(node)
			self._add(node)
		else:
			if self.size == self.cap:
				tail_prev = self.tail['prev']
				self._remove(tail_prev)
				del self.cache[tail_prev['key']]
				self.size -= 1
			node = {'key': key, 'val': value}
			self.cache[key] = node
			self._add(node)
			self.size += 1


import collections

class LRUCache:

	def __init__(self, cap):
		self.cap = cap
		self.key_value = collections.OrderedDict()

	def get(self, key):
		a = self.key_value.get(key, None)
		if a:
			self.key_value.move_to_end(key)
			return a
		else:
			return -1

	def set(self, key, value):
		a = self.key_value.get(key, None)
		if a:
			self.key_value.move_to_end(key)
		self.key_value[key] = value
		if len(self.key_value) > self.cap:
			self.key_value.popitem(last=False)


from collections import OrderedDict

class LRUCache:

	def __init__(self, cap):
		self.cap = cap
		self.d = OrderedDict()

	def get(self, key):
		if self.d.get(key, 0):
			val = self.d.get(key)
			self.d.move_to_end(key)
			return val
		else:
			return -1

	def set(self, key, value):
		if self.d.get(key, 0):
			self.d[key] = value
			self.d.move_to_end(key)
		else:
			if len(self.d) == self.cap:
				self.d.popitem(last=False)
			self.d[key] = value


from collections import OrderedDict

class LRUCache:

	def __init__(self, cap):
		self.capacity = cap
		self.values = OrderedDict()

	def get(self, key):
		if key not in self.values:
			return -1
		else:
			self.values[key] = self.values.pop(key)
			return self.values[key]

	def set(self, key, value):
		if key not in self.values:
			if len(self.values) == self.capacity:
				self.values.popitem(last=False)
		else:
			self.values.pop(key)
		self.values[key] = value


class Node:

	def __init__(self, key, value):
		self.key = key
		self.value = value
		self.prev = None
		self.next = None

class LRUCache:

	def __init__(self, cap):
		self.cap = cap
		self.cache = {}
		self.head = Node(0, 0)
		self.tail = Node(0, 0)
		self.head.next = self.tail
		self.tail.prev = self.head

	def get(self, key):
		if key in self.cache:
			node = self.cache[key]
			self._remove(node)
			self._add(node)
			return node.value
		return -1

	def set(self, key, value):
		if key in self.cache:
			node = self.cache[key]
			self._remove(node)
		new_node = Node(key, value)
		self.cache[key] = new_node
		self._add(new_node)
		if len(self.cache) > self.cap:
			node_to_remove = self.head.next
			self._remove(node_to_remove)
			del self.cache[node_to_remove.key]

	def _add(self, node):
		prev_node = self.tail.prev
		prev_node.next = node
		node.prev = prev_node
		node.next = self.tail
		self.tail.prev = node

	def _remove(self, node):
		prev_node = node.prev
		next_node = node.next
		prev_node.next = next_node
		next_node.prev = prev_node


class LRUCache:

	def __init__(self, cap):
		self.capacity = cap
		self.cache = {}
		self.head = {}
		self.tail = {}
		self.head['next'] = self.tail
		self.tail['prev'] = self.head

	def get(self, key):
		if key in self.cache:
			node = self.cache[key]
			prev_node = node['prev']
			next_node = node['next']
			prev_node['next'] = next_node
			next_node['prev'] = prev_node
			last_node = self.tail['prev']
			last_node['next'] = node
			node['prev'] = last_node
			node['next'] = self.tail
			self.tail['prev'] = node
			return node['value']
		return -1

	def set(self, key, value):
		if key in self.cache:
			node = self.cache[key]
			prev_node = node['prev']
			next_node = node['next']
			prev_node['next'] = next_node
			next_node['prev'] = prev_node
		elif len(self.cache) >= self.capacity:
			oldest_node = self.head['next']
			del self.cache[oldest_node['key']]
			self.head['next'] = oldest_node['next']
			oldest_node['next']['prev'] = self.head
		new_node = {'key': key, 'value': value}
		self.cache[key] = new_node
		last_node = self.tail['prev']
		last_node['next'] = new_node
		new_node['prev'] = last_node
		new_node['next'] = self.tail
		self.tail['prev'] = new_node


class Node:

	def __init__(self, key, value):
		self.key = key
		self.value = value
		self.next = self.pre = None

class LRUCache:
	hsmap = dict()
	capacity = count = 0
	head = tail = None

	def __init__(self, cap):
		self.hsmap = dict()
		self.capacity = cap
		self.head = Node(0, 0)
		self.tail = Node(0, 0)
		self.head.next = self.tail
		self.head.pre = None
		self.tail.next = None
		self.tail.pre = self.head
		count = 0

	def addToHead(self, node):
		node.next = self.head.next
		node.next.pre = node
		node.pre = self.head
		self.head.next = node

	def deleteNode(self, node):
		node.pre.next = node.next
		node.next.pre = node.pre

	def get(self, key):
		if key in self.hsmap:
			node = self.hsmap[key]
			result = node.value
			self.deleteNode(node)
			self.addToHead(node)
			return result
		else:
			return -1

	def set(self, key, value):
		if key in self.hsmap:
			node = self.hsmap[key]
			node.value = value
			self.deleteNode(node)
			self.addToHead(node)
		else:
			node = Node(key, value)
			self.hsmap[key] = node
			if self.count < self.capacity:
				self.count += 1
				self.addToHead(node)
			else:
				self.hsmap.pop(self.tail.pre.key)
				self.deleteNode(self.tail.pre)
				self.addToHead(node)


from collections import OrderedDict

class LRUCache:

	def __init__(self, cap):
		self.c = OrderedDict()
		self.cap = cap

	def get(self, key):
		if key not in self.c:
			return -1
		else:
			self.c.move_to_end(key)
			return self.c[key]

	def set(self, key, value):
		self.c[key] = value
		self.c.move_to_end(key)
		if len(self.c) > self.cap:
			self.c.popitem(last=False)


class Node:

	def __init__(self, key, value):
		self.key = key
		self.val = value
		self.next = None
		self.prev = None

class DoublyList:

	def __init__(self):
		self.head = None
		self.tail = None
		self.size = 0

	def insert(self, key, val):
		node = Node(key, val)
		if self.tail:
			node.prev = self.tail
			self.tail.next = node
			self.tail = self.tail.next
		else:
			self.tail = self.head = node
		self.size += 1
		return node

	def remove(self, mp):
		if self.head:
			del mp[self.head.key]
			if self.head == self.tail:
				self.tail = None
				self.head = None
			else:
				self.head = self.head.next
			self.size -= 1

	def move_to_front(self, node):
		if not self.head or not node or node == self.tail:
			return
		if self.size == 1:
			return
		if node == self.head:
			self.head = self.head.next
			self.head.prev = None
			self.tail.next = node
			node.prev = self.tail
			self.tail = self.tail.next
			self.tail.next = None
		else:
			node.prev.next = node.next
			node.next.prev = node.prev
			node.next = None
			self.tail.next = node
			node.prev = self.tail
			self.tail = self.tail.next

class LRUCache:

	def __init__(self, size):
		self.size = size
		self.list = DoublyList()
		self.mp = {}

	def get(self, key):
		if not self.mp.get(key):
			return -1
		node = self.mp[key]
		self.list.move_to_front(node)
		return node.val

	def set(self, key, val):
		if self.mp.get(key):
			self.mp[key].val = val
			self.list.move_to_front(self.mp[key])
			return
		self.mp[key] = self.list.insert(key, val)
		if self.list.size > self.size:
			self.list.remove(self.mp)


class Node:

	def __init__(self, val):
		self.data = val
		self.prev = None
		self.next = None

class LRUCache:

	def __init__(self, cap):
		self.cap = cap
		self.size = 0
		self.head = Node(-1)
		self.tail = Node(-1)
		self.key_node = {}
		self.node_key = {}
		self.head.next = self.tail
		self.tail.prev = self.head

	def get(self, key):
		if key in self.key_node:
			node = self.key_node[key]
			(prev, next) = (node.prev, node.next)
			prev.next = next
			next.prev = prev
			end = self.tail.prev
			end.next = node
			node.prev = end
			self.tail.prev = node
			node.next = self.tail
			return node.data
		return -1

	def set(self, key, value):
		if key in self.key_node:
			node = self.key_node[key]
			(prev, next) = (node.prev, node.next)
			prev.next = next
			next.prev = prev
			end = self.tail.prev
			end.next = node
			node.prev = end
			self.tail.prev = node
			node.next = self.tail
			node.data = value
		else:
			newNode = Node(value)
			self.key_node[key] = newNode
			self.node_key[newNode] = key
			end = self.tail.prev
			end.next = newNode
			newNode.prev = end
			self.tail.prev = newNode
			newNode.next = self.tail
			if self.size == self.cap:
				lru = self.head.next
				(prev, next) = (lru.prev, lru.next)
				prev.next = next
				next.prev = prev
				self.key_node.pop(self.node_key[lru])
				self.node_key.pop(lru)
				del lru
			else:
				self.size += 1


from collections import OrderedDict

class LRUCache:

	def __init__(self, cap):
		self.ordict = OrderedDict()
		self.cap = cap

	def get(self, key):
		if key in self.ordict:
			self.ordict.move_to_end(key)
			return self.ordict[key]
		else:
			return -1

	def set(self, key, value):
		if key in self.ordict:
			self.ordict.move_to_end(key)
			self.ordict[key] = value
		else:
			if len(self.ordict) == self.cap:
				self.ordict.popitem(0)
			self.ordict[key] = value


class Node:

	def __init__(self, key, value):
		self.key = key
		self.value = value
		self.next = None
		self.prev = None

class LRUCache:

	def __init__(self, capacity):
		self.capacity = capacity
		self._key_to_node = {}
		self._head = Node(0, 0)
		self._tail = Node(0, 0)
		self._head.next = self._tail
		self._tail.prev = self._head

	def _delete_node(self, node):
		node.next.prev = node.prev
		node.prev.next = node.next

	def _add_to_head(self, node):
		node.next = self._head.next
		node.next.prev = node
		node.prev = self._head
		self._head.next = node

	def move_node_to_head(self, node):
		self._delete_node(node)
		self._add_to_head(node)

	def get(self, key):
		if key not in self._key_to_node:
			return -1
		node = self._key_to_node[key]
		self.move_node_to_head(node)
		return node.value

	def set(self, key, value):
		if key in self._key_to_node:
			node = self._key_to_node[key]
			node.value = value
			self.move_node_to_head(node)
		else:
			new_node = Node(key, value)
			if len(self._key_to_node) + 1 > self.capacity:
				least_recently_used = self._key_to_node.pop(self._tail.prev.key)
				self._delete_node(least_recently_used)
			self._key_to_node[key] = new_node
			self._add_to_head(new_node)


class Node:

	def __init__(self, key, value):
		self.key = key
		self.value = value
		self.prev = None
		self.next = None

class LRUCache:

	def __init__(self, cap):
		self.size = cap
		self.head = Node(-1, -1)
		self.tail = Node(-1, -1)
		self.head.next = self.tail
		self.tail.prev = self.head
		self.d = {}

	def display(self):
		print()
		thead = self.head
		while thead:
			print(thead.key, ':', thead.value, end='->')
			thead = thead.next
		print()

	def get(self, key):
		if key not in self.d:
			return -1
		elif key in self.d:
			ans = self.d[key].value
			temp = self.d[key]
			p = temp.prev
			n = temp.next
			p.next = n
			n.prev = p
			n_n = Node(key, ans)
			temp = self.head.next
			n_n.next = temp
			temp.prev = n_n
			self.head.next = n_n
			n_n.prev = self.head
			self.d[key] = n_n
			return self.d[key].value

	def set(self, key, value):
		if key in self.d:
			node = self.d[key]
			p = node.prev
			n = node.next
			p.next = n
			n.prev = p
			del self.d[key]
			n_n = Node(key, value)
			temp = self.head.next
			n_n.next = temp
			temp.prev = n_n
			self.head.next = n_n
			n_n.prev = self.head
			self.d[key] = n_n
		elif len(self.d) < self.size:
			n_n = Node(key, value)
			temp = self.head.next
			n_n.next = temp
			temp.prev = n_n
			self.head.next = n_n
			n_n.prev = self.head
			self.d[key] = n_n
		elif len(self.d) >= self.size:
			temp = self.tail.prev
			p = temp.prev
			n = temp.next
			p.next = n
			n.prev = p
			del self.d[temp.key]
			n_n = Node(key, value)
			temp = self.head.next
			n_n.next = temp
			temp.prev = n_n
			self.head.next = n_n
			n_n.prev = self.head
			self.d[key] = n_n


class node:

	def __init__(self, key, value):
		self.key = key
		self.value = value
		self.next = None
		self.prev = None

class LRUCache:

	def __init__(self, cap):
		self.first = node(0, 0)
		self.end = node(0, 0)
		self.first.next = self.end
		self.end.prev = self.first
		self.capacity = cap
		self.curr_capacity = 0
		self.hashmap = {}

	def get(self, key):
		if key in self.hashmap:
			x = self.hashmap[key]
			x.prev.next = x.next
			x.next.prev = x.prev
			temp = self.first.next
			self.first.next = x
			x.prev = self.first
			x.next = temp
			temp.prev = x
			return x.value
		else:
			return -1

	def set(self, key, val):
		if key in self.hashmap:
			self.hashmap[key].value = val
			x = self.hashmap[key]
			x.prev.next = x.next
			x.next.prev = x.prev
			temp = self.first.next
			self.first.next = x
			x.prev = self.first
			x.next = temp
			temp.prev = x
			self.hashmap[key] = x
			return
		if self.curr_capacity < self.capacity:
			x = node(key, val)
			self.curr_capacity += 1
			temp = self.first.next
			self.first.next = x
			x.prev = self.first
			x.next = temp
			temp.prev = x
			self.hashmap[key] = x
		elif self.curr_capacity == self.capacity:
			rem = self.end.prev
			rem.prev.next = self.end
			self.end.prev = rem.prev
			try:
				self.hashmap.pop(rem.key)
			except:
				print('issue')
			x = node(key, val)
			temp = self.first.next
			self.first.next = x
			x.prev = self.first
			x.next = temp
			temp.prev = x
			self.hashmap[key] = x

	def printdll(self):
		x = self.first
		while x != self.end:
			print(x.key, x.value)
			x = x.next


class DLLNode:

	def __init__(self, key, val):
		self.val = val
		self.key = key
		self.prev = None
		self.next = None

class LRUCache:

	def __init__(self, cap):
		self.cap = cap
		self.map = {}
		self.head = DLLNode(0, 0)
		self.tail = DLLNode(0, 0)
		self.head.next = self.tail
		self.tail.prev = self.head
		self.count = 0

	def deleteNode(self, node):
		node.prev.next = node.next
		node.next.prev = node.prev

	def addToHead(self, node):
		node.next = self.head.next
		node.next.prev = node
		node.prev = self.head
		self.head.next = node

	def get(self, key):
		if key in self.map:
			node = self.map[key]
			result = node.val
			self.deleteNode(node)
			self.addToHead(node)
			return result
		return -1

	def set(self, key, value):
		if key in self.map:
			node = self.map[key]
			node.val = value
			self.deleteNode(node)
			self.addToHead(node)
		else:
			node = DLLNode(key, value)
			self.map[key] = node
			if self.count < self.cap:
				self.count += 1
				self.addToHead(node)
			else:
				del self.map[self.tail.prev.key]
				self.deleteNode(self.tail.prev)
				self.addToHead(node)


class Node:

	def __init__(self, key, value):
		self.key = key
		self.value = value
		self.next = None
		self.prev = None

class LRUCache:

	def __init__(self, cap):
		self.cache = {}
		self.cap = cap
		self.head = Node(0, 0)
		self.tail = Node(0, 0)
		self.head.next = self.tail
		self.tail.prev = self.head

	def insert(self, node):
		prv = self.tail.prev
		nxt = self.tail
		node.next = nxt
		node.prev = prv
		prv.next = node
		nxt.prev = node

	def remove(self, node):
		t1 = node.next
		t2 = node.prev
		t2.next = t1
		t1.prev = t2
		t1 = None
		t2 = None

	def set(self, key, value):
		if key in self.cache:
			self.remove(self.cache[key])
		self.cache[key] = Node(key, value)
		self.insert(self.cache[key])
		if len(self.cache) > self.cap:
			LRU = self.head.next
			self.remove(LRU)
			del self.cache[LRU.key]

	def get(self, key):
		if key in self.cache:
			self.remove(self.cache[key])
			self.insert(self.cache[key])
			return self.cache[key].value
		return -1


class Node:

	def __init__(self, key, val):
		(self.key, self.val) = (key, val)
		(self.prev, self.next) = (None, None)

class LRUCache:

	def __init__(self, cap):
		self.capaciti = cap
		self.Cache = {}
		(self.head, self.tail) = (Node(0, 0), Node(0, 0))
		self.head.next = self.tail
		self.tail.prev = self.head

	def insert(self, node):
		(prev, nxt) = (self.tail.prev, self.tail)
		prev.next = nxt.prev = node
		node.next = nxt
		node.prev = prev

	def REMOVE(self, node):
		(prev, nxt) = (node.prev, node.next)
		prev.next = nxt
		nxt.prev = prev

	def get(self, key):
		if key in self.Cache:
			self.REMOVE(self.Cache[key])
			self.insert(self.Cache[key])
			return self.Cache[key].val
		return -1

	def set(self, key, value):
		if key in self.Cache:
			self.REMOVE(self.Cache[key])
		self.Cache[key] = Node(key, value)
		self.insert(self.Cache[key])
		if len(self.Cache) > self.capaciti:
			LRU = self.head.next
			self.REMOVE(LRU)
			del self.Cache[LRU.key]


class ListNode:

	def __init__(self, key=0, value=0, next=None, prev=None):
		self.key = key
		self.value = value
		self.next = next
		self.prev = prev

class LRUCache:

	def __init__(self, cap):
		self.cap = cap
		self.lru = {}
		self.head = ListNode()
		self.tail = ListNode()
		self.head.next = self.tail
		self.tail.prev = self.head

	def get(self, key):
		if key in self.lru:
			n = self.lru[key]
			self._remove(n)
			self._add(n)
			return n.value
		return -1

	def set(self, key, value):
		if key in self.lru:
			self._remove(self.lru[key])
		n = ListNode(key, value)
		self._add(n)
		self.lru[key] = n
		if len(self.lru) > self.cap:
			n = self.head.next
			self._remove(n)
			del self.lru[n.key]

	def _remove(self, node):
		prev_node = node.prev
		next_node = node.next
		prev_node.next = next_node
		next_node.prev = prev_node

	def _add(self, node):
		p = self.tail.prev
		p.next = node
		node.prev = p
		node.next = self.tail
		self.tail.prev = node


class Node:

	def __init__(self, k, v):
		self.key = k
		self.val = v
		self.prev = None
		self.next = None

class LRUCache:

	def __init__(self, cap):
		self.capacity = cap
		self.hmap = {}
		self.head = Node(0, 0)
		self.tail = Node(0, 0)
		self.head.next = self.tail
		self.tail.prev = self.head

	def get(self, key):
		if key in self.hmap:
			node = self.hmap[key]
			self._remove(node)
			self._add(node)
			return node.val
		return -1

	def set(self, key, value):
		if key in self.hmap:
			self._remove(self.hmap[key])
		elif len(self.hmap) == self.capacity:
			lru_node = self.head.next
			self._remove(lru_node)
			del self.hmap[lru_node.key]
		new_node = Node(key, value)
		self._add(new_node)
		self.hmap[key] = new_node

	def _remove(self, node):
		prev_node = node.prev
		next_node = node.next
		prev_node.next = next_node
		next_node.prev = prev_node

	def _add(self, node):
		latest_node = self.tail.prev
		latest_node.next = node
		self.tail.prev = node
		node.prev = latest_node
		node.next = self.tail


class Node:

	def __init__(self, k, v):
		self.key = k
		self.val = v
		self.prev = None
		self.next = None

class LRUCache:

	def __init__(self, cap):
		self.capacity = cap
		self.dic = dict()
		self.head = Node(0, 0)
		self.tail = Node(0, 0)
		self.head.next = self.tail
		self.tail.prev = self.head

	def get(self, key):
		if key in self.dic:
			n = self.dic[key]
			self._remove(n)
			self._add(n)
			return n.val
		return -1

	def set(self, key, value):
		if key in self.dic:
			self._remove(self.dic[key])
		n = Node(key, value)
		self._add(n)
		self.dic[key] = n
		if len(self.dic) > self.capacity:
			n = self.head.next
			self._remove(n)
			del self.dic[n.key]

	def _remove(self, node):
		p = node.prev
		n = node.next
		p.next = n
		n.prev = p

	def _add(self, node):
		p = self.tail.prev
		p.next = node
		self.tail.prev = node
		node.prev = p
		node.next = self.tail