An LRU cache

Build an LRU cache (lesson 7). It holds at most capacity keys, each with a value.

• get(key) returns the value, or -1 if the key is not there. A successful get makes the key the most recently used.
• put(key, value) sets the value and makes the key the most recently used. If the key is new and the cache is full, first throw out the least recently used key.
• Both methods must take O(1) time on average.

C = LRUCache(2)
C.put(1, 1); C.put(2, 2)
C.get(1)       # 1   (now 2 is the least recently used)
C.put(3, 3)    # throws out 2
C.get(2)       # -1

collections.OrderedDict is switched off: build the two-way list yourself.

The tests make an object and call its methods in order. A test shows the list of calls, and compares the list of everything they returned (methods that return nothing give None).

Limits

• Capacity up to 50,000; up to 200,000 calls.