• I use a dictionary to map to key to data nodes.
The data nodes are linked together with nodes with the exact same frequency count, headed by a dummy node. The dummy node contains one value: the count.
I also have a linked list of dummy nodes, with the head being the smallest frequency count.
Data nodes have pointer to their dummy node parent, allowing for O(1) access.
Since incrementing frequency is always count + 1 we either 1) get the next dummy node if it is count + 1, or 2) insert a new dummy node next to it and set it's frequency count to count + 1.
We then insert the new data node into the following dummy node.
We will delete the previous dummy node if unlinking the data node from its previous dummy node empties the linked list.

``````class LFUCache(object):
class DummyNode(object):
def __init__(self, count_value):
self.count_value = count_value
self.next_node = self
self.prev_node = self
self.next_freq = self
self.prev_freq = self
class DataNode(object):
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.dummy_node = self
self.next_node = self
self.prev_node = self

def __init__(self, capacity):
"""

:type capacity: int
"""
self._max_capacity = capacity
self._data_node_dict = {}
self._lfu_dummy_node_list = LFUCache.DummyNode(0)

def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self._data_node_dict:
return -1

node = self._data_node_dict[key]
self._increment_node_frequency(node)
return node.value

def set(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if self._max_capacity == 0:
return

if key not in self._data_node_dict:
node = LFUCache.DataNode(key,value)
if len(self._data_node_dict) == self._max_capacity:
self._delete_least_used_node()
self._data_node_dict[key] = node
root_dummy = self._lfu_dummy_node_list
if root_dummy.next_freq.count_value != 1:
new_dummy = LFUCache.DummyNode(1)
self._insert_next_freq_dummy_node(root_dummy,new_dummy)
else :
node = self._data_node_dict[key]
node.value = value
self._increment_node_frequency(node)

def _increment_node_frequency(self, node):
old_dummy = node.dummy_node
new_count_val = old_dummy.count_value + 1
if old_dummy.next_freq.count_value != new_count_val:
new_dummy = LFUCache.DummyNode(new_count_val)
self._insert_next_freq_dummy_node(old_dummy,new_dummy)
dummy = old_dummy.next_freq
return node.value

def _insert_next_freq_dummy_node(self, prev_dummy, next_dummy):
next_dummy.next_freq = prev_dummy.next_freq
next_dummy.prev_freq = prev_dummy
prev_dummy.next_freq.prev_freq = next_dummy
prev_dummy.next_freq = next_dummy

node.next_node = dummy.next_node
node.prev_node = dummy
dummy.next_node.prev_node = node
dummy.next_node = node
node.dummy_node = dummy

dummy = node.dummy_node
node.prev_node.next_node = node.next_node
node.next_node.prev_node = node.prev_node
if dummy.next_node == dummy : #delete dummy node
dummy.prev_freq.next_freq = dummy.next_freq
dummy.next_freq.prev_freq = dummy.prev_freq
del dummy

def _delete_least_used_node(self):
least_used_dummy = self._lfu_dummy_node_list.next_freq
least_used = least_used_dummy.prev_node