LRU Cache Simulator
Programming Interview
Hard
9 views
Problem Description
Implement an LRU cache of capacity C. You will get q operations: GET key and PUT key value. For each GET print value or -1.
Input Format
See description.
Output Format
See description.
Sample Test Case
Input:
2 6
PUT a 10
PUT b 20
GET a
PUT c 30
GET b
GET c
Constraints
Total operations up to 200000.
Official Solution
import sys
from collections import OrderedDict
lines=sys.stdin.read().splitlines()
if not lines or not lines[0].strip():
sys.exit(0)
C,Q=map(int,lines[0].split())
cache=OrderedDict()
out=[]
for i in range(1,1+Q):
parts=(lines[i] if 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)>C:
cache.popitem(last=False)
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!