LRU Cache Simulator
Python
Hard
2 views
Problem Description
You have cache capacity cap. Commands: GET key, PUT key value. For GET output value if present else -1. LRU eviction is used when capacity exceeded.
Input Format
First line cap. Second line q. Next q lines commands.
Output Format
Outputs for GET commands.
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())
cache=OrderedDict()
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':
k=parts[1]
if k in cache:
v=cache.pop(k)
cache[k]=v
out.append(str(v))
else:
out.append('-1')
else:
k=parts[1]
v=parts[2]
if k in cache:
cache.pop(k)
cache[k]=v
if len(cache)>cap:
cache.popitem(last=False)
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!