Implement Promise based memoization with a given cache size behaving as an LRU cache with an expiry time and auto cache burst.
First, what we have to do is breakdown the terms in the problem statement to understand what is going on and what we are asked to do.
- Promise based memoization: Memoization is one of the ways we can improve the performance of functions by eliminating redundant calls. Memoization is a technique where we store the results of a function call in a cache and return the result from the cache if the function is called again with the same arguments.
let memoize = (fn) => {
let cache = {};
return (...args) => {
let key = JSON.stringify(args);
if (key in cache) {
return cache[key];
} else {
let result = fn(...args);
cache[key] = result;
}
}
}
- LRU cache: The LRU cache is a data structure that is used to store the most recently used items in a cache. However in our problem statement, it is specified that the cache is a fixed size that means the least recently used item is removed when the cache is full.
class LRUCache {
public cache: Map<number | string, LRUCacheNode>;
private capacity: number;
private head: LRUCacheNode;
private tail: LRUCacheNode;
constructor(capacity: number) {
this.cache = new Map();
this.head = new LRUCacheNode('head', 0, 0);
this.tail = new LRUCacheNode('tail', 0, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
this.capacity = capacity;
}
length(): number {
return this.cache.size;
}
get(key: number | string): number {
if (this.cache.has(key)) {
const value = this.cache.get(key);
if (value?.isExpired()) {
this.cache.delete(key);
return -1;
}
value.prev.next = value?.next;
value.next.prev = value?.prev;
this.tail.prev.next = value;
value.prev = this.tail.prev;
value.next = this.tail;
this.tail.prev = value;
return value.value;
}
return -1;
}
put(
key: number,
value: number,
expiryTime: number = 0,
): void {
if (this.get(key) !== -1) {
this.tail.prev.value = value;
}
if (this.cache.size === this.capacity) {
const first = this.cache.keys().next().value;
this.cache.delete(first);
this.head.next = this.head.next.next;
this.head.next.prev = this.head;
}
const newNode = new LRUCacheNode(
key,
value,
expiryTime,
);
this.cache.set(key, newNode);
this.tail.prev.next = newNode;
newNode.prev = this.tail.prev;
newNode.next = this.tail;
this.tail.prev = newNode;
}
}
-
with an expiry time: Because we don't have sufficient context, we can assume the expiry time is the time after which the cache is automatically cleared or after which an item is removed from the cache.
-
auto cache burst: Cache burst is a feature that is used to remove an item from the cache after a specific time period. We can use this piece of information to infer that it is the time after which an item in the cache is cleared.
<!-- This means that we are going to create a LRUCacheNode Instance that stores the key, value with information about whether it expires or not -->
class LRUCacheNode {
public key: number | string;
public value: number;
public expires: Boolean;
public expiryTime: number;
public next: LRUCacheNode | undefined;
public prev: LRUCacheNode | undefined;
constructor(
key: number | string,
value: number,
expiryTime: number,
) {
this.key = key;
this.value = value;
this.next = {};
this.prev = {};
this.expires = !!expiryTime;
this.expiryTime = expiryTime + DATE;
}
isExpired(): Boolean {
return this.expires && this.expiryTime < Date.now();
}
}
We can therefore update our LRUCache class that will be used to store the cache and the LRUCacheNode class that will be used to store the cache nodes.
const DATE = Date.now();
class LRUCacheNode {
public key: number | string;
public value: number;
public expires: Boolean;
public expiryTime: number;
public next: LRUCacheNode | undefined;
public prev: LRUCacheNode | undefined;
constructor(
key: number | string,
value: number,
expiryTime: number,
) {
this.key = key;
this.value = value;
this.next = {};
this.prev = {};
this.expires = !!expiryTime;
this.expiryTime = expiryTime + DATE;
}
isExpired(): Boolean {
console.log('this', this.expires, this.key);
return this.expires && this.expiryTime < Date.now();
}
}
class LRUCache {
public cache: Map<number | string, LRUCacheNode>;
private capacity: number;
private head: LRUCacheNode;
private tail: LRUCacheNode;
constructor(capacity: number) {
this.cache = new Map();
this.head = new LRUCacheNode('head', 0, 0);
this.tail = new LRUCacheNode('tail', 0, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
this.capacity = capacity;
}
length(): number {
return this.cache.size;
}
get(key: number | string): number {
if (this.cache.has(key)) {
const value = this.cache.get(key);
if (value?.isExpired()) {
this.cache.delete(key);
return -1;
}
value.prev.next = value?.next;
value.next.prev = value?.prev;
this.tail.prev.next = value;
value.prev = this.tail.prev;
value.next = this.tail;
this.tail.prev = value;
return value.value;
}
return -1;
}
put(
key: number,
value: number,
expiryTime: number = 0,
): void {
if (this.get(key) !== -1) {
this.tail.prev.value = value;
}
if (this.cache.size === this.capacity) {
const first = this.cache.keys().next().value;
this.cache.delete(first);
this.head.next = this.head.next.next;
this.head.next.prev = this.head;
}
const newNode = new LRUCacheNode(
key,
value,
expiryTime,
);
this.cache.set(key, newNode);
this.tail.prev.next = newNode;
newNode.prev = this.tail.prev;
newNode.next = this.tail;
this.tail.prev = newNode;
}
}
const test = new LRUCache(3);
console.log('length', test.length());
console.log('put 2', test.put(2, 4));
console.log('put 3', test.put(3, 5, 5000));
console.log('length', test.length());
console.log('get 2', test.get(2));
console.log('length', test.length());
console.log('put 3', test.put(4, 6));
console.log('length', test.length());
const sleep = (time: number) =>
new Promise((resolve) => setTimeout(resolve, time));
sleep(5000).then(() => {
console.log('value', test.get(3));
// console.log('cache', test.cache)
console.log('length', test.length());
});
Nice work :P