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

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.

Here it is taken straight out of leetcode.com

## 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.

## 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.

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

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.