LRU Cache Simulator
Hard
Programming Interview
OOP
26 views
Problem Statement
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.
Example
2 6 PUT a 10 PUT b 20 GET a PUT c 30 GET b GET c
10 -1 30
Constraints
Total operations up to 200000.
Input / Output Format
Input Format
See description.
Output Format
See description.
Constraints
Total operations up to 200000.
Examples
Input:
2 6
PUT a 10
PUT b 20
GET a
PUT c 30
GET b
GET c
Output:
10
-1
30
Example Solution (Public)
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))
Official Solution Code
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))
Please login to submit solutions.