Good morning! Here's our prompt for today.

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?

1// initialize with a capacity of 3 keys
2const cache = new Cache(3);
3cache.put(1, 1);
4cache.put(2, 4);
5cache.put(3, 9);
6cache.get(1);      // returns 1
7cache.put(4, 16);  // evicts key 2
8cache.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

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

var assert = require('assert');

​

class Cache {

  constructor(capacity) {

    // do something

  }

}

​

try {

  var cache = new Cache(3);

  cache.put(1, 1);

  cache.put(2, 4);

  cache.put(3, 9);

  assert.equal(cache.get(1), 1);

​

  console.log(

    'PASSED: Initialize a cache of size 3, and run `cache.put(1, 1); cache.put(2, 4); cache.put(3, 9);`. `cache.get(1)` should return 1'

  );

} catch (err) {

  console.log(err);

}

​

try {

  cache.put(4, 16);

  assert.equal(cache.get(2), -1);

​

  console.log('PASSED: ' + '`cache.put(4, 16);` should evict key `2`');

} catch (err) {

  console.log(err);

Here's our guided, illustrated walk-through.

How do I use this guide?