Design an LRU Cache
Read more about the questions
Feedback about Special Chameleon (the interviewee)
Advance this person to the next round?
How were their technical skills?
How was their problem solving ability?
What about their communication ability?
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?
How excited would you be to work with them?
How good were the questions?
How helpful was your interviewer in guiding you to the solution(s)?
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.
Fearsome Sandwhich: Hello. Special Chameleon: Hello. How are you this morning? Or whatever time zone you happen to be in. Fearsome Sandwhich: 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? Fearsome Sandwhich: This will be my first one. Special Chameleon: Ok good, it's been my first one with
codepointor any of these other interactive things before? Fearsome Sandwhich: 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(n log n)or whatever. The better analogy is have you ever hard of a cardiac stress test? Fearsome Sandwhich: 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. Fearsome Sandwhich: 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. Fearsome Sandwhich: 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. Fearsome Sandwhich: 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
nullbecause two is ejected. That's where you get to decide whether it returns
nullor 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. Fearsome Sandwhich: 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. Fearsome Sandwhich: 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. Fearsome Sandwhich: 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. Fearsome Sandwhich: 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. Fearsome Sandwhich: 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." Fearsome Sandwhich: 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. Fearsome Sandwhich: 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? Fearsome Sandwhich: 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. Fearsome Sandwhich: Oh okay, this guy... Special Chameleon: You can leave that there, because you... but just the last three lines. Fearsome Sandwhich: 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
setTimeout()maybe? Special Chameleon: Oh gosh, well all right yeah asynchronous things. Ah let's that make our lives miserable. Fearsome Sandwhich: 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. Fearsome Sandwhich: 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_accessedoldest key. If we want to see if it's less than... Special Chameleon: Yeah they're smaller as they get older... Fearsome Sandwhich: 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. Fearsome Sandwhich: Okay let me... maybe I should... actually since I'm accessing each key already, let's just