Here is the interview question prompt, presented for reference.

A cache (pronounced cash) is a place of storage that allows for faster data retrieval. Separate from the main data storage, it's usually faster memory that houses frequently accessed values.

With a cache in place, when a client application needs to access data, it'll check the cache first before going to main memory. As an example, web browsers will typically download a page once, and refer to its cached assets in future calls to help speed up the experience.

To determine whether something should be cached, a few eviction strategies are used. IBM refers to eviction as "a feature where file data blocks in the cache are released when fileset usage exceeds the fileset soft quota, and space is created for new files". The process of releasing blocks is called eviction.

One of the most common is LRU, or Least Recently Used. It's exactly as it sounds-- we keep track of usage so that we can "evict" the least recently used key.

Can you implement a LRU Cache where the following code would properly work with some constraints?

// initialize with a capacity of 3 keys
const cache = new Cache(3);
cache.put(1, 1);
cache.put(2, 4);
cache.put(3, 9);
cache.get(1);      // returns 1
cache.put(4, 16);  // evicts key 2
cache.get(2);      // returns -1

# initialize with a capacity of 3 keys
cache = Cache(3)
cache.put(1, 1)
cache.put(2, 4)
cache.put(3, 9)
cache.get(1)      # returns 1
cache.put(4, 16)  # evicts key 2
cache.get(2)      # returns -1

The put and get methods should have a time complexity of O(1).

Constraints

• The cache size will be <= 100000
• The key and value will have values between -1000000000 and 1000000000

You can see the full challenge with visuals at this link.