Exercise 1 solution

    from collections import OrderedDict

    class LRUCache:
        def __init__(self, capacity):
            self.capacity = capacity
            self.data = OrderedDict()

        def get(self, key, default=None):
            if key not in self.data:
                return default
            self.data.move_to_end(key)          # now the most recently used
            return self.data[key]

        def put(self, key, value):
            if key in self.data:
                self.data.move_to_end(key)
            self.data[key] = value
            if len(self.data) > self.capacity:
                self.data.popitem(last=False)   # drop the least recently used

        def keys(self):
            return list(self.data)

    c = LRUCache(3)
    c.put("a", 1)
    c.put("b", 2)
    c.put("c", 3)
    print(c.keys())
    print(c.get("a"), c.keys())
    c.put("d", 4)
    print(c.keys(), c.get("b"))
    c.put("c", 30)
    print(c.keys(), c.get("c"))
    c.put("e", 5)
    print(c.keys())

Output:
    ['a', 'b', 'c']
    1 ['b', 'c', 'a']
    ['c', 'a', 'd'] None
    ['a', 'd', 'c'] 30
    ['d', 'c', 'e']

Two needs meet here: find a key in constant time (a hash table) and know
which key was used least recently (an order). An OrderedDict is both at once:
a hash table whose entries also form an ordered chain, so move_to_end and
popitem(last=False) are constant-time moves. After reading "a" it moves to the
back, so when "d" overflows the cache it is "b", the least recently used, that
is dropped. Updating "c" counts as a use too. Keeping a plain dict plus a
separate list of keys would work, but moving a key within a list costs a
linear scan each time.