JavaScript Interview with a Pivotal Labs engineer

Watch someone solve the lru cache problem in an interview with a Pivotal Labs engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

LRU Cache

Interview question

Design an LRU Cache

Interview Feedback

Feedback about Special Chameleon (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

3/4

I encourage testing during screenings because it gives rapid visual feedback about code outcomes, but console.logs are fine as well. code that expresses intent is easier to read. kudos on naming things!

Feedback about Fearsome Sandwich (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

I greatly appreciated how he explained the problem. The suggestions and guidance he gave throughout the interview were helpful without giving too much away. He wasn't always the most comfortable with my chosen language, but that is more to do with how interviewing.io matches people up than anything specific about him.

Interview Transcript

Special Chameleonh: Hello.

Special Chameleon: Hello. How are you this morning? Or whatever time zone you happen to be in.

Special Chameleonh: It is this morning, yes. I'm doing ok.

Special Chameleon: Ok so my name is Ken and um you can be anonymous or whatever. How many of these have you done?

Special Chameleonh: This will be my first one.

Special Chameleon: Ok good, it's been my first one with interviewing.io, I've done a bunch of coding technical interviews, but this is the first time I'm actually working with this thing.

Special Chameleonh: So we'll muddle through it together.

Special Chameleon: Yes, it should be reasonable practice. You can use the language of your choice, my language of choice is Ruby, but don't let that muddle you, I'm fluent with almost everything.

Special Chameleonh: Okay, I will probably use JavaScript.

Special Chameleon: Alright then. Alright so, I'm going to paste... let's get started... I'm going to paste in this thing, you've probably seen it a thousand times before. And let me change the language for you. Cool, I don't have you use codepen or codepoint or any of these other interactive things before?

Special Chameleonh: I've used a couple, yeah, of these little online IDEs.

Special Chameleon: So alright, so uh there's no rush, but let me tell you what my expectations are while you're reading. This is not a a trivia test, I am NOT looking to see whether you know the difference between O(log) and O(n log n) or whatever. The better analogy is have you ever hard of a cardiac stress test?

Special Chameleonh: Um I don't think I have actually.

Special Chameleon: Okay well, let's say that your doctor thinks... mmm let's see if your heart's okay and one of the best ways to do it is to put you on a treadmill wire you up to some electrodes maybe put a mask over your face to measure your air volume and then start slow and watch how your things go. Now a really bad thing would be is they actually triggered a heart attack while you're doing the stress test. That is not my goal okay. My goal is quit once you feel comfortable. It is kind of by by using a bunch of different probe points that I've got it on my checklist over here on the side that you can't see is you know where your comfort range is and in your technical limits. So there are no right or wrong answers and I am much more interested in hearing how you solve problems than actually solving the problem, but that being said, have fun with the problem. Go wherever you want to go, I will try to keep you out of the weeds if you get stuck and so that you don't get frustrated, and I will also try to help you where I can, but like don't worry about whether this stuff is performance or not. What I want to see is solve the problem first. I'm a TDD agile type of person, so the first rule is to make it work and then make it right and then that gets asked. So we can talk about this stuff, it depends on how fast you get through this, what the levels of stuff that we can talk about but this is your chance to show off you know your chops and I'm going to try to put you through your paces as best I can without causing a heart attack.

Special Chameleonh: Okay. Okay so yeah I'm actually not familiar with this problem, I have not gotten it yet so let me just read through it here first. So your task should you choose to accept it is to implement a LRU cache. LRU caches are often used to implement caches which you do not want to grow indefinitely.

Special Chameleon: So LRU... I'm going to fix this for you. So this is a least recently used cache okay. So the idea here is that you've got a bunch of stuff in a bag, but the bag has a limited capacity and then when you put something new in, you want to evict the oldest thing from the cache so that the the most recent stuff is always in the cache and stuff that's gotten old has fallen out of it.

Special Chameleonh: Okay, so it sounds kind of like a queue type of, you know first-in first-out type.

Special Chameleon: True, yes, but um but it's random access.

Special Chameleonh: Okay so the cache has a max size when the new key isn't there that would make larger than the max size, the key which has not been accessed for the longest time is removed to make space, so it should support these operations: get key, get the value of the key if it exists in the cache, put key, update, or insert the value if the key is not already present. When cache reaches its capacity, it should invalidate the least recently used item before inserting a new one. Okay so what happens if you call get key on a key which doesn't exist in the cache is up to you to define. Okay so these are the operations down here. So we have a cache, a new LRU cache with a capacity of two. We'll put one into... okay so these are the keys and the values, okay.

Special Chameleon: So this shows you what I'm highlighting right? Okay yeah, so that's the key and that's the value. This is a great tool for performance improvements, like web things right, where you get a page... your browser gets the page and then and then it gets another page and gets another page and then somewhere along line it says you know you haven't looked at this page in like a week, you're probably not going to look at it again. I'm just going to throw it out of the cache to make room for the next web page that you need and vice versa. So that's why it says get one is the key get two. Get one is going to get what the value was which in this case was the string one. These values and types don't really matter. So here on line 23 which says put three right, it's going to put a new value into the cache but there's only room for two slots because of the capacity two. So it says, all right well we're going to get rid of this one because get refreshed the the recency of that particular key. So one gets to stay a bit longer, two gets kicked out. So here it says returns null because two is ejected. That's where you get to decide whether it returns null or an exception or something else, that's up to you, what you want to do there and again so here, right, this is the fourth key goes in, so one gets kicked out. Now one's gone, now you get three get four and so in the cache at the end are keys three and four.

Special Chameleonh: Okay. Okay so I'm going to be creating a new class called LRU cache a so I'm going to start with that first. You cache and it will have a capacity property, so it will need a constructor. Then we'll need put and get methods to it. So each method will need, they'll need a key and a value.

Special Chameleon: Hmm no the get only needs a key.

Special Chameleonh: Yes you're right.

Special Chameleon: I'm also here to be your wingman. I'll try to keep you from falling on the ground.

Special Chameleonh: Making ill mistakes, yeah.

Special Chameleon: Yeah I'll catch you on the typos and stuff because you know, you're not really being you know scored on grammar.

Special Chameleonh: Yeah, so I need a capacity. We also need some place to store these keys and values so, we need our actual like cache and I think... so I also need somewhere to put to record when something was last accessed. I'm wondering...

Special Chameleon: Yeah okay go ahead, but what I was going to suggest is that if we simplify the problem at first, will that help with the design choices? What if we said that this was an unlimited cache, that it basically you know it's a dictionary right but stuff and you get stuff out right and would that make your at least your initial design choices easier? And it leaves some time for testing.

Special Chameleonh: Yeah so if it was an unlimited cache, I would probably just go with... I mean you just need an object to store the keys and the values.

Special Chameleon: Yeah exactly. I'm big on testing and getting feedback from my code, so one of the things that I kind of like to see is "hey does this stuff really work" as you're going along and what little things can we put into the interpreter to say, "alright hey it works, doesn't work, doesn't work as expected."

Special Chameleonh: Okay so let's see... so if it was an unlimited cache, then we could just in this class just have the cache object and input would just add in so this cache, the key equals the value. And we want to return...

Special Chameleon: Yeah it's undefined what put returns.

Special Chameleonh: Okay so the big important parts just that, so get we want to make sure we return this stuff cache key.

Special Chameleon: Yeah, okay can we see it work in real life?

Special Chameleonh: Yeah so right now we have cache... and if we do cache put one, one, and then cache get one, it should return us one. And now cache is not defined because I need to declare it.

Special Chameleon: Yeah um... or if you just take that code that you've written and copy and paste it over to the right hand side, that's the interpreter.

Special Chameleonh: Oh okay, this guy...

Special Chameleon: You can leave that there, because you... but just the last three lines.

Special Chameleonh: Oh okay okay. Let's just console.log() to see if it just gives us what we want. Run... yay... we got our one. We can put in and we can get items from the cache and so now we need to check and see if the cache is at or over capacity, well should never go over capacity, so we need a conditional to check if the cache is at capacity. So just a quick check here to make sure that this logic is working, so cache put two, and we've got our cache get one there and let's do console.log() cache put three... even more parentheses there. Okay so we got one and we got the we are at capacity. Okay so when we are at capacity, then we need to throw away the least recently used item and that's... so we need to record the last time that everything was accessed. I'm wondering if that should be like a separate object that has the keys and the values of date last accessed or if there's a way to do that within the cache object?

Special Chameleon: Um either way works for me. In terms of implementation, I'm easy.

Special Chameleonh: Okay, so yeah my first instinct is go with a little object here, this last accessed and so it would do this last accessed key equals and I think it's like new date, I believe that's the current time in JavaScript. Let's uh kind of yeah... okay so that's new date and so that will give us our... actually let's just make sure that this last accessed... Let's run that and see if that gives us the object we're looking for... okay. So those are... yeah are those times subtly different, hard to tell with this...

Special Chameleon: Yeah it's going to be tough...

Special Chameleonh: Like milliseconds difference or something.

Special Chameleon: Yes okay that's an you know an interesting design question, right? What if what if this thing is being pulled so fast that even millisecond granularity is not enough, or does it matter right? The trouble with does it matter is that it makes your testing uncertain.

Special Chameleonh: So we do need to on the get we need to update that last access so...

Special Chameleon: Yes, yes we do.

Special Chameleonh: That should subtly change the times a little bit maybe... yeah...

Special Chameleon: Can we put a sleep? Does sleep actually work?

Special Chameleonh: Ah we could like setTimeout() maybe?

Special Chameleon: Oh gosh, well all right yeah asynchronous things. Ah let's that make our lives miserable.

Special Chameleonh: Okay, I think... I think it'll still eject the right ones here so... okay so we have our table of last accessed. We now need to go through that table and find the one that is the the oldest state and I'm sure there's more elegant ways to do this but just brute forcing it, my first instinct would just be to loop through all the keys and just compare dates.

Special Chameleon: Like I said, I'm not looking for elegance at this level. Let's get something that works and comes back with reliable results. And then if we have time, we can talk about refactoring and optimizing and other things, but yeah.

Special Chameleonh: Oh cool, yeah so we'll do this ugly and it will hopefully work. So start undefined and we'll have some logic in there about a field this key doesn't exist and we'll just see that's the key. Alright so if this last accessed... ok this ternary is going to become kind of a pain... so let's just do an if statement just because... so if oldest key... will do some logic there... else all my tabs are screwed up, oldest key equals key, and fix that because I like pretty code. Okay so if oldest key exists, then we want to compare all oldest key this.last_accessed oldest key. If we want to see if it's less than...

Special Chameleon: Yeah they're smaller as they get older...

Special Chameleonh: So less than the last access key, then we will stick with the oldest key. So at the end of all that, here let's get rid of these guys we don't need them anymore... So at the end of all of that, we should have console.log() oldest key, which should be one in this case. So let's run that and see what we get.

Special Chameleon: No.. so we are not getting the right key here.

Special Chameleonh: Okay let me... maybe I should... actually since I'm accessing each key already, let's just console.log() this last access key, just to see what those times are.

Special Chameleon: It might help me and it might help you if you put some labels in on those console logs as well. My my memory stack is only about 3 plus 5 plus or minus 2, so um I know what these values are, but I can't remember which console log statement is here and here.

Special Chameleonh: Sure sure, okay so let's see here. We got our yeah... actually for the get, instead of just returning I'm going to console log the value at key. Key is just cached...

Special Chameleon: That works now? Whoa I learned something new today.

Special Chameleonh: Yes, template literals are my friend. Okay yes, all right um, so that is let's see here... so let's add some labels to this one. The time key was last accessed was this next accessed key and I need to turn that into a backtick. Okay and the oldest key is... but not really...

Special Chameleon: Or not yet.

Special Chameleonh: Yeah, okay. So I think, yeah the issue is that because this is all happening synchronously...

Special Chameleon: Actually, I think that's the right answer.

Special Chameleonh: Oh yeah no that is the right answer because we accessed one. If we took this guy out, then it still doesn't work.

Special Chameleon: Instead of putting it out, change it from... oops what did I just do? I was undoing my thing. Uh yeah try replacing get one with get two and see if you get a different.

Special Chameleonh: Get two. Okay so now, the oldest key should be one by far and it is not.

Special Chameleon: Okay so maybe date or time stamps is not a fine enough granularity for this task. You need to come up with some other data structure or algorithm for for solving it. So let's see, this is the first... so last accessed...

Special Chameleonh: Let me try to... okay I'm going to make a suggestion, um just to... maybe this will help maybe this won't, if it doesn't help just tell me about it. All right okay, so the the getting of cache keys, you got working just fine. And we have sort of something, and it looks sort of like a method or some kind of API for recording the last, although right now we're doing date. It's this algorithm that's causing pain. Can we just take that whole algorithm out and make a brand new method which just says this is the key that you need to evict before you do the next put? That might... One way you can fix it, you can start test-driving just that small piece of the code and leave the rest of it alone and it also might help with data structures if you can separate it out into something. It may actually turn out to be harder, but my instinct says let's figure out what... let's create a different function to figure out what's the key that we should evict next.

Special Chameleon: Okay so yeah, we want kind of an evict method and...

Special Chameleonh: It doesn't actually have to do the eviction right, it just has to say this is the one to do and then we can write separate code that just deletes the key. So that's to just make it even simpler right, that the only thing this method tells you which one's the oldest.

Special Chameleon: Okay so this is actually find least used. Yeah okay. Okay so what we want to do is if the object keys length equals this capacity then we will want to use this find least used key and that will return back and it should return back the least used key. So that doesn't actually, I don't think that actually needs to take any arguments because it's going to just go through the cache and so all of this in here will be part of that. Let's say you finally use key, so let's just toss this in there for a moment and then least used key is least used key. Okay and let's just for the moment just return this will be the least used key just to make sure that that's running correctly.

Special Chameleonh: Yeah okay.

Special Chameleon: All right, so now we've got to figure out least used key here.

Special Chameleonh: So you actually started down this path at the very beginning, which was this was going to be a some kind of queue.

Special Chameleon: Okay, yes. So if we have a queue, we have so queue could actually be an array. So if we turn this guy into an array, then our foot would be... so we have an array of keys and we put we could push the key into the array. Now if the key already exists and we're updating it, then that might be...

Special Chameleonh: Right so there's a little magic involved. Yeah I mean I like the path you're going. Okay so look for the key in that last accessed array. If it exists, then push it to the... pull it out of wherever it is and put it back to the beginning.

Special Chameleon: Yeah so that's yeah it's probably not the most performative but we'll start there for now... okay so first off simple was simple thing is let's assume the key does not exist so this cache key equals high...

Special Chameleonh: Your um okay I see what you mean. Okay I thought I you were working on your algorithm. I was trying to save you from editing the wrong block of code, but nope you are correct and I will shut up now.

Special Chameleon: Okay. Let's see here. So we could actually and I can probably put all this logic of whether to push it to the end of the array or sort through it into a method itself but so let's see here what would I... let's call that... update use or something...

Special Chameleonh: Naming things is one of the hard things in computer science.

Special Chameleon: Okay. There, that is a complete sentence. Okay so um... this lacks access... so the simple case is it just pushes to the end and so this would be... so that just pushes everything to the end. Now what we need to do is... this is so... so if equals negative one then we do that we push it to the end otherwise we need to remove it from the array and then push it to the end and let's see if I can remember my splice. So we have position and amount. Okay so we want...

Special Chameleonh: I'm going to just type over here in the console because I'm curious.

Special Chameleon: Okay. Let's see here. Okay.

Special Chameleonh: We can actually like experiment with that right? Just just to isolate on that update access time function to make sure that it's doing the right thing for us. Instead of running all the other bits and bobs, you can just focus on that one function for a little bit.

Special Chameleon: Yeah so if we... forgot the value here... if I just comment that out for a moment and comment that out. So that's put, that updates the access time and do I have any more consoles in here? Got this guy here. Let's just return true for a moment, just getting you simple. Alright, so this should just show us the state of the last accessed array throughout these lines of code. So it's currently one, two. The last access array is currently one, two and... okay so if we do that then one should end up on the end of the array, currently two, one.

Special Chameleonh: Okay sweet.

Special Chameleon: Now why aren't you doing something here. Let's see... Is it because your console.log?

Special Chameleonh: Yes, because put doesn't actually have any return values. And put...

Special Chameleon: But it should be doing... should be running this guy one more time.

Special Chameleonh: Unless it's this thing is not...

Special Chameleon: Yes because it's at capacity. Okay, so when we get to capacity, we need to find the least used and this guy is actually pretty easy now because he's essentially just return this last accessed 0. If I'm not mistaken.

Special Chameleonh: Mmm-hmm. You might want to just shift it off while you're doing it.

Special Chameleon: Sorry, shift it off?

Special Chameleonh: This push, pop, shift, and unshift and I always forget... so let's decide. So left hand side 0th element in the array is the most recent and, yes so your oldest is going to be the end of the array. So if you use shift...

Special Chameleon: So I think... so I want to... Okay, yeah that removes that. So I think we've taken care of all the removing. Now we just need to... just basically repeat this, which means essentially all I really need to do is just not put an else here.

Special Chameleonh: So how do you evict that old value from the cache.

Special Chameleon: Oh yes, so okay... so we need to... so we need to remove keys from the thing, so I think...

Special Chameleonh: You won't do that in the put, but yes.

Special Chameleon: Okay yeah find least used, so at least used key is here. So we want to yes... gets to delete this cache key. Lets console.log... the cache is now this cache. Let's run this and see what happens. Oh of course, it's an object. But if we do... let's see... let's see what that does and cache get three. Okay let's see, I think we got that guy figured out and this is not actually useful. So we have the last accessed array... so right now get if it doesn't find something... so this update access time key...

Special Chameleonh: Why is this getting one three two?

Special Chameleon: So if it's at capacity and we find the least used...

Special Chameleonh: Is delete actually doing what we think it's doing?

Special Chameleon: Well the array doesn't seem to be shifting. Why aren't you working... Let's see here. So this last accessed... So find least used, let's make that just... all it does is just return the thing, we'll shift it afterwards. So last accessed array is this and then we will do things to that, so this just returns this.last_accessed(0) and I'll just run this real quick. Okay so last accessed array is one two three one... why is this not even running? Oh oh I didn't console out my least used key. Okay. Least used key is two, that is correct and so this last access shift is 1,3 so yeah that is not... let's see... I thought that was right...

Special Chameleonh: Yeah I tested that over here.

Special Chameleon: So let's see, why are you not... so if this cache key...

Special Chameleonh: So you've got rid of the else here, I think that may have been what's confusing stuff. Because you delete it and then you add it right back in again.

Special Chameleon: Wait, oh this cache least used key. I think that's yeah, I was deleting the wrong key.

Special Chameleonh: Hey, there you go, sweet.

Special Chameleon: Alrighty, so that is... so we are putting, we are getting, when we reach capacity, we find the least use key and we remove it. Let's see, are there any other cases we need to make sure we take care of here?

Special Chameleonh: Um there probably are, um but we're running low on time and I want to stop here because we're a good stopping point.

Special Chameleon: Okay.

Special Chameleonh: So how's it feel?

Special Chameleon: Um so, that was uh less intimidating than I feared. It was... I appreciate being able to just work through it pretty much line by line and figure out, you know, how to build this thing up first with no capacity and then adding in the capacity and... yeah so I feel pretty good about it?

Special Chameleonh: Okay, so I'm looking at my notes and actually... so without rewriting anything, because we're kind of pressed for time, but now... if we had a test suite, which would be like the next thing that we would work on, so that you could just run tests and say hey it's still working, and I'm just going to do this in pseudocode right? So now, if we had a test suite and this actually worked right, we could run it and then every time we make a change, now we could say all right, all our code still works, which would would help in the refactoring part. But now let's assume that the test always works that you don't break anything because you're a perfect coder. Where would you attack some refactoring choice. Let's look, at you know, once you just kind of look at the code and say hmm where are some places where I could refactor this to make the code more expressive, fewer lines of code means fewer bugs, that sort of thing. You've been banging away at this for 45 minutes with your head down and so I'm trying to get you to relax, take a breath, and kind of look at the code from a more global perspective.

Special Chameleon: Um I would probably like the put area could probably use some refactoring. So we've got... because the find least used is so simple now it may not actually even be necessary, we're just grabbing the zero index of the last accessed array.

Special Chameleonh: So yeah because this is all you know one action and and shift in itself is destructive. So you could shift the value off, find it, and delete it all in one line.

Special Chameleon: That's right, yes, because shift returns... the value or the key? It returns the, it's an array, so yeah returns the value.

Special Chameleonh: Yeah so you could do this and then.

Special Chameleon: Finally some used is pretty much redundant at this point, it's not used.

Special Chameleonh: Nice thing about this is that this is almost an atomic action now, it finds it, pops the thing off, it shifts the thing off the queue, and deletes it all at once so there's no... it reads as this all happens at once, right? And it's easier to read. And I like that you got rid of the else, I don't like else's. They make my brain hurt.

Special Chameleon: Yeah, it was nice to just see, yeah we're doing the same thing regardless at the end, whether it's at capacity or not. There's a design pattern where you're adding functionality to a class, so one interesting way to to refactor this is to start with an infinite cache as a class right? And then, and I don't know how to do inheritance very well in...

Special Chameleonh: Yeah superclass LRU cache extends cache or something like that.

Special Chameleon: Yeah exactly. And then you could just put, you could extend the functionality to do the evictions as you move along. Also, I mean, this was super easy and I just... great these are the same, right? So you can take them out of the if and just kind of go. And then whatever..

Special Chameleonh: So essentially, the if does not equal...

Special Chameleon: Yup, super simple. Easy.

Special Chameleonh: I think we still need a push after 67 right?

Special Chameleon: Oh yeah, because I got rid of it. Whatever, sorta done. Cool. Um have you done much testing in JavaScript?

Special Chameleonh: I've done, yeah server-side testing. Node using mocha. I've done some reactants on testing as well. I'm always curious about... like I said from for me and Ruby testing is sort of part of the DNA, that I can load testing into the same editor as everything else and start running it. Testing and setting up in JavaScript always still gives me pain.

Special Chameleon: Yeah I don't think there's going to be any kind of... like I don't know if this particular interview setup has an integrated tester or not.

Special Chameleonh: It actually does.

Special Chameleon: It does, oh?

Special Chameleonh: It has chai and mocha, although I... oh there it is. That's how you. Cool all right learn something new every day. Yeah, that is I would say a personal preference, that I try to drive testing first and I know that I'm fighting City Hall on that.

Special Chameleon: I like testing first when I'm making end points on the server at least, so I definitely want to be using testing first more in my code. Yeah just because it lets me know if I'm screwing up.

Special Chameleonh: Yeah exactly. Um okay, time is up. Any questions or comments for me? Especially since this is the first time I've ever done this, I actually don't know what to do next.

Special Chameleon: Yeah, I guess we just end the interview down there. How's as far as like the flow of this interview, how does this compared to other interviews you've conducted, as far as like working through the problem?

Special Chameleonh: I think it worked well. You seemed a little shaky out of the gate, um which is, you know, expected. But about 15 minutes in you started to hit your stride on this stuff. And I was impressed by the way you started solving the problems, especially since when you started facing the fact that it wasn't working, right, and you kept working at it. And my only comment is to make the outputs from your whatever you're doing, whether you're going to do testing or console logs, make them more expressive about intent. If you're not going to do testing, then put console logs in and say I expect it to be this, so because when I started looking at it and when you got to about four or five lines, I started losing track of is it right is it working I don't know I think it is it sort of feels right and you know I had to go ahead and scratch my head a little bit. And if in your expression of the code that you're doing you say, this is what it should be doing or this is the output I expect compared with the output again, even if you're not testing, then there's a very concrete way for the interviewer to say yeah okay you're doing it right and okay um, then at least one of the other things is that the interview can't say well no you're doing it wrong, you say I got the right answer. He says you may not agree with the way I did it, but no yeah. So yeah uh and you used your outside voice all the time um which was great because what we're trying to see how you think. That is the number one high order bit for all these screenings, is to see how you attack problems, not whether you get the problem right or not.

Special Chameleon: Okay.

Special Chameleonh: Well thank you, it's been a pleasure.

Special Chameleon: Alright, thank you very much yeah.

Special Chameleonh: Good luck with your job search.

Special Chameleon: Thank you. Bye.

Special Chameleonh: Bye.