Pregunta de entrevista de Gigya

Design or write in pseudo code an implementation for LRU Cache (least recently used cache). The collection will have a defined maximum number of items (Item = Key & Value), and will only keep the items that were used most recently. If requested to exceed the maximum number of items, the oldest items will be removed from the cache. Each time you add a new item, set a new value to an item, or read the value of item that exists in the cache, it is considered to be a most recently used item and should be removed last. You should consider and explain the performance and complexity of your solution each time you set or read an item, the desired complexity should be less than O(N).