Hash Strategies Target: 15s
OrderedDict gives O(1) get/put with LRU eviction. Classic system design building block.
from collections import OrderedDict
class LRU:
def __init__(self, cap):
self.cap = cap
self.d = OrderedDict()
def get(self, k):
if k not in self.d: return -1
self.d.move_to_end(k)
return self.d[k]
def put(self, k, v):
self.d[k] = v
self.d.move_to_end(k)
if len(self.d) > self.cap:
self.d.popitem(last=False)Type it from memory. Go.