LRU Cache Class
Programming Interview
Hard
8 views
Problem Description
Cache capacity cap is provided and q commands: PUT k v, GET k. Implement LRUCache class. For GET output value or -1.
Input Format
Line1 cap. Line2 q. Next q lines commands.
Output Format
Outputs for GET.
Sample Test Case
Input:
2
6
PUT a 1
PUT b 2
GET a
PUT c 3
GET b
GET c
Official Solution
import sys
from collections import OrderedDict
lines=sys.stdin.read().splitlines()
if len(lines)<2: sys.exit(0)
cap=int(lines[0].strip())
q=int(lines[1].strip())
class LRUCache:
def __init__(self,cap):
self.cap=cap
self.od=OrderedDict()
def get(self,k):
if k in self.od:
v=self.od.pop(k)
self.od[k]=v
return v
return None
def put(self,k,v):
if k in self.od:
self.od.pop(k)
self.od[k]=v
if len(self.od)>self.cap:
self.od.popitem(last=False)
cache=LRUCache(cap)
out=[]
for i in range(q):
parts=(lines[2+i] if 2+i<len(lines) else '').split()
if not parts: continue
if parts[0]=='GET':
v=cache.get(parts[1])
out.append(str(v) if v is not None else '-1')
else:
cache.put(parts[1],parts[2])
print('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!