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
andvalue
will have values between-1000000000
and1000000000
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);
We'll now take you through what you need to know.
How do I use this guide?