Ace This Hard Computer Science Question In Your Next Coding Interview | by Francisco Sainz | Apr, 2022

Photo by John Fornander on Unsplash

In some interviews, the interviewer will ask you to design a data structure to meet certain criteria and complete tasks with specific memory and speed constraints.

I haven’t solved this question beforehand, so we’ll be cracking it together. I’ve had this question stuck in my head for a couple of days when I suddenly had the ever-elusive AHA moment.

These types of questions are harder than regular ones, and if you have used leetcode.com before, this specific question falls in the medium category.

Not extremely hard, but by no means easy either; These questions will usually require thinking deeper and combining two or more existing data structures to complete them.

Let’s get to it.

Photo by Kelly Sikkema on Unsplash

Here it is taken straight out of leetcode.com

https://leetcode.com/problems/lru-cache/

Understanding the problem

The problem asks us to do a couple of things.

  • First, we know we need to store items as key: value pairs. If they exist, we return the value. If not, we return -1.
  • We also need to be able to insert new key-value pairs or update the value if the key already exists.
  • We know cache has a specified capacityso we must somehow keep track of the Least Recently Used (LRU) item and delete it before inserting a new one.

Making Assumptions (And Asking Questions)

We can deduce a couple of things from these statements, but in any case, we could ask the interview to confirm that we are indeed going the right way.

  1. When we add a new value or update it, we move it to the front of the list, making it the most recently used.
  2. Whenever we reach a current value, we move it to the front of the list.

Now that we have sorted that out let’s dig deeper and figure out how we can accomplish this.

Photo by Hello I’m Nik on Unsplash

Storing the data

To store data as key-value pairs, we can use a hash table.

Often called a map or dictionary in some languages. It solves our storage and retrieval problem in O(1) time or constant time.

Keeping track of the LRU Item

The real problem is figuring out how to keep track of the least recently used item in our hash table and removing it whenever we run out of space.

A follow-up question might ask you to solve both methods in constant time, which is not uncommon.

If you’re not familiar with Big O notation, it means that storing accessing and deleting the LRU item should always be executed in a constant amount of operation, no matter the input.

We know we can access items in constant time, but what data structure can we use to control the order of items?

A doublely linked list, to be exact.

Check out the article below if you’re not familiar with this data structure.

We need each node’s previous and next pointers to delete them from the list.

Searching a linked list requires O(n) operations, where n is the size of the list.

Adding and removing values ​​is as simple as modifying one or two pointers.

Photo by Mohamed Nohassi on Unsplash

Here is where the magic happens because we are using the strength of one data structure to compensate for the weakness of the other.

For Linked Lists

Linked lists aren’t great for finding values, but they are good at modifying their order if you know the location.

For Hash Tables

Hash tables are great and find values ​​fast, but they are usually unordered, and we don’t have access to modify the underlying structure.

First, create a hash table where the values ​​reference nodes in our LinkedList.

The key will be the same number, but the linked list will hold both the key and value.

Why Do We Need The Key Inside The Node?

If we want to delete the LRU value — which will be at the end of the list — we must also delete it from the hash table.

The LinkedList knows which item is the LRU, but the hash table does not.

By storing the key in the list, we know which item to delete inside the hash table.

We must perform certain operations when adding or deleting items from our list.

  1. Add an item to the front of the list (if we have space)

2. Move an existing item to the front of the list after a get() call

3. Delete the last item in the list (Least Recently Used)

Important Note: I will provide a visual representation, but since this part is more about linked lists than anything, try to solve them on your own as a challenge.

This one shouldn’t give you any trouble as it is very straightforward. However, remember to update all affected nodes!

There are three cases we need to account for here.

1. The Item Is Already At The Front Of The List

In which case, we don’t do anything.

2. The Item Is At The End Of The List

If the item is at the end of the list, we must update all nodes affected by this action.

3. The Item Is In Between Other Nodes

Here we must account for the previous node, the next node, and the head of the node.

Be careful. This one is the trickiest!

Removing the last item is easy because we only need to update the previous node to point to null.

Phew, that’s a lot to take in, but hopefully, you were able to step up to the challenge. By now, your implementation of a custom Doubly Linked List should look like this.

There are two possibilities here.

  1. The key exists, so we return the value and move the item to the front of our list.
  2. The value doesn’t exist, so we return -1;

This one is easy and should look something like this.

This one is tricky, but we have already implemented most of the heavy lifting, so it shouldn’t be a problem.

Here there are three possibilities.

  1. The key already exists, so we update the value and move it to the front of the list.
  2. The value doesn’t exist, and we still have space— we still have space, so we add the item to the front of the list and the hash.
  3. The value doesn’t exist, and we do not have space. So we also need to delete the last value from the linked list and use the key to delete it from the hash table. We can then add the new item to the front.

Here it is, all put together and importing the DLinkedList from another file.

Let’s test our data structure by adding and removing values ​​and printing the result.

If you add a console.log to the get function, you can see that when we try to call get(2)the result would be -1 because we called get(1) right before passing the capacity.

One will be the second element on the list after 5, and thus, 2 was the LRU item when we added 5, so we deleted it.

If you displayed the list, you could also see that it now displays 5 → 1 →4 →3 since 2 was the LRU and thus deleted — because capacity is 4.

If everything goes smoothly, you can now appreciate the value that data structures can bring to the table.

But even more than that, the power that combining them can give you, using the strength of one to compensate for the other’s weakness.

However, there are always tradeoffs, and in this case, we use extra space to optimize speed.

Note: The full code can be found here, but I highly recommend you to solve it while reading the article.

Leave a Comment