Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism. It should support the following operations: get for data and PUT for writing data.

Get (key) – Gets the value of the key if it exists in the cache (always positive), otherwise -1 is returned. Write data PUT (key, value) – Writes data if the key does not exist. When the cache reaches its maximum capacity, it should delete the oldest unused data before writing new data to make room for new data.

Advanced:

Can you do both in O(1) time?

Example:

LRUCache cache = new LRUCache(2 /* Cache capacity */); cache.put(1, 1); cache.put(2, 2); cache.get(1); // return 1 cache. Put (3, 3); Cache.get (2); // This operation invalidates key 2. // return -1 (not found) cache.put(4, 4); Cache.get (1); // This operation invalidates key 1. // return -1 (not found) cache.get(3); // return 3 cache.get(4); / / return 4Copy the code

Answer key

function LRUCache(max) { this.map = new Map(); this.max = max; } LRUCache.prototype.get = function (key) { if (! this.map.has(key)) return -1; const value = this.map.get(key); this.map.delete(key); this.map.set(key, value); return value; }; LRUCache.prototype.put = function (key, value) { if (this.map.has(key)) this.map.delete(key); this.map.set(key, value); if (this.map.size > this.max) this.map.delete(this.map.keys().next().value); }; LRUCache.prototype.getData = function () { return [...this.map]; };Copy the code