This is my first submission, please bare with me for any problem. Having learned a lot from the discussion and decide, maybe as a new year resolution, I should contribute if I can. Didn't find python solution in the discussion, so I'd like to share mine. The idea is similar to many existing solutions that use a double linked list to track the frequencies of each item and put all items that have the same frequency into one node. Inside that node, use collections.OrderedDict to track the ordering of items be added (so we know which item to be popped out if need to remove).

Defined a `move_forward()`

helper function for either adding new item or setting and getting existing items from the cache, as all these operations will adds 1 frequency of an item.

Please let me know if you have any question and suggestion. Thanks.

```
class LFUNode(object):
def __init__(self, frequency):
self.frequency = frequency
# use ordered dict for removing the first item added
self.od = collections.OrderedDict()
self.pre, self.next = None, None
class LFUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.cap = capacity
self.size = 0
self.map = {}
self.head = LFUNode(0)
self.tail = LFUNode(0)
self.head.next = self.tail
self.tail.pre = self.head
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self.map:
return -1
node = self.map[key]
res = node.od[key]
node.od.pop(key)
self.move_forward(node, key, res)
return res
def pop_item(self):
node = self.tail
while len(node.pre.od) == 0:
# remove the pre node that has no item saved on that
node.pre = node.pre.pre
node.pre.next = node
(k, v) = node.pre.od.popitem(last = False)
self.map.pop(k)
def move_forward(self, node, key, value):
# Add new item
if node.pre == self.head or node.pre.frequency != node.frequency + 1:
pre_node = LFUNode(node.frequency + 1)
pre_node.pre = node.pre
node.pre = pre_node
pre_node.pre.next = pre_node
pre_node.next = node
else:
pre_node = node.pre
pre_node.od[key] = value
self.map[key] = pre_node
def set(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if self.cap == 0:
return
if key in self.map:
node = self.map[key]
node.od.pop(key)
self.move_forward(node, key, value)
else:
if self.size == self.cap:
self.pop_item()
else:
self.size += 1
self.move_forward(self.tail, key, value)
```