Every LRU cache is built on one small structure: a list of keys ordered from most to least recently used, where you can move any key to the front and drop the oldest key in O(1). Build just that part, with no capacity or values yet.
Implement class RecencyList:
RecencyList()starts empty.touch(key)makeskeythe most recently used. If it's new, add it; if it's already there, move it to the front.pop_oldest()removes the least recently used key and returns it, or returnsNoneif the list is empty.__len__()returns the number of keys.keys()returns a Python list of all keys, most recent first (used by the tests; O(n) is fine here).
r = RecencyList()
r.touch("a"); r.touch("b"); r.touch("c")
r.keys() # ["c", "b", "a"]
r.touch("a") # "a" moves to the front
r.keys() # ["a", "c", "b"]
r.pop_oldest() # "b"
len(r) # 2
touch and pop_oldest must be O(1): the tests do 200,000 operations. Use a dict from key to node plus a doubly linked list with sentinel head and tail nodes. Don't use OrderedDict or scan a Python list.
Show hint
store the key inside each node, so that when you unlink tail.prev you know which dict entry to delete; sentinels mean unlink and push-front never need if checks for None.