6 views
# LRU Cache OrderedDict (Practice 5029): Drill Interviewers use this pattern to test whether you can state the invariant before coding. Here is a compact rehearsal note. ## Approach move_to_end on get/put. ```python 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) ``` ## Complexity Linear in the dominant input size for the scan; heap/tree variants add a log factor. ## Interview pitfalls State the invariant out loud, name the complexity, then code. Skipping the invariant is the usual fail mode. ## Practicing out loud Narrate the approach, complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see [the Linkjob AI app](https://www.linkjob.ai/).