Pergunta de entrevista da empresa Varonis Systems
Implement local in-memory cache util that uses LRU as an eviction algorithm and works in a multithreaded environment. LRU means evicting the item that hasn’t been accessed the longest in case the cache is full. Each item should also hold a TTL and return Null when trying to fetch an item that its TTL passed. In addition, the cache should be limited in size. The perfomance (get, set) should be in optimal time.
Resposta da entrevista
Sigiloso
The cache is very straightforward (Python) dictionary that implements the TTL and is_cache_full check. The tricky part, which I did not succeeded solving, was implementing the LRU in O(1) time. The trick is setting each value (set(key, val) item part of a linked list, so that it has references to who is older and newer than it. For this, you need to also keep self.head, self.tail, which are cache keys to the last accessed and least accessed keys. When an item is accessed, you "remove" it from it's current position in the linked list, and move it to the head. if the cache is full, you can handle that case as well since you have the key to the oldest element. A very none trivial solution in my opinion.