Pergunta de entrevista da empresa G-Research
Implement "most recently used" cache eviction strategy (in the context of a memoized function).
Resposta da entrevista
Sigiloso
6 de set. de 2017
That can be done using a combination of dictionary (for quickly finding the cache entry in normal operation) and doubly-linked list (for ordering the entries for eviction), where you always rewire the last-accessed node to the front of the list. When the cache gets too large, it's easy to just remove the head of the list (and the corresponding dictionary key).