# Simple Python solution fails long test case, did it on paper and I agree with my solution

• Disclaimer: I'm looking for a simple functional solution, not an optimal one.

So my solution seems to be working for most test cases, but fails the following more complicated one. The problem is: I did it on paper (a little bit tedious), and I agree with my solution, not leetcode's. The key 6 should indeed be replaced by the 7, such that at execution 49, get 6 should return -1 and not 14.

Input:

``````["LFUCache","set","set","set","set","set","get","set","get","get","set","get","set","set","set","get","set","get","get","get","get","set","set","get","get","get","set","set","get","set","get","set","get","get","get","set","set","set","get","set","get","get","set","set","get","set","set","set","set","get","set","set","get","set","set","get","set","set","set","set","set","get","set","set","get","set","get","get","get","set","get","get","set","set","set","set","get","set","set","set","set","get","get","get","set","set","set","get","set","set","set","get","set","set","set","get","get","get","set","set","set","set","get","set","set","set","set","set","set","set"]
[[10],[10,13],[3,17],[6,11],[10,5],[9,10],[13],[2,19],[2],[3],[5,25],[8],[9,22],[5,5],[1,30],[11],[9,12],[7],[5],[8],[9],[4,30],[9,3],[9],[10],[10],[6,14],[3,1],[3],[10,11],[8],[2,14],[1],[5],[4],[11,4],[12,24],[5,18],[13],[7,23],[8],[12],[3,27],[2,12],[5],[2,9],[13,4],[8,18],[1,7],[6],[9,29],[8,21],[5],[6,30],[1,12],[10],[4,15],[7,22],[11,26],[8,17],[9,29],[5],[3,4],[11,30],[12],[4,29],[3],[9],[6],[3,4],[1],[10],[3,29],[10,28],[1,20],[11,13],[3],[3,12],[3,8],[10,9],[3,26],[8],[7],[5],[13,17],[2,27],[11,15],[12],[9,19],[2,15],[3,16],[1],[12,17],[9,1],[6,19],[4],[5],[5],[8,1],[11,7],[5,2],[9,28],[1],[2,2],[7,4],[4,22],[7,24],[9,26],[13,28],[11,26]]
``````

Output:

``````[null,null,null,null,null,null,-1,null,19,17,null,-1,null,null,null,-1,null,-1,5,-1,12,null,null,3,5,5,null,null,1,null,-1,null,30,5,30,null,null,null,-1,null,-1,24,null,null,18,null,null,null,null,-1,null,null,18,null,null,11,null,null,null,null,null,18,null,null,24,null,4,29,-1,null,12,11,null,null,null,null,29,null,null,null,null,17,-1,18,null,null,null,24,null,null,null,20,null,null,null,29,18,18,null,null,null,null,20,null,null,null,null,null,null,null]
``````

Expected:

``````[null,null,null,null,null,null,-1,null,19,17,null,-1,null,null,null,-1,null,-1,5,-1,12,null,null,3,5,5,null,null,1,null,-1,null,30,5,30,null,null,null,-1,null,-1,24,null,null,18,null,null,null,null,14,null,null,18,null,null,11,null,null,null,null,null,18,null,null,-1,null,4,29,30,null,12,11,null,null,null,null,29,null,null,null,null,17,-1,18,null,null,null,-1,null,null,null,20,null,null,null,29,18,18,null,null,null,null,20,null,null,null,null,null,null,null]
``````

My code:

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

def __init__(self, capacity):
"""

:type capacity: int
"""

self.capacity = capacity
self.num = 0
self.command_id = 0

self.vals = {}
self.usage = {}
self.last_usage = {}

def get(self, key):
"""
:type key: int
:rtype: int
"""

self.command_id += 1

if key in self.vals:
self.usage[key] += 1
self.last_usage[key] = self.command_id
return self.vals[key]
else:
return -1

def set(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""

self.command_id += 1

if self.capacity == 0:
return

min_val = None
exists = key in self.vals

if not exists and self.num == self.capacity:
# Find lowest value.
for k in self.vals:
if min_val is None or self.usage[k] < self.usage[min_val] \
or (self.usage[k] == self.usage[min_val] and self.last_usage[k] < self.last_usage[min_val]):
min_val = k

# Remove it.
del self.vals[min_val]
del self.usage[min_val]
del self.last_usage[min_val]
self.num -= 1

self.vals[key] = value
self.last_usage[key] = self.command_id

if not exists:
self.usage[key] = 0
self.num += 1
``````

• I had a similar problem and it was due to an incomplete explanation of the expected behavior. The solution updates the access count when you set a key that already exists in the cache.

• Wow, okay. That was not properly explained. Thanks for the reply!

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