Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the given LFUCache Class with the following description.
LFUCache(int capacity): This Initializes the object with the capacity of the data structure.
int get(int key): Returns the value of the given key if it exists or else returns -1.
void put(int key, int value): If the key is already present, then update its value and if the key is not present, then it should be inserted. If the data  structure has reached its maximum capacity, then the least frequently used (LFU) key should be invalidated and removed. If during removal, more than one key has same frequency, then the Least Recently Used (LRU) key amongst them should be removed.
Example:
Input: 
Capacity: 3
put(5,7)put(4,6)put(3,5)put(2,4)put(1,3)
get(1)get(2)get(3)get(4)get(5)
Output: 
3
4
5
-1
-1
Explanation: 
When put(2,4) is executed, (5,7) gets invalidated. Similarly when put(1,3) is executed, (4,6) gets invalidated. Therefore only the values for key 1,2,3 are present in the cache after all the put operations.
Your Task:
Implement the given functions, void put(int key, int value) and int get(int key). 
The functions get and put must each run in O(1) average time complexity.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
0 <= capacity <= 10^{4}
0 <= key <= 10^{5}
0 <= value <= 10^{6}
At most 2 *10^{5} calls will be made to get and put.

Source: geeksforgeeks | Difficulty: MEDIUM_HARD

Starter code: #User function Template for python3



class LFUCache:



    def __init__(self, capacity: int):

        



    def get(self, key: int) -> int:

        



    def put(self, key: int, value: int) -> None:

        





# Your LFUCache object will be instantiated and called as such:

# obj = LFUCache(capacity)

# param_1 = obj.get(key)

# obj.put(key,value)

Solutions:
import collections

class LFUCache:

	def __init__(self, capacity: int):
		self.capacity = capacity
		self.minfreq = None
		self.keyfreq = {}
		self.freqkeys = collections.defaultdict(collections.OrderedDict)

	def get(self, key: int) -> int:
		if key not in self.keyfreq:
			return -1
		freq = self.keyfreq[key]
		val = self.freqkeys[freq][key]
		del self.freqkeys[freq][key]
		if not self.freqkeys[freq]:
			if freq == self.minfreq:
				self.minfreq += 1
			del self.freqkeys[freq]
		self.keyfreq[key] = freq + 1
		self.freqkeys[freq + 1][key] = val
		return val

	def put(self, key: int, value: int) -> None:
		if self.capacity <= 0:
			return
		if key in self.keyfreq:
			freq = self.keyfreq[key]
			self.freqkeys[freq][key] = value
			self.get(key)
			return
		if self.capacity == len(self.keyfreq):
			(delkey, delval) = self.freqkeys[self.minfreq].popitem(last=False)
			del self.keyfreq[delkey]
		self.keyfreq[key] = 1
		self.freqkeys[1][key] = value
		self.minfreq = 1


import sys

class node:

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

class LRUCache:

	def __init__(self):
		self.first = node(-1, -1)
		self.end = node(-1, -1)
		self.first.next = self.end
		self.end.prev = self.first
		self.curr_cap = 0

	def push(self, key, value, freq, x=None):
		if x == None:
			x = node(key, value)
		x.value = value
		x.freq = freq
		y = self.first.next
		self.first.next = x
		x.prev = self.first
		x.next = y
		y.prev = x
		return x

	def isolate(self, x):
		x.prev.next = x.next
		x.next.prev = x.prev

	def pop(self):
		rem = self.end.prev
		rem.prev.next = self.end
		self.end.prev = rem.prev
		return rem

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

	def isEmpty(self):
		if self.first.next.value == -1:
			return 1
		return 0

class LFUCache:

	def __init__(self, capacity: int):
		self.hashmap = {}
		self.freq = {}
		self.capacity = capacity
		self.curr_capacity = 0

	def get(self, key: int) -> int:
		if key in self.hashmap:
			node = self.hashmap[key]
			try:
				self.freq[node.freq].isolate(node)
				if node.freq + 1 in self.freq:
					self.freq[node.freq + 1].push(key, node.value, node.freq + 1, node)
				else:
					obj = LRUCache()
					obj.push(key, node.value, node.freq + 1, node)
					self.freq[node.freq] = obj
			except:
				print('here error')
			return node.value
		else:
			return -1

	def put(self, key: int, value: int) -> None:
		if self.capacity == 0:
			return
		if key in self.hashmap:
			node = self.hashmap[key]
			self.freq[node.freq].isolate(node)
			if node.freq + 1 in self.freq:
				self.freq[node.freq + 1].push(key, value, node.freq + 1, node)
			else:
				obj = LRUCache()
				obj.push(key, value, node.freq + 1, node)
				self.freq[node.freq] = obj
		else:
			if self.curr_capacity == self.capacity:
				min_freq = sys.maxsize
				for key2 in self.freq.keys():
					if self.freq[key2].isEmpty():
						continue
					else:
						min_freq = min(key2, min_freq)
				del_node = self.freq[min_freq].pop()
				del self.hashmap[del_node.key]
				self.curr_capacity -= 1
			if 1 in self.freq:
				new_node = self.freq[1].push(key, value, 1)
				self.hashmap[key] = new_node
			else:
				obj = LRUCache()
				new_node = obj.push(key, value, 1)
				self.hashmap[key] = new_node
				self.freq[1] = obj
			self.curr_capacity += 1


class LFUCache:

	def __init__(self, capacity: int):
		self.capacity = capacity
		self.cache = {}
		self.freq = {}
		self.min_freq = 0

	def get(self, key: int) -> int:
		if key not in self.cache:
			return -1
		(value, freq, timestamp) = self.cache[key]
		self.freq[freq].remove(key)
		if not self.freq[freq]:
			del self.freq[freq]
			if self.min_freq == freq:
				self.min_freq += 1
		freq += 1
		self.freq.setdefault(freq, []).append(key)
		self.cache[key] = (value, freq, timestamp + 1)
		return value

	def put(self, key: int, value: int) -> None:
		if self.capacity == 0:
			return
		if key in self.cache:
			(_, freq, timestamp) = self.cache[key]
			self.freq[freq].remove(key)
			if not self.freq[freq]:
				del self.freq[freq]
				if self.min_freq == freq:
					self.min_freq += 1
			freq += 1
			self.freq.setdefault(freq, []).append(key)
			self.cache[key] = (value, freq, timestamp + 1)
		else:
			if len(self.cache) == self.capacity:
				min_freq_keys = self.freq[self.min_freq]
				lru_key = min(min_freq_keys, key=lambda k: self.cache[k][2])
				self.freq[self.min_freq].remove(lru_key)
				if not self.freq[self.min_freq]:
					del self.freq[self.min_freq]
				del self.cache[lru_key]
			self.freq.setdefault(1, []).append(key)
			self.cache[key] = (value, 1, 0)
			self.min_freq = 1


import collections

class Node:

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

class DLinkedList:

	def __init__(self):
		self._sentinel = Node(None, None)
		self._sentinel.next = self._sentinel.prev = self._sentinel
		self._size = 0

	def __len__(self):
		return self._size

	def append(self, node):
		node.next = self._sentinel.next
		node.prev = self._sentinel
		node.next.prev = node
		self._sentinel.next = node
		self._size += 1

	def pop(self, node=None):
		if self._size == 0:
			return
		if not node:
			node = self._sentinel.prev
		node.prev.next = node.next
		node.next.prev = node.prev
		self._size -= 1
		return node

class LFUCache:

	def __init__(self, capacity):
		self._size = 0
		self._capacity = capacity
		self._node = dict()
		self._freq = collections.defaultdict(DLinkedList)
		self._minfreq = 0

	def _update(self, node):
		freq = node.freq
		self._freq[freq].pop(node)
		if self._minfreq == freq and (not self._freq[freq]):
			self._minfreq += 1
		node.freq += 1
		freq = node.freq
		self._freq[freq].append(node)

	def get(self, key):
		if key not in self._node:
			return -1
		node = self._node[key]
		self._update(node)
		return node.val

	def put(self, key, value):
		if self._capacity == 0:
			return
		if key in self._node:
			node = self._node[key]
			self._update(node)
			node.val = value
		else:
			if self._size == self._capacity:
				node = self._freq[self._minfreq].pop()
				del self._node[node.key]
				self._size -= 1
			node = Node(key, value)
			self._node[key] = node
			self._freq[1].append(node)
			self._minfreq = 1
			self._size += 1


class Node:

	def __init__(self, key, val, freq_node):
		self.key = key
		self.val = val
		self.left = None
		self.right = None
		self.freq_node = freq_node

	def __str__(self):
		res = ''
		if self.right:
			res += str(self.right) + ' => '
		res += str(self.key)
		return res

class FreqNode:

	def __init__(self):
		self.upper = None
		self.lower = None
		self.first_val_node = None
		self.last_val_node = None

	def add_val(self, val_node):
		if self.first_val_node is None:
			self.first_val_node = val_node
			self.last_val_node = val_node
		else:
			self.first_val_node.left = val_node
			val_node.right = self.first_val_node
			self.first_val_node = val_node

	def pop_last(self):
		if self.empty():
			return None
		result = (self.last_val_node.key, self.last_val_node.val)
		if self.last_val_node.left is not None:
			self.last_val_node = self.last_val_node.left
			self.last_val_node.right = None
			return result
		else:
			self.last_val_node = None
			self.first_val_node = None
		return result

	def pop_first(self):
		if self.empty():
			return None
		result = (self.first_val_node.key, self.first_val_node.val)
		if self.first_val_node.right is not None:
			self.first_val_node = self.first_val_node.right
			self.first_val_node.left = None
			return result
		else:
			self.last_val_node = None
			self.first_val_node = None
		return result

	def del_node(self, node):
		if self.first_val_node == node:
			self.pop_first()
		elif self.last_val_node == node:
			self.pop_last()
		else:
			node.left.right = node.right
			node.right.left = node.left

	def empty(self):
		if self.first_val_node is None:
			return True
		return False

	def __str__(self):
		return str(self.first_val_node)

class LFUCache:

	def __init__(self, capacity: int):
		self.capacity = capacity
		self.map = {}
		self.lower_freq = FreqNode()
		self.higher_freq = self.lower_freq

	def get(self, key: int) -> int:
		if key not in self.map:
			return -1
		node = self.map[key]
		self._update_node(node)
		return node.val

	def put(self, key: int, value: int) -> None:
		if self.capacity == 0:
			return
		if key not in self.map:
			if len(self.map) == self.capacity:
				freq_node = self.lower_freq
				while freq_node.empty():
					freq_node = freq_node.upper
				del self.map[freq_node.pop_last()[0]]
			self.map[key] = Node(key, value, self.lower_freq)
			self.lower_freq.add_val(self.map[key])
		else:
			self.map[key].val = value
			self._update_node(self.map[key])

	def _update_node(self, node):
		if node.freq_node is self.higher_freq:
			self.higher_freq.upper = FreqNode()
			self.higher_freq = self.higher_freq.upper
		node.freq_node.del_node(node)
		node.left = None
		node.right = None
		node.freq_node.upper.add_val(node)
		node.freq_node = node.freq_node.upper

	def __str__(self):
		s = ' *'
		freq = self.lower_freq
		rank = 0
		while freq:
			rank += 1
			s += '\n| | \n[' + str(rank) + ']'
			if not freq.empty():
				s += ' => ' + str(freq)
			freq = freq.upper
		return s


from collections import defaultdict, OrderedDict

class LFUCache:

	def __init__(self, capacity: int):
		self.capacity = capacity
		self.cache = {}
		self.freq = defaultdict(OrderedDict)
		self.min_freq = 0

	def get(self, key: int) -> int:
		if key not in self.cache:
			return -1
		(value, freq) = self.cache[key]
		self.freq[freq].pop(key)
		if not self.freq[self.min_freq]:
			self.min_freq += 1
		self.freq[freq + 1][key] = value
		self.cache[key] = (value, freq + 1)
		return value

	def put(self, key: int, value: int) -> None:
		if self.capacity <= 0:
			return
		if key in self.cache:
			self.cache[key] = (value, self.cache[key][1])
			self.get(key)
			return
		if len(self.cache) >= self.capacity:
			(k, _) = self.freq[self.min_freq].popitem(last=False)
			del self.cache[k]
		self.cache[key] = (value, 1)
		self.freq[1][key] = value
		self.min_freq = 1


class Node:

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

class DLL:

	def __init__(self):
		self.head = Node(0, 0)
		self.tail = Node(0, 0)
		self.head.next = self.tail
		self.tail.prev = self.head
		self.size = 0

	def insert(self, node):
		nxt = self.head.next
		prv = self.head
		nxt.prev = prv.next = node
		node.next = nxt
		node.prev = prv
		self.size += 1

	def remove(self, node):
		node.prev.next = node.next
		node.next.prev = node.prev
		self.size -= 1

class LFUCache:

	def __init__(self, capacity: int):
		self.max = capacity
		self.freq_map = {}
		self.hash_map = {}
		self.min_freq = 0
		self.size = 0

	def update(self, key: int) -> None:
		node = self.hash_map[key]
		afreq = node.freq
		oldDLL = self.freq_map[afreq]
		oldDLL.remove(node)
		if self.min_freq == afreq and oldDLL.size == 0:
			self.min_freq += 1
		node.freq += 1
		if node.freq in self.freq_map:
			newDLL = self.freq_map[node.freq]
		else:
			newDLL = DLL()
			self.freq_map[node.freq] = newDLL
		newDLL.insert(node)

	def get(self, key: int) -> int:
		if key in self.hash_map:
			self.update(key)
			return self.hash_map[key].value
		else:
			return -1

	def put(self, key: int, value: int) -> None:
		if self.max == 0:
			return
		if key in self.hash_map:
			self.hash_map[key].value = value
			self.update(key)
		else:
			if self.size == self.max:
				minDLL = self.freq_map[self.min_freq]
				least = minDLL.tail.prev
				minDLL.remove(least)
				del self.hash_map[least.key]
				self.size -= 1
			new = Node(key, value)
			self.hash_map[key] = new
			if 1 in self.freq_map:
				self.freq_map[1].insert(new)
			else:
				new_DLL = DLL()
				self.freq_map[1] = new_DLL
				self.freq_map[1].insert(new)
			self.min_freq = 1
			self.size += 1


from collections import defaultdict
from collections import OrderedDict

class Node:

	def __init__(self, key, val, count):
		self.key = key
		self.val = val
		self.count = count

class LFUCache:

	def __init__(self, capacity: int):
		self.cap = capacity
		self.key2node = {}
		self.count2node = defaultdict(OrderedDict)
		self.minCount = None

	def get(self, key):
		if key not in self.key2node:
			return -1
		node = self.key2node[key]
		del self.count2node[node.count][key]
		if not self.count2node[node.count]:
			del self.count2node[node.count]
		node.count += 1
		self.count2node[node.count][key] = node
		if not self.count2node[self.minCount]:
			self.minCount += 1
		return node.val

	def put(self, key, value):
		if not self.cap:
			return
		if key in self.key2node:
			self.key2node[key].val = value
			self.get(key)
			return
		if len(self.key2node) == self.cap:
			(k, n) = self.count2node[self.minCount].popitem(last=False)
			del self.key2node[k]
		self.count2node[1][key] = self.key2node[key] = Node(key, value, 1)
		self.minCount = 1
		return