# Python Interview with a Microsoft engineer #### Watch someone solve the lru cache problem in an interview with a Microsoft 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** 1) Design an LRU cache. 2) Find the longest common prefix from an array of strings. Read more about the questions - [LRU Cache](/content/questions/lru-cache/index.html) ### Interview Feedback **Feedback about Inventive Lizard (the interviewee)** - Advance this person to the next round? Yes - How were their technical skills? 3/4 - How was their problem solving ability? 4/4 - What about their communication ability? 4/4 > Focus more on data structures, and their usage. We know the hashmaps, and linked lists, and queues, but if you can nail what and how they are used, that will be awesome at your level. > I found your problem solving ability to be really good, you took the use cases, and attacked the problem with the use-cases. A very important thing when solving software design problems. This to me also shows the knack of customer focus. > Read through some of the basics of system design, like Services, APIs, rate limiting, and you will do well. **Feedback about Admiral Lambda (the interviewer)** - Would you want to work with this person? No - How excited would you be to work with them? 1/4 - How good were the questions? 2/4 - How helpful was your interviewer in guiding you to the solution(s)? 3/4 > The interviewer was very kind, patient and helpful while I was solving the questions. I think the LRU cache question was at the right difficulty level, but too frequent. I wished that I had gotten a question that I hadn't seen before. The second question was a little too easy, but good given the time that I had left. I think the interviewer could give the interviewee some more time to work through bugs on their own, but overall gave good hints and guidance. ### Interview Transcript **Admiral Lambda:** So this being a practice interview, you know, we'll still try and do it in the fashion that actual interviews happen. But I'll make it more casual so that if you need the hints or if you need more... feel more than happy to ask me questions. Just because it's a practice interview, you have more leeway. Yeah, let's start with introducing ourselves. I'll go first. And I'll give you a few minutes to let you talk about some of your recent work, any particular project that you would like to talk about, whatever interests you. And I think this is a coding style interview that you would like to do? **Inventive Lizard:** Coding style interview? **Admiral Lambda:** I mean, is this basic standard coding algorithm, data structures interview that you are practicing? Right? **Inventive Lizard:** Yes, absolutely. **Admiral Lambda:** Right. Okay. Great. So Peter, I have been in the industry for 14 years now and have worked across a few companies, working on services, APIs... used to do things in the front end before, now more of a back end guy, looked at distributed systems. And yeah, enjoy solving larger problems with more simplicity. So that's what I focus on now. Yeah. How about you? **Inventive Lizard:** Yes, so I'm a rising junior in college studying Computer Science. I took a gap year this year. So I'm going back to school in September, but over this past year, I worked as a front end intern over a physical security startup in California, and so, I sort of delved deep into front end development, and don't have much exposure to the back end or distributed systems or things like that. Although I do want to move into that field out of college. **Admiral Lambda:** Do you have a preferred language of choice that you would like to? **Inventive Lizard:** Yeah, is it Python okay? **Admiral Lambda:** Sure, I'm fine. I haven't coded much in Python, but I'm more than happy to understand what you write the code in. **Inventive Lizard:** Okay. **Admiral Lambda:** And, yeah, I'm still learning... any particular problem that you would like to solve or focus on areas of the problems like, specifically string problems, problems related to arrays, or data structures in particular? **Inventive Lizard:** Just whatever you think is okay. **Admiral Lambda:** Okay. All right. So have you heard of stocks buying and selling problem? **Inventive Lizard:** I have. Yes. **Admiral Lambda:** Okay. Then let's skip that. So you would have already practiced it. Let's go by... Do you understand what a LRU cache is? **Inventive Lizard:** Yes, I do. **Admiral Lambda:** Do you know how to code for it? **Inventive Lizard:** I can try. **Admiral Lambda:** Okay, so why don't you first tell me what's an LRU cache? I'll give you a minute. And then I'll actually put in what you need to do. So that you understand. **Inventive Lizard:** Okay, so I think a LRU cache is a least recently used cache. And so it's essentially a store of data that has a certain kind of capacity, and you're able to introduce elements and store it in that data structure. And if you look for the same value in that destruction, then it can be immediately returned. Whereas if the value is not in the in the cache, then you won't be able to find the value. **Admiral Lambda:** Right. What happens if the capacity is full? **Inventive Lizard:** Then the least recently used element is ejected, and the new element is inserted into the cache. **Admiral Lambda:** Okay, fantastic. I think you know the cache. Let's try and code for it. I'll put in the problem statement here. **Inventive Lizard:** It should be command slash. **Admiral Lambda:** Control slash. Yeah. Yeah. So what you need to do is it's basically a LRU cache. You need to implement using a data structure. And there are basically two methods that you have to implement, get and put. Get being if the key of the element is present, then you get me the value for it, and put is if the key is not present, you insert the record, and if it is already present, then you have to basically eject it, and then put it back again, so that it becomes the most recently used one. Okay. And I'll give you a few examples. For example... I had the problem in Java, but basically I'm a Java programmer who writes code in some other languages to like C or C++. So it's fine. So essentially what you need to do, so let's say if you have a cache, you put the first element: one, two. For the simplicity of this question, let's just take in that the key and values are the same. So if you say, put in a key of one, the value of push should be one. If the key is two, the value of that is two. So that's just a numeric values and keys. Okay. And at this point, if you have inserted one and two, if you retrieve the most recent one, you will get one over here on this line, and then you go ahead and put three, and then next time when you get output, get two, it should return you two and then make that as the most recently used. Okay. So, is the problem clear? **Inventive Lizard:** Yes, it is. **Admiral Lambda:** Okay. Great. Yeah, go ahead with however you want to start off with. And I'll also tell you that if we get across this problem faster, then we'll spend more time on another problem. **Inventive Lizard:** Okay. Great. So just to clarify, if the element is not in the cache, then when we try to get that element, and you should just return None?. **Admiral Lambda:** Yeah, return None, return minus one. Whatever feels good. I made it minus one just because we only deal with integers. **Inventive Lizard:** Okay. I see. Okay, yeah. So I think the general approach is you can have a hash table that points to a node. Oh, it's part of a linked list. **Admiral Lambda:** Okay. **Inventive Lizard:** And so that's what happens when we do object dot put (1, 1). **Admiral Lambda:** Okay. **Inventive Lizard:** So node one is a linked list, and you kind of put in two. First you check that the hash table is smaller than the max capacity. And I guess you put it behind this node one. I think it'd be better if we put it before node one. **Admiral Lambda:** Quick question, pardon my understanding of if this is very specific to Python, but why are you using hash table with the value being on linked list node. **Inventive Lizard:** So I think this would just store a reference to this pointer, or it'd be a pointer to this node. This one rather. **Admiral Lambda:** Let's say we are just dealing with integers and very basic, there are no objects. And we don't need to take care of the pointers or anything, it's a very simple numeric value. **Inventive Lizard:** Okay. **Admiral Lambda:** I mean, yeah. Yeah, that makes sense. So let's start from the beginning. So if we have one that we append, we add the one to the cache. And then we put two, but we're gonna have to somehow keep track of... you're gonna have to keep track of which one was least recently used. **Inventive Lizard:** What is the data structure in Python that does this? **Admiral Lambda:** A dictionary? **Inventive Lizard:** Yeah. **Admiral Lambda:** So one is the key. And this one is the value? **Inventive Lizard:** Sure. **Admiral Lambda:** I think we do need to like list to sort of, I'm thinking that we need a linked list to keep track of the order of how these were added to our dictionary. So first, it's one that's the most recent. Then we'll be adding... **Inventive Lizard:** In the order of insertion? **Admiral Lambda:** Oh, yes. Dictionary does... **Inventive Lizard:** So if it does maintain the order of insertion, then do you need any other data structure to keep track of order? Actually, I don't think that the Python dictionary keeps track of order. **Admiral Lambda:** Probably maybe... Yeah, that's a bit strange with Python is that they have... I don't know what version of Python is running right now. I can google it up... but I thought the latest one has it. **Inventive Lizard:** Let me just quickly try it then. **Admiral Lambda:** Sure. **Inventive Lizard:** Okay, we have the dictionary. **Admiral Lambda:** And if you need to Google up something. I'm okay with it. Yeah. And usually in the interviews also, people are usually okay. I mean, you can ask. **Inventive Lizard:** Okay. Yeah, it doesn't seem to store the order. It should have printed B and A first, but it printed A and B. **Admiral Lambda:** Can you try adding some more, so that I'm just saying if it maintains the reverse order? **Inventive Lizard:** Yeah, gets sorted by like alphabetically. Oh, interesting. **Admiral Lambda:** This is ACB. Okay, so there is no order. Okay. Okay, there. **Inventive Lizard:** Quickly. Can I switch you to Python3 and let's try this. **Admiral Lambda:** Sure. **Inventive Lizard:** And can you try running this one more time? Are you still there? **Admiral Lambda:** Oh, yes. Can you see what I'm doing? **Inventive Lizard:** Actually, no. **Admiral Lambda:** Oh, I'm sorry. Can you see this? **Inventive Lizard:** Yeah, you commented that out here. Okay. Okay, let's try this. **Admiral Lambda:** Okay, great. So there seems to be order. Okay. Awesome. **Inventive Lizard:** Yeah. Then if the dictionary maintains order, then I think we can put one and then put two. Which means... okay. If the two is added after the one... Okay, and then when we get one, we just simply remove it, then add it again. That was line 13. And then for line 14, we add it to the end. And then we try to get two. Then we put four. Oh, oops. **Admiral Lambda:** Yeah, that's right. **Inventive Lizard:** Right. So those that's one, two and then we got one, right? And then now we want to put three. So we simply delete the first entry and then add three, three. And then... **Admiral Lambda:** Yeah, if the capacity is two, yes. **Inventive Lizard:** Right. And then we try to get two, but it doesn't exist. So we can simply give them negative one. And then we put four, one is the least recently used. And then we get one, which is also negative one. **Admiral Lambda:** Right. **Inventive Lizard:** I think that's the general approach. **Admiral Lambda:** Right. **Inventive Lizard:** Is it okay if I begin to implement that? **Admiral Lambda:** Yes, please, go ahead with the implementation. **Inventive Lizard:** This should be a class, LRU. So this has an initializer and a put and a get. This is going to need a hash, just going to be a dictionary. This can have a given max capacity. Now, when you put the value, you want to do the length of self.cache is less than the self.max_capacity. And you're just free to append the key value to our cache. So you do self.cache at key value. Otherwise, you need to remove the first entry from our cache. So need to delete. Well, let's figure out what the first key is first. To figure out the first cache, you can do delete self cache at first key. And after deleting that first entry, you're free to add to that dictionary the key value. So if there's a successful put, should we just return true? Does it matter what we return after the put? **Admiral Lambda:** No, it doesn't matter what you return after the put. Yeah, let's just put or whatever. **Inventive Lizard:** For the get, you can simply do value is in the cache, you want to get the result. I want to get what that value actually is. This should be more appropriately named, just key. So we're going to return that result at the end. But before we do that, we have to delete self.cache at the key. Then add it again. Return result. If the key is not in self.cache, return at this point. So just to make sure that we're doing this correctly, just run through the example input again. So we create a new LRU cache with max capacity of two. And when we put in one, one, length of self.cache is zero, or, yeah, and zero is definitely less than two. So we can add in the one, one, we can also do that for two, two. At that point, we are going to have something like self.cache is going to be one, one and two, two and we try to get one. One is in the self.cache. So we get the value, delete that, and then add it again. Then we just return one. And then we put three. So we're at max capacity. So we get the first key, remove it, and then add three, three. And then we try to get a non existent two. So we just simply return negative one. And then we put four. And we return negative one when we try to get one. So I think this should work. **Admiral Lambda:** Is there a use case where this won't work? When can you see breaking your code for a use case? **Inventive Lizard:** So okay, let's go through this. It'd be function by function. For the put, for each, as long as the length of self.cache is less than the max capacity, we add it to our cache. Otherwise, we... So let's say at line number 12. I change this to say this. Yeah. So then we would enter this condition. This else. **Admiral Lambda:** Why? **Inventive Lizard:** Rather, we would enter this, because length is one so far. **Admiral Lambda:** Yeah. What would happen if you try and put the same key value again in the dictionary? **Inventive Lizard:** Right. Would it update the least... Would it update the most recently used? **Admiral Lambda:** So you said it will? **Inventive Lizard:** It would not update the most recently used. So to explain. If we had a one, one, and hypothetically, we had a three three in there, and we put in another one, one, then this should actually move this up to the front. But it doesn't do that right now. I think. **Admiral Lambda:** Yeah, that's correct. That's true. If you increase the capacity, you would have done that use case. But in this case, if the capacity is just two, and you don't have this, it's basically there is just one element in it. And your capacity is still less than the max capacity, and you will try that again. So it would it should actually eject this and inserted back in again, so that it becomes the most recently used one. Okay, so what you're saying is that we need to take care of that. So there is a missing step. Let's go one time more. You have one and two. And at line number 13, you would retrieve one and finish with an end right? right? so at line number 13 you would get one and put it back again in the top, which would mean interchange line 22 and 23. Right. Now on line 14, you would put three back three in, because you still have capacity. So you will put three. Right? Yeah, now come to line 15, you have to put one and one. Can you put one and one, because you still... now you have in the else condition, else block. So going by the code, you will retrieve and insert a duplicate. **Inventive Lizard:** So we would need to add another conditional if key in self.cache... And then you can add it to the cache. **Admiral Lambda:** Right. And that is for the case when it is within the capacity. And if it is, let's see... if it hits the capacity. In that case, you still retrieve the first key and delete the first key and then put it back, which you will still have the duplicates. So what you're doing in the if condition should also be done in the else condition. Right? So let's go one time more. You have one and two. And at line number 13, you would retrieve one and finish with an end right? Right? So at line number 13 you would get one and put it back again in the top, which would mean interchange line 22 and 23. Right? Now on line 14, you would put three back three in, because you still have capacity. So you will put three. Right? Yeah, now come to line 15, you have to put one and one. Can you put one and one, because you still... now you have in the else condition, else block. So going by the code, you will retrieve and insert a duplicate. **Admiral Lambda:** So now, when you try to put one, you will not be able to because the capacity will get filled up again. **Inventive Lizard:** Yes, I see. So add that additional condition inside for the put method, along with logic. **Admiral Lambda:** Okay, so now let's just run through the use case one more time with the code change that you made. When we put in zero of the cache, we will add one, and now add two. Then we will put in three, correct? **Inventive Lizard:** Right, right, let’s see. **Admiral Lambda:** And then what happens with duplicate one, what happens to the maximum capacity? **Inventive Lizard:** Properly iterate, flush out duplicates before inserting with the duplicates in place and ensures the values stay correct in the cache. **Admiral Lambda:** And release a new design end now tests work correctly. ## Conclusion - Write clear and maintainable code. Capture the necessary conditions and cases. - Aim to iron out redundancy and avoid duplicates while inserting items into the cache. - Create functionality that outputs expected values on each test to solidify understanding of cache mechanics.