# Help please. O(n) Python Soln - Can't figure out what's wrong.

• I figured I'll move to the O(1) soln after solving it in O(n)

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

def __init__(self, capacity):
"""

:type capacity: int
"""

self.c = capacity
self.d = {}
self.f = {}
self.l = []

def get(self, key):
"""
:type key: int
:rtype: int
"""
d = self.d
f = self.f
c = self.c
l = self.l

if c==0:
return -1

if key in d:
print('Key {} Found. Value = {}'.format(key,d[key]))
f[key]+=1

if key in l:
l.remove(key)

l.append(key)

return d[key]

else:
return -1

def set(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
d = self.d
f = self.f
c = self.c
l = self.l

if c==0:
return

if key not in d:
# If dictionary is at capacity, we need to pop something.
if len(d)==c:
print('Capacity Reached')

print('d = {}'.format(d))
print('f = {}'.format(f))
print('l = {}'.format(l))

# Get least frequently used item
lfu = self.getLFU()

# Delete the retrieved element
del d[lfu]
del f[lfu]
l.remove(lfu)

# Dictionary now has space
print('Setting {}={}'.format(key,value))
d[key] = value
f[key] = 0
if key in l:
l.remove(key)
l.append(key)

def getLFU(self):
d = self.d
f = self.f

min = float('inf')
key = None

lru = []
# Find the min
for k,v in f.items():
if v < min:
min = v
key = k

# Check for same min
for k,v in f.items():
if v==min:
lru.append(k)

# If lru has more than one element, we have a couple of elements with the same frequency.
# Now we need to return the least recently used element in these.
if len(lru)>1:
return self.getLRU(lru)
else:
print('LFU Key deleted = {}'.format(key))
return key

# Compares their indices and returns the one with least
# Least index means least recent
def getLRU(self,lru):
l = self.l

min = float('inf')
key = None

for k in lru:
index = l.index(k)

if index<min:
key = k
min = index

print('LRU Key deleted = {}'.format(key))
return key

# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.set(key,value)
``````

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