LRU Cache Class

LRU Cache Class

Hard Programming Interview OOP 26 views
Explanation Complexity

Problem Statement

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.

Example

2
6
PUT a 1
PUT b 2
GET a
PUT c 3
GET b
GET c
1
-1
3

Constraints

cap,q

Input / Output Format

Input Format
Line1 cap. Line2 q. Next q lines commands.
Output Format
Outputs for GET.
Constraints
cap,q

Examples

Input:
2 6 PUT a 1 PUT b 2 GET a PUT c 3 GET b GET c
Output:
1 -1 3

Example Solution (Public)

Programming Interview 
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))

Official Solution Code

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))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.