Imaa Minifax
← All writing

Implementing an LRU cache

How I implemented an LRU cache from scratch with a defined capacity and time complexity.

  • #engineering
  • #system-design

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

I am not a senior engineer, at least not yet, but I think I can guide you on how to implement an LRU cache in whatever language. The core concepts transfer. Ideally, in questions like this (and most engineering questions), we’d be given the ‘starting code’

class LRUCache {
	constructor(capacity) {
	this.capacity = capacity;
	this.cache = new Map();
}

get(key) {
	// Your code here
}

put(key, value) {
	// Your code here
}

So, as instructed by the comments, we’d be writing the get and put functions. A Least Recently Used cache is a type of cache that stores the most recently used items in a cache, within its size. That size is important, because that’s what determines how much items it can carry. As an example, imagine we have a shoe shelf that can only store 5 pairs of shoes. If we brought a sixth one, we’d have to remove one pair of shoe to make space for the new shoe we’ve just brought. In most cases we tend to remove the oldest one, because that’s the “least recently used” shoe. Without knowing it, we implement LRU caches in our lives daily.

Important disclaimer: I am yet to learn the fundamentals of average time complexities. I will be answering this question based on what worked for me in passing the question on my tesla prep site. Why this works within the O(1) time complexity, I am yet to find out.

First things first, this line: “Return the value of the key if the key exists, otherwise return -1.” That makes things a bit simpler. We simply check if the cache has the key, if it doesn’t, we return -1.

get(key) {
	// Your code here
	if (!this.cache.has(key)) return -1;
}

That’s one step in the right direction. But what if it does? We still have to return the key. Here is the flow AI used to teach me this that I understood: we get the value from the key, store it in a variable, delete the key, then create a new key (with that same key) using set(). This way, the key gets deleted from its position in the cache and gets inserted into the “most recently used” position in the cache. Which is super important for this to work. If the cache does not monitor which items were most recently used, then that’s a problem because it would not function as intended.

In practice, our get() function will look something like:

get(key) {
	// Your code here
	if (!this.cache.has(key)) return -1;
	
	const value = this.cache.get(key) // we are getting the value of the key here. Next is to delete it then re-insert it.
	this.cache.delete(key);
	this.cache.set(key, value); // the delete function only needs the key but the set function needs the key and the value it will be putting in the key.
	
	// at this point, we can now return the value of the key.
	return value;
}

First off we checked if the key existed in the cache, and if it didn’t we returned -1. If it did, however, we got the value of the key using the get() method, assigned it to a variable, deleted the key from the cache, inserted it again into the cache (which automatically puts it at the front, that’s at the most recently used position), and returned the value. Pretty simple, and functional. Again, why this works in O(1) time, I don’t know. Now that our get function is in order, we turn to the put function.

Put is a little bit more work, but certainly not impossible. For the put function, we are evaluating a number of things. First, we have to ensure the key does not exist (and if it does, we delete it, since we’d be changing the value anyway and we want it to come to the most recently used position), we also have to verify we have not reached the maximum capacity of the cache. If we have reached it, we delete the oldest key in the cache. That’s about it, let’s get to work.

put(key, value) {
	// Your code here
	if (this.cache.has(key)) {
		this.cache.delete(key) // this deletes the key. good.
	} else if (this.cache.size >= this.capacity) { // if the key does not exist, we are now checking to verify we have not hit the maximum capacity of the cache and if we have, we delete the oldest item.
		this.cache.delete(this.cache.keys().next().value) // this.cache.keys().next().value returns the oldest item in the cache
	}
	
	this.cache.set(key, value) // here we now set the key with the intended value.
}

That, ladies and gentlemen, is how you implement an LRU cache. I am in the web engineering space so this was written in JS. Like I mentioned earlier though, the concepts transfer. Bye

Side note: in that put function, I think we can check if we’ve hit the maximum capacity of the cache first before checking if the cache has the key. Only drawback is that in a situation where we have and we delete the oldest item, it is futile to delete the key because we’ve already created an empty space. SO yeah, I think the order in the put function works better.