Questions / Quant development, Trading system components
An LRU cache on a short trace
The cache holds two keys. What does this print?
from collections import OrderedDict
class LRU:
def __init__(self, cap):
self.cap, self.d = cap, OrderedDict()
def get(self, k):
if k not in self.d:
return None
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)
c, misses = LRU(2), 0
for k in "ABACBDA":
if c.get(k) is None:
misses += 1
c.put(k, 1)
print(misses)Answer it in the app It's free. You get hints, a second try if you miss, and a follow-up question.
Show the answer and worked solution
Answer: 6 count
- A miss, B miss, A hit (A now most recent).
- C miss evicts B; B miss evicts A.
- D miss evicts C; A miss evicts B.
- Misses: 6.
Interview shortcut. Track the order after each step: [A,B] → [B,A] → [A,C] → [C,B] → [B,D] → [D,A].
Takeaway. LRU evicts the key touched longest ago, counting reads.
In the app this has a follow-up where one thing about the setup changes. Try the follow-up.