[Challenge | Medium/Hard] In-Memory Cache for Storing Bytes

[403-html]

In-Memory Cache for Storing Bytes

Implement an in-memory cache that can store bytes of data and has a maximum capacity. When the cache is full, it should evict the least recently used data to make room for new data.

Your implementation should include the following features:

• The cache should be able to store data of any size, up to its maximum capacity.
• The cache should have a configurable maximum capacity.
• When the cache is full and a new item is added, the least recently used item should be evicted to make room for the new item.
• The cache should have methods for adding, retrieving, and removing items.

Your implementation should have the following methods:

constructor(capacity: number)

This constructs a new cache instance with the specified maximum capacity.

set(key: string, value: Buffer)

This adds the given value to the cache with the specified key, overwriting any existing value with the same key. If the cache is full and the new value cannot be added without exceeding the maximum capacity, the least recently used item should be evicted to make room for the new value.

get(key: string): Buffer

This retrieves the value associated with the specified key from the cache. If the key is not found, this method should return null.

remove(key: string)

This removes the item with the specified key from the cache, if it exists.

clear()

This removes all items from the cache, if it exists.

getCapacity(): number

This get capacity of the cache.

setCapacity(capacity: number)

This set new capacity for the cache, if it's lower than current values remove them until they match new size.

Example

const cache = new InMemoryCache(1024); // maximum capacity of 1024 bytes

// Add some data to the cache
cache.set('key1', Buffer.from('value1'));
cache.set('key2', Buffer.from('value2'));
cache.set('key3', Buffer.from('value3'));

// Retrieve the data
console.log(cache.get('key1')); // should print 'value1'
console.log(cache.get('key2')); // should print 'value2'
console.log(cache.get('key3')); // should print 'value3'

// Remove an item from the cache
cache.remove('key2');
console.log(cache.get('key2')); // should print 'null'

// Try to add an item that exceeds the maximum capacity
cache.set('key4', Buffer.from('value4')); // should evict the least recently used item ('key1')
console.log(cache.get('key1')); // should print 'null'

Constraints

• The constructor method should have O(1) time complexity.
• The set, get, and remove methods should have O(1) time complexity.
• The set method should have O(1) space complexity.
• The cache should use no more than O(N) additional space, where N is the maximum capacity.

Good luck!