OA: Memoizing LRU cache that survives crashes

You're given the outline of a memoizing cache in the spirit of functools.lru_cache, and its key function is broken: it chokes on unhashable arguments and treats f(a=1, b=2) and f(b=2, a=1) as different calls. Write the class properly.

Implement LRU(capacity):

• generate_key(*args, **kwargs) returns a hashable key. Two argument lists must get equal keys exactly when their positional arguments are pairwise equal (==) and their keyword arguments are equal as dicts. So:
  • keyword order doesn't matter;
  • arguments may be lists, dicts and sets, nested to any depth (and mixed with ints, strings, tuples, None, ...);
  • values that Python considers unequal must not collide: [1, 2] vs (1, 2), {"a": 1} vs [("a", 1)], f(1) vs f((1,)), a positional argument vs the same value passed by keyword.
• call(func, *args, **kwargs) returns func(*args, **kwargs), memoized. The cache entry is identified by func.__name__ (assume names are unique) together with generate_key(*args, **kwargs).
  • A hit returns the stored value without calling func and makes the entry most recently used.
  • A miss calls func, stores the result as most recently used, and if there are now more than capacity entries, evicts the least recently used one.

Both hits and misses must be O(1) apart from building the key (OrderedDict.move_to_end or a dict plus a doubly linked list).

cache = LRU(2)
cache.call(add, 1, 2)       # miss: add runs, returns 3
cache.call(add, 1, 2)       # hit: add is not called
cache.call(add, a=1, b=2)   # miss: passing by keyword is a different call
cache.call(add, b=2, a=1)   # hit: same call as the previous one
cache.generate_key([1, {"k": 2}], y=3) == cache.generate_key([1, {"k": 2}], y=3)   # True