I've never been one for interviews. Even when I was younger - especially when I was younger - I always dreaded the idea of talking to people, being questioned and cross-examined for what seemed like hours. Then again, I knew even less when I was younger than I do now, and it's often easier to talk about things one knows than things in general. In this blog post, I'll be talking about my experience doing a spate of online coding interviews, what sort of questions they asked, and some tips for acing your own interviews. Let's dive in!
Generic applicant #133412
Even getting to the interview stage feels like quite the accomplishment. In today's software engineering market, it can often feel like we're throwing resumes and cover letters out into the void, waiting and then eventually forgetting about emails that will never arrive. I am no coding prodigy, and I am very far removed from the stories of talented engineers applying to 15 ultra-prestigious companies (FAANG? big-N? unicorns?) and getting interviews with all of them. I've come to realize, however, that while there is a certain prestige to being employed at Google or Facebook or Amazon, even getting an interview at all is a significant achievement.
Software engineers get paid well, and our skills are highly desirable across the entire market. Short of something disastrous like the internet being obliterated, or worse, WordPress becoming easy to use, software engineers will always be in demand. However, with the proliferation of bootcamps and online courses, there are millions of extremely talented and proficient coders who are all vying for the same few spots. Getting your foot in the door already puts you near the top of the pile, and is definitely something worth celebrating.
What the interview process (might) look like
A foot in the door is important, but even more important is nailing the subsequent interview. I had the opportunity to take part in two onsite interviews, and both were unique and challenging in their own ways. I want to go over one of the questions I was asked, and since for most companies you're able to choose the language you'd like to use, I'll be describing my solutions in ES6 JavaScript. The task in this instance was to create a Least-Recently-Used cache, with a statically set size, supporting just two operations: set(Key k, Value v), and get(Key k).
Before we jump into the code, let's go over what an LRU Cache is meant to be. It functions very similarly to a hashtable or Map() in JavaScript, except it has a fixed size and only stores the keys that have been used the most recently (hence the name), evicting the older keys as necessary. Depending on your coding background, you might implement this data structure using Object-Oriented Programming or not; I chose to use the OOP paradigm. Let's dive in to the skeleton of the code:
class LRUCache {
constructor(size) {
this.size = size;
// more to add here
}
set(key, value) {
// TODO
}
get(key) {
// TODO
}
}
// main
let c = new LRUCache(3);
c.set(1, 1); // => cache should look like [{1=1}, {}, {}]
c.set(2, 2); // => cache should look like [{2=2}, {1=1}, {}]
c.set(3, 3); // => cache should look like [{3=3}, {2=2}, {1=1}]
c.set(4, 4); // => cache should look like [{4=4}, {3=3}, {2=2}]
c.get(3); // => "3", cache should look like [{3=3}, {4=4}, {2=2}]
c.get(1); // => "-1" or null
Thanks to ES6, we're finally able to use intrinsic class declarations in JavaScript. Before we go into the LRUCache class, let's look at some of the other code we've set up. Right below the class, we've declared a quick test to ensure that we understand how the cache is supposed to work. How horrible it would be to spend the better part of 30 minutes coding up the class only to find out that you misunderstood it from the beginning! By writing out expected behavior like this, you get two benefits: you can double check with the interviewer that you understand the problem correctly, and you have a very simple test ready to go before you even write any application code. With that, you have my very first tip:
Tip 1: Tests before code. Talk through an example run of the program or data structure with your interviewer, and write it down. They are there to help you, and want to see you succeed. Take advantage of that, and use them as a sounding board to see if you've overlooked anything.
Now that we have our mini test example set up, let's actually consider how we're going to implement this data structure. In terms of efficiency, we're aiming for O(1) time for both operations. It is easy to see that simply getting and setting the values in a Map will take O(1) time, but what we really need to be concerned with is all the extra stuff that comes with a cache. Specifically, how are we going to evict and update the cache in constant time?
The most semantic way to do this would probably be some sort of queue. It makes sense — the first value we set is likely the first one evicted (assuming no extraneous gets), which suits a queue's FIFO structure. The only issue with this implementation is that a queue only has pointers going in one direction, so if we need to find the node before a given node, that will take O(n) time.
To remedy this, we can make one minor modification, and use a doubly linked list instead of a queue. The general idea is the same, except that you can get both previous and next pointers in a doubly linked list in O(1) time. To implement this, let's make a new class representing a node on this linked list:
class Node {
constructor(value, prev, next) {
this.value = value;
this.prev = prev;
this.next = next;
}
}
Super simple, and if you're familiar with linked lists you should recognize the general syntax: the value of the node, and the two pointers in either direction. Now that we have this, however, we need to use it. This also brings us to our second tip:
Tip 2: Complexity to code, not vice versa. If you know your data structures (and you should), you'll have a general idea of the complexities generally associated with each of them. As you get exposed to more complex code, you'll also have an intuition for what the best complexities you can obtain for a specific problem will be. Use this to your advantage — if you need to find items in O(1) time, you're going to need a hashtable. Need the minimum in constant time? Min-heap. These associations will become the building blocks of your programming.
That said, a common way of using node-based linked lists is to have a pointer pointing towards the head of the linked list, but in this case, both ends of the list are important to us. As a result, we'll be using pointers to both the head, and the tail of the linked list. Let's add those, along with our hashtable, to our cache constructor.
constructor(size) {
this.size = size;
this.map = new Map();
this.head = null;
this.tail = null;
this.stored = 0;
}
I also added a new variable called stored to help us keep track of how many keys we have stored in the cache. That way, we can avoid having to count every element in the hashtable each time. That brings us to our third tip:
Tip 3: Lose space to gain on time. Space is very, very cheap compared to processing cycles. In the correct context, a hashtable will almost always be more cost-effective than a simple array, because spending O(n) time searching for items costs significantly more than the extra space required for a hashtable. Space is almost always the cheaper alternative, so when you can, sacrifice space to get a faster algorithm.
Now that we have all our properties set up, all we have to do is implement the methods themselves. Let's start with the set() method, since we know that we'll need to set something before even considering getting anything. We know that if our cache is empty, stored === 0, and all we have to do is make a new node and set our head and tail pointers:
set(key, value) {
if (stored === 0) {
// first object that we will be storing
let node = new Node(value, null, null);
// set doubly linked list
this.head = node
this.tail = node;
// set in Map for O(1) retrieval
this.map.set(key, node);
this.stored++;
} else {
// TODO
}
}
If stored isn't 0, though, we need to check if it's a value that already exists in the cache, or one that we'll have to add. If it's the former, we're going to have to update it to be at the tail of the list (i.e. the last to be evicted). This is because of the intrinsic property of an LRU cache, where any key that is recently used needs to be moved to the back of the queue. To do that, we can simply excise it from the list and append it to the end:
else {
if (this.map.has(key)) {
// we can set key as most recently used if it's already in the cache
this.map.get(key).value = value; // update value
if (this.stored === 1) return; // if only one object
else {
if (this.map.get(key) === this.tail) return; // if already MRU
else if (this.map.get(key) === this.head) {
// special case if it is the head
this.head.prev = this.tail; // now it is circular
this.head = this.head.next;
this.head.prev = null;
this.tail = this.tail.next;
} else {
// general case
let node = this.map.get(key);
// slice node out of order
node.next.prev = node.prev;
node.prev.next = node.next;
// set node's pointers
node.next = null;
node.prev = this.tail;
// put node at tail
this.tail.next = node;
this.tail = node;
}
}
} else {
// TODO
}
}
This is a lot to take in, but it really is just verbose code. First, note that we can use the has() method of the JavaScript Map in our conditional. Then, if the key is already at the end, we don't have to do anything more. However, if it isn't at the end, we need to move it there. This is a bit easier if it is currently the head, since we can link the two together to form a circular queue. We can then simply shift the head and tail pointers, and null any other pointers that need to be null, and we're in business. On the other hand, if it is not the head, we do the more traditional operation of setting previous pointers to the previous node, and next pointers to the next node. Finally, we append it to the end and set the tail node accordingly.
If this part is a little confusing, take the time to sit with the code and understand it. Reason through it out loud. In an interview environment, talk to your interviewer about what you're trying to do, and then try to do it. This, incidentally, is my fourth tip:
Tip 4: Words can speak louder than actions. Talking is extremely important. A coding interview is a chance for the interviewer to see what you'd be like on their team, and if there's one thing that facilitates working on a team, it's communication. If you're not sure how to implement some code, but you have an idea in your head, talk it through. Your interviewer will be there to help you, and you get the bonus of being able to show them that you know how to communicate both in code and outside of it.
Now that we've got that sorted, we need to take care of the situation where we're adding a new value to the cache when there are already values there. There are two possibilities here: if there's still empty space in the cache (i.e. this.stored < this.size), and when the cache is full and we need to evict. Let's take a look at both of these:
else {
// if it's not in the cache, we have a few conditions
if (stored < this.size) {
// add to the Map freely
let node = new Node(value, null, null);
// we have at least one node in the doubly linked list
this.tail.next = node;
this.tail = node;
// set in Map for O(1) retrieval
this.map.set(key, node);
this.stored++;
} else {
// eviction time
this.head = this.head.next;
this.head.prev = null;
// set in Map for O(1) retrieval
this.map.set(key, node);
let node = new Node(value, this.tail, null);
this.tail = node;
}
}
Surprisingly, the case where we have to evict is just as short as the one where we have to add new nodes. This is because the structure of our program allows us to evict in constant time, simply removing the head and shifting all the nodes down. When we're adding new nodes to the end, we do something similar, but instead of shifting the nodes down we simply append to the end.
Now that we're through the set() method, let's take a look at the get() method. When getting a value, we obviously need to return the value, but we also need to move the key to the tail of the queue. Sound familiar? That's because it is. We can extract that logic to a function and save ourself a lot of work, which brings us to our fifth and final tip:
Tip 5: Code like you would in the real world. It's easy to say, and harder to do. However, if you usually feel comfortable extracting logic to smaller testable units — all power to you. If you don't usually do that and have a more procedural style, code that way in the interviews. You're not going to be able to fool the interviewer by coding in a neater or more understandable style than you do normally, so don't let it be a stumbling block. Code the way you normally do, and embrace your code.
I like to code by avoiding repeated logic, and extracting lots of things to functions. Here's what the logic looks like extracted to a function called setMRU(), where MRU means Most Recently Used:
setMRU(key) {
if (this.stored === 1) return; // if only one object
else {
if (this.map.get(key) === this.tail) return; // if already MRU
else if (this.map.get(key) === this.head) {
// special case if it is the head
this.head.prev = this.tail; // now it is circular
this.head = this.head.next;
this.head.prev = null;
this.tail = this.tail.next;
} else {
// general case
let node = this.map.get(key);
// slice node out of order
node.next.prev = node.prev;
node.prev.next = node.next;
// set node's pointers
node.next = null;
node.prev = this.tail;
// put node at tail
this.tail.next = node;
this.tail = node;
}
}
}
You've seen all this before, so now let's take a look at the get() method and see how simple that is now:
get(key) {
// first, set the node to MRU
setMRU(key);
return this.map.get(key).value;
}
And that's it! We've successfully coded an LRU cache, all in ES6 JavaScript, that performs super fast. Before we wrap up, a once over of the 5 tips:
Tip 1: Tests before code.
Tip 2: Complexity to code, not vice versa.
Tip 3: Lose space to gain on time.
Tip 4: Words can speak louder than actions.
Tip 5: Code like you would in the real world.
And finally, just to recap, this is the final solution we arrived at for the LRU cache problem:
class Node {
constructor(value, prev, next) {
this.value = value;
this.prev = prev;
this.next = next;
}
}
class LRUCache {
constructor(size) {
this.size = size;
this.map = new Map();
this.head = null;
this.tail = null;
this.stored = 0;
}
set(key, value) {
if (stored === 0) {
// first object that we will be storing
let node = new Node(value, null, null);
// set doubly linked list
this.head = node
this.tail = node;
// set in Map for O(1) retrieval
this.map.set(key, node);
this.stored++;
} else {
if (this.map.has(key)) {
// we can set key as most recently used if it's already in the cache
this.map.get(key).value = value; // update value
setMRU(key);
} else {
// if it's not in the cache, we have a few conditions
if (stored < this.size) {
// add to the Map freely
let node = new Node(value, null, null);
// we have at least one node in the doubly linked list
this.tail.next = node;
this.tail = node;
// set in Map for O(1) retrieval
this.map.set(key, node);
this.stored++;
} else {
// eviction time
this.head = this.head.next;
this.head.prev = null;
// set in Map for O(1) retrieval
this.map.set(key, node);
let node = new Node(value, this.tail, null);
this.tail = node;
}
}
}
}
get(key) {
// first, set the node to MRU
setMRU(key);
return this.map.get(key).value;
}
setMRU(key) {
if (this.stored === 1) return; // if only one object
else {
if (this.map.get(key) === this.tail) return; // if already MRU
else if (this.map.get(key) === this.head) {
// special case if it is the head
this.head.prev = this.tail; // now it is circular
this.head = this.head.next;
this.head.prev = null;
this.tail = this.tail.next;
} else {
// general case
let node = this.map.get(key);
// slice node out of order
node.next.prev = node.prev;
node.prev.next = node.next;
// set node's pointers
node.next = null;
node.prev = this.tail;
// put node at tail
this.tail.next = node;
this.tail = node;
}
}
}
}
// main
let c = new LRUCache(3);
c.set(1, 1); // => cache should look like [{1=1}, {}, {}]
c.set(2, 2); // => cache should look like [{2=2}, {1=1}, {}]
c.set(3, 3); // => cache should look like [{3=3}, {2=2}, {1=1}]
c.set(4, 4); // => cache should look like [{4=4}, {3=3}, {2=2}]
c.get(3); // => "3", cache should look like [{3=3}, {4=4}, {2=2}]
c.get(1); // => "-1" or null
That's all for today, folks! I hope my experience helped you out even a little, seeing what the coding interview experience was like in the era of Zoom and remote learning. Good luck out there, and be sure to take a look at the rest of my blog!
Top comments (0)