Concise Python O(1) beats 95% using two maps.

• Two hashmaps: the freq_map keeps track of freq-> linked list of node.
key_map tracks key->val

``````PREV,NEXT,KEY,VAL,FREQ = 0,1,2,3,4
class LFUCache(object):

def __init__(self, capacity):
self.capacity = capacity
self.freq_map = {}
self.key_map = {}
self.min_freq = 1

def get(self, key):
key_map, freq_map = self.key_map, self.freq_map
if key not in key_map:
return -1
else:
val_node = key_map[key]
val_node[PREV][NEXT],val_node[NEXT][PREV] = val_node[NEXT],val_node[PREV]
if freq_map[self.min_freq] is freq_map[self.min_freq][NEXT]:
self.min_freq+=1
freq = val_node[FREQ]
root = freq_map.setdefault(freq+1,[])
if not root:
root[:] = [root,root,None,None,freq+1]
val_node[PREV],val_node[NEXT] = root[PREV],root
val_node[FREQ]+=1
root[PREV][NEXT] = root[PREV] = val_node
return key_map[key][VAL]

def set(self, key, value):
key_map, freq_map, cap = self.key_map, self.freq_map, self.capacity
if not cap:
return
if key in key_map:
key_map[key][VAL] = value
self.get(key)
else:
if len(key_map) == cap:
root = freq_map[self.min_freq]
node_evict = root[NEXT]
root[NEXT],node_evict[NEXT][PREV] = node_evict[NEXT], root
del key_map[node_evict[KEY]]
self.min_freq = 1
val_node = [None,None,key,value,1]
root = freq_map.setdefault(1,[])
if not root:
root[:] = [root,root,None,None,1]
val_node[PREV],val_node[NEXT] = root[PREV],root
root[PREV][NEXT] = root[PREV] = val_node
key_map[key] = val_node
``````

• Could you explain
root = freq_map.setdefault(1,[])
if not root:
root[:] = [root,root,None,None,1]
val_node[PREV],val_node[NEXT] = root[PREV],root

what is root?

• @chenweisomebody
"root" is a circular double linked list, represented by a list. At the initialization, root's PREV and NEXT point to itself.

In python's collections.py, the LRU_Cache is implemented this way, from which I was inspired.

• @xiyayan Another question is why you need to do the copy, like
key_map, freq_map = self.key_map, self.freq_map
key_map, freq_map, cap = self.key_map, self.freq_map, self.capacity
Couldn't you modify on self.map directly?

• @chenweisomebody
That's is for performance consideration. Accessing local variable is always faster. I put it this way just out of a habit.

• Can you explain how to update the freq_map and keep track of the freq to node?
Thank you!

• This post is deleted!

• @chenweisomebody
"root" is a circular double linked list, represented by a list. At the initialization, root's PREV and NEXT point to itself.

In python's collections.py, the LRU_Cache is implemented this way, from which I was inspired.

+1 for referencing python source code :) the correct link is here

• Same idea except, but using "deque" (doubly linked list by python) to maintain LRU queue of frequencies -

``````class LFUCache(object):

def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity   = capacity
self.kvstore    = dict()
self.freqstore  = collections.defaultdict(collections.deque)
self.used       = 0
self.minfreq    = 1

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

(value,freq) = self.kvstore[key]
self.freqstore[freq].remove(key)
if not self.freqstore[freq]:
del self.freqstore[freq]
if self.minfreq == freq:
self.minfreq = freq + 1
self.kvstore[key] = (value,freq+1)
self.freqstore[freq+1].append(key)
return value

def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if self.capacity:
if key not in self.kvstore:
while self.used >= self.capacity:
evicting_key = self.freqstore[self.minfreq].popleft()
if not self.freqstore[self.minfreq]:
del self.freqstore[self.minfreq]
del self.kvstore[evicting_key]
self.used -= 1
self.used += 1
self.kvstore[key] = (value,1)
self.freqstore[1].append(key)
self.minfreq = 1
else:
oldvalue, freq = self.kvstore[key]
self.freqstore[freq].remove(key)
if not self.freqstore[freq]:
if freq == self.minfreq:
self.minfreq = freq + 1
del self.freqstore[freq]
self.kvstore[key] = (value,freq+1)
self.freqstore[freq+1].append(key)
``````

• @xiyayan

``````val_node = key_map[key]
val_node[PREV][NEXT],val_node[NEXT][PREV] = val_node[NEXT],val_node[PREV]
if freq_map[self.min_freq] is freq_map[self.min_freq][NEXT]:
self.min_freq+=1
``````

here what if min_freq is not the frequency of the node you get , i think the judgement should be

``````if freq_map[self.min_freq] is freq_map[self.min_freq][NEXT] and self.min_freq==val_node[FREQ]:
self.min_freq+=1
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.