Implement LRU and LFU caches

Design a fixed-capacity key-value store that must support two different eviction policies. In both versions the API is the same: get(key) returns the stored value when the key exists, otherwise it returns -1; put(key, value) either creates a new mapping or updates the value for an existing key. Part 1: Recent-use cache Every get for an existing key, and every put that updates an existing key, marks that key as the most recently used. Newly inserted keys are also marked as…