Python Interview with a FAANG engineer

Watch someone solve the max water in well problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Max water in well

Interview question

1) Write a stack class that keeps track of the minimum value in the stack. 2) Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Interview Feedback

Feedback about Adequate Gyroscope (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Nothing particular. Maybe it can be a bit faster on typing out the solutions, but I think overall the candidate did well! He was able to walk through the test cases in detail and think of the solution in a reasonable timeframe.

Feedback about Festive Tsunami (the interviewer)

Would you want to work with this person?

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

He was really nice and patient. And also explained why he conducts interview with two questions instead of one hard one.

Interview Transcript

Festive Tsunami: Hello.

Adequate Gyroscope: Hey. Can you hear me?

Festive Tsunami: Yeah, I can hear you, can hear me?

Adequate Gyroscope: Yes, I can hear you loud and clear.

Festive Tsunami: Cool. So yeah, let's start our mock interview. I'll introduce myself first. I'm a senior engineer in one of the software companies. And then they supervise the design doing my own design. And my team is basically focused on the data engineering and big data part.

Adequate Gyroscope: Nice.

Festive Tsunami: Do you want to talk?

Adequate Gyroscope: Yeah, I am a software software engineers about 12 years of experience. I have a couple of interviews lined up. I have 10 days. In 10 days, I have Amazon interview lined up for me at level three and two and level three, depending on how the interview goes. So yeah, this is my first time using interviewing.io.

Festive Tsunami: I gotcha. Sounds good. So let's jump right into the question. Which language do you use?

Adequate Gyroscope: I use Java, Python. So for interview I have chosen Python because of syntax.

Festive Tsunami: All right. So well, the first questions you just need to implement this class. In the meantime is the question clear enough?

Adequate Gyroscope: Okay, yeah, just give me a minute time going through it. So, I have to design a stack that support push up top and retrieving the minimum element in the constant time to push up top and min stack class. Manage circles, initialize it, pushes the element and removes elements from the top of the stack top of the stack the top of the element of the stack, get is the minimum element in the stack, okay. This is the class definition they have already created.

Festive Tsunami: Yeah. Okay, is it clear or do you need an example?

Adequate Gyroscope: Yeah, let's go with an example. Here I can okay.

Festive Tsunami: So, for example, if you push two and you push one, you push three then here, what do you do? When you do top, you should return three. When you do get minimum, you should return one. And then for example if I do minus 1 here, then it should return minus one. So if I pop that you should return one again, because that will be the minimum previously.

Adequate Gyroscope: Okay. All right, all right. I said okay. So, if fit was what is a normal stack, I can just use the Python list itself. So I can necessarily, I can append towards the end of the list to for the constant time append and constant time pop. The top element is also possible with lists and I can directly access the last element in the list that you can make the top part of it. So that's also constant and retrieving the minimum element and the constant time. For the retrieving for the minimum, I have to keep track off of all the elements that I have pushed in the stack what is the running minimum I know I can just have the running minimum because that example that he said the if minus one came into minus one became minimum. So, once it popped out then one will become minimum. So, I have to have the history of the minimum okay I can have maybe another list that keeps track of okay for every insertion of push and pop, what is the current minimum thing tagging So, that whenever I'm popping, so, I will pop it from the main stack, but I also I will pop it from the minimum the minimum tracking stack and that can return it in the constant time either that or I can have let's say in the stack itself I can put in a pair of values that also possibility that in the same stack I will have a pair of values rather than just one single value which is the question. So, the pair of value will end in the element being inserted and then pushed and also what is the minimum so far for stack. So, those are the ways and if I do that how... Yeah, so, that that should give me the constant time for minimum too.

Festive Tsunami: Sounds good. Do you want to start implementing?

Adequate Gyroscope: Yeah, sure. So, I have the structure of the class here thank you for that. So, this so, I need what all I need... Can you show just a stack object I do not need to have the size at the start okay. So, I need my stack in which would be a simple list I can have something so, if I am putting in something okay. So, again I put a simple simple object in it. I can also have a name that will make it slightly more readable. So, I am trying to import from collections I will improve named. So, just like logic, but I can put some names refer by name and also initialize and so it will contain this okay. Object is name and I'll just say stack object. And that would be without a value which has been pushed and also min value so far. initialization is just an empty initialization will come down to push part of it. So if I'm pushing a value in it, so I'll have push up and check which should say my rattling the well and also okay... factor plus check for that. But they're not really the first value, or does it already contain something? So... Okay, so I was coming to push later. So let's see if self top... I'm just thinking through what are the condition I have to handle. So if self dot stack, so I think if I have the stack is not empty, and my self.top minimum value you can handle. So if I if my self.stack is not empty, then I'm inserting the value and the minimum value of this value and minimum, do I have more than necessary back with a slip, okay? So, so if my stack is not complete, so I'm pushing in the current value, and I'm seeing, okay, either my current value is the minimum or the whatever the topmost I have, that will have some minimum value. So I'm paying that minimum. So this means learning from my stack object name couple up here. So what is the main computer for them.

Festive Tsunami: But then the top layer returns the integer if you see is Iine 36.

Adequate Gyroscope: Okay, right, right, right, right. Okay. Yeah, thank you. I was making mistake. So I was trying to reuse method again. So I will, just from this stack, or this list, pick up the last value. And that last value will have some minimum value. I'll compare against that. Okay. So else means that stack is empty. So in that particular case, I'll have the same thing but I won't be doing any minimum. That is stack object value, and I do not need to value has to be the minimum value. This is the only value I have. And finish when I'm doing pop. Alright, so what is the expectation if pop? If there is nothing in the stack, then pop is to throw some error.

Festive Tsunami: Just assume that we're not going to pop empty stack.

Adequate Gyroscope: Okay. If it will return nothing. So if it's already hard, so if self dot stack exists, then only I'm going to pop out of it. So I am going to have to return stack dot pop. This pop is for the last element and I only want to return the value of it.

Festive Tsunami: In this case, in this case, you don't have to because it's unknown.

Adequate Gyroscope: So I'm thinking if this stack exist?

Festive Tsunami: No, I was saying that if you look at the method signature, it's not the return value.

Adequate Gyroscope: Oh, the pop does okay. Generally pop returns the value to okay.

Festive Tsunami: Yeah, yeah, I'm just saying you don't.

Adequate Gyroscope: Yeah, I miss quite a bit nervous right now. Alright, so yeah, this is a chance now and then. So I will just see if if the second is on value and just kind of pop it out. Okay, so top playlists top returns the value so again how to check for the stack existence so my stack exists then typically case and return have last the value of the list and how to turn the value of it so I don't care and get to min would be very similar to this top except I'm going to return the minimum value out of it. Oh yeah, this man will contain for the entire stack this should work but for the top and get min in if the stack is empty... Am I supposed to return something specific venue I see on top it is not written for the edge case i'm.

Festive Tsunami: No it's fine, like assume the operation always valid.

Adequate Gyroscope: Alright. So if that is sent, then I have to lift this new...

Festive Tsunami: Do you want to test some cases make sure it actually works.

Adequate Gyroscope: So top level push. So I am going to show something two then four then 1 0 1 7. So if I do that and so my stack for to be appear so I'm going to push him to first to self esteem and first two goals in this should contain when you have to come up at a minimum should also be right. And if I push for ever wish for appear, then my stack is not empty, then I will append the value object which is the four part and take this value. I'm inserting the fourth value and I'm looking for the cells that stack the last object. Yeah, last object we will still be used to to and minimum value or those wouldn't be this second argument of the two. So, important to come in there. Witness push one more value to come in there. One I will do. So my stack is not empty when this first condition will apply again. So my value current value will cause this one and minimum value of current and that my top most value minimum setup must value minimum is two from four comma two. The second one is smaller than two so one would have been inserted was that similar. Okay, we do one more insertion, then I pop something out of it. An extra zero comes into picture. So I'm inserting zero stack is still not empty. So we're still value zero as is new and self stack the last value I had one one, and the minimum is one so minimum of one and the current value is zero is it is zero. So let's say I did some pop up and then push 3. 1. So I'm going to read this. So if I do next pop, so when my friend during the pop, so it is just removing the topmost and the proper is then this guy and then my pseudo will go away and actually I'll fire and get them into tears. So if I do try to get them in at this point. So getting might get me down. So if my stack is not empty, and I'm returning the last element of the stack and the minimum attribute of it. So last element is one and the minimum weight is one. So this should return 1x. It's not removing anything then doing pop again. So, simply remove the last element. I have not done anything talk about it. Up top, if I am exercising, so where is it, I just check for the existence of my stack, stack is not empty. So I'm taking the last element in my stack returning the value part, which is the first part of my tuple. And the last element is foreign to and first part is for the top should return for at this point. If I push it back, and it's fun. So, the minus pebble created the value of current which is minus one and compare the minimum value of current value and the last element which is four and two the second attribute of true hope. Sorry. So two n minus one, the minimum of two n minus one is minus one. So it should have done kind of for me here, and if I fire get minimum again, get minimum will get me be the last element in the stack. And give me the minimum min max a bit of this last element is minus one and a minus one. So minus one here. Do you want me to do you feel because this looks decent enough to me?

Festive Tsunami: No, that's good. So if the question change, too, is getting the element in constant time, I don't want to use extra space. Well, in this case, extra space other than the the element itself. How will you do it? So kind of So currently, you're using a space of all to two array, assuming it is the number of number of elements. Yeah, okay. So if so, if we're saying we don't want to have constant time, we just want to have space no extra space other than the element itself, how will you do it?

Adequate Gyroscope: So, I was saying that if you have a restriction that I cannot store the minimum value along with the actual value as you can see, we are storing just the value method essentially in sanitation. So I can just store the value but not all level values okay. So, back then minimum, it you have to for at any point of time to tell the what is the minimum value I need to have some kind of tracking mechanism that what is the current minimum and if the topmost goes away what. The past two minimum would be so some tracking still need to pretend we can't have constant space for that. But if you're not allowed to store that track tracking but why would it be so I say.

Festive Tsunami: You want to know what's the unit you want to know is that we're not asking constant time anymore.

Adequate Gyroscope: Oh Oh okay. So this constant time is not okay. So, if constant time is I don't have a restriction of constant time then I can further get so I can have a model stack aspect of it. So that I can have the push will just contain the value so I will lengthen to seven ad copy it for a second copy. So it should be just contain plain simple. So it will two four and minus one would have been in this stack and before the minimum value, I can do the linear scan on this because this is an array I can do one linear scan and always return the minimum value. So that could make the get a minimum will have bigger O(n) runtime because it will be linear scan of it. Is that the answer you were looking for? Do I need to optimize try and optimize it?

Festive Tsunami: No, that's great. That is right that shows simply shows that that you can use time to trade space you can use space to trade time on to make sure that you want to make sure that the concept is there. Cool. So the next question then okay. So I'll let you read first while I provide example that example.

Adequate Gyroscope: These are what I'm understanding so for the given away so this is something like there's a vertical bars the length the value of those... Yeah, the height of the array. Okay, yeah, yeah, they're gonna get you okay at this point, we have these many bar essentially.

Festive Tsunami: Okay, explain to understand why 65 like 65 generates the output 49. Do you know why this is 49? No. So he says, So essentially, you can see that is one a six to five, four, a three, seven, right. And the largest value that you can trap will be seven and eight. So the first, sorry, the second one, and the last one. So that will be the wall you choose. That one's the container. It brings in between them. They're seven, seven intervals. So it's essentially, it's multiplied. I was trying to type.

Adequate Gyroscope: Wall of length eight on left hand side wall of length seven, right hand side, and the distance is 7 between them. So the exact volume of water is seven times seven.

Festive Tsunami: Yeah. And do you know why number line or seven before is four? Like that? I should be clear, right? Like, it's like the water trap I was. I used the dart to know the that's the water trap. So you said like two and wall four. And the water they trap will be two multiplied two equals to four.

Adequate Gyroscope: Okay. Okay. So sort of walls in between, they're not taking any spaces?

Festive Tsunami: No, you can think of that there are many walls for you to choose. If you do, if you choose two walls, you can ignore all the other walls in between. So, okay, for example, even if even if there's nothing like this in between, it's not going to affect you. Tapping the water, you do select two and four. I see. Actually, yeah, but but you might not be a bad answer once there's a three because it's still going to be a bad answer. Because it's three multiply one will be three is smaller than four. So if you do this, the answer is still going to be four in this case, yes.

Adequate Gyroscope: Okay. I understood, I think, yeah.

Festive Tsunami: You, yeah. But then you can choose to choose to tread water like that. It just is not going to be the answer from other than four. Yeah, exactly. Yeah.

Adequate Gyroscope: Okay. All right. So I'm gonna play on to the, to the input example in line 65 appear. Sure. So since one is not taking any vector of its own, so they're not kind of taking the place of work. So that makes it probably a little more easier if it was taking. Okay, so I have to choose two walls and which two walls is contract most water, essentially. So if I ever do worse, I'm thinking of creating a pointer at the start and also a pointer at the end and so, okay, I am here. So if I have sorry, event, something, know that please, I have one point at a here to here at one and seven. So if I have a two pointer up here, I will calculate the area between them. So it would be the minimum of seven and one would be one times the distance between them, it will be... distance of eight, so in dense one, so it lengthens the value. So that pointer will leave me a value of eight. Okay. I'm thinking about trying to move the pointer to see something so trying to figure out what should be my condition to move my pointer. Or I can choose and move the pointer, both one first, moving just a and see if it is maximum. I mean, moving the left pointer on its own. I can just move the right one I'm getting the feeling that in this can be done in linear time. I don't have to...

Festive Tsunami: So Well, how about how about you talk about the brute force first? Okay? What's the easiest way to generate?

Adequate Gyroscope: Brute force I will exhaust all options. And so, if I have this from the start to end and then I will make a choice of... Okay, what if I move my left pointer first and see you what is the maximum volume I'm getting and then the right point to one what is the maximum getting or in fact for the brute force, I do not have to have the left hand side pointer I can scan from the left side itself like and and a square kind of solution where I have a double for loop and from first follow from start of zero to all the way to the end and other one is from zero to the i which is my first pointers and keep on scanning which has a maximum every iteration I will calculate the area and keep track of some maximum trapped value and final would be the responsibility the final maximum I found out of it that would be the big O of n squared, because it would be something like creating all the possible substring of this sub arrays of the emissary in essence square okay. So, if I take in this sorry.

Festive Tsunami: So, now, go ahead I was about to give you a hint. Okay, you can keep thinking to say about greedy approach?

Adequate Gyroscope: Greedy approach up here. So, if I put left pointer like 967, I will start with this data of the end of the array. So, I calculate the area will come out to be eight in this particular case, and then what can have, so, whichever is the smaller wall and the smaller wall will not give me the more areas to be trapped. So, in this case, one and seven out of one is the smaller wall. So, I try and have a smaller one towards towards the move the left pointer towards the right, because the left is the smaller wall calculus area in this particular area, I will have the distance has been reduced by seven and a minimum of eight and seven is seven, two. So this is the case of 49. And some this has happened to be the answer. I don't know that part here. So now I'm going to take the duty approach again. So it is bigger than seven. So make go and move the wall light wall towards in inwards, and try to find that can get me more water. So in this case, I will have just put it up here was just seven out of eight. And so it so this would be you descend to six and then meanwhile is three to six times three, it would be 18 have our gain going ahead with the theory approach I will move my right pointer in because the right wall is smaller. Now I have found an eight. So if I can eight, so my distance between them 12345. And length of height of the wall is 8 5 8 times it's 14. Now in this particular case, both are same, so this should not matter. So we'll just let's say move the left one. Good. Yep, I both had the same height, so I'm moving just anyone. So six and eight. So minimum height is six and distances for six sentinels. So I'll have 24 up here. Since six is smaller than eight, so six is the pointer which will be moved and two and eight will be... The claim exercise which would make it as whatever 123 times two is six and bad two is still smaller. So I'm gonna move forward five and eight. So, five times two, two is the distance between them sets of 10. And similarly favorites again smaller than that, move it to four and then four times one is four. And if I have, so, this is a move again, left pointer. So, if I have a point of same moving at the same place, it means I cannot hold any water because a single wall cannot hold any water. So that would be my terminal terminating condition. So and out of these values that I have generated, the maximum this value would be the my possible answer. Yeah, I think this should work. And they should work in linear time scanning barrier just once with two points, and the space complexity would be constant too, because I'm gonna be keeping a one max variable and the two pointer, the key just two variables.

Festive Tsunami: Do you want to implement it?

Adequate Gyroscope: Yes, I would like to. Okay, this is investing max area of hide analysts. So height is an array. So I will initialize my variable. So I'll have to have of course, the max water initializing it to zero need the pointer of the left pointer and right pointer left find a start at zero right pointer with end of array. So, whatever my length of an array is n minus one. So, now, I need to have a condition. So, the while left, less than right that certain point, they will be same or right and that cannot get more than that will come before that in they will get the same. So as long as left is less than that, I cannot keep evaluating the area. Okay, so I need the water content. I need the wood with a minimum of so I'm looking for the height of the wall. So height of the wall should be height of left times height of right. Back is the max, the height of the wall is and now times the distance between them set distance between them. Okay. Additionally, simply right minus left. Those are indexes. So this will give me the water content. So max water would be a max of max water and this water content. I didn't want me to track down which two walls are making it right. So that is not the part of requirement fine to learn lines. Oh. So on lines?

Festive Tsunami: Or we're just returning the, the water we're not returning that line.

Adequate Gyroscope: Okay. All right. Sure. If we had to, then I can have couple more variables and, and put the indexes over there too. Okay, my left wall is this index, that is also doable. Alright. So in this particular case, we I don't have to track that. So I'm not worried about it. So max water would be whatever my the current is what says I pasted that on value. Yeah. The current water content and whatever running max I have found so far. And once I have that, now I have to move my pointer. So how my pointer is, yeah, so I'm going by the height the greedy approach. So, if height of left less than height of light if the higher the left is less than I am going to increase left if they are same or more high to be seen it does not matter with going with the right needs to be decreased. So, right should we decrease minus one to one and yes, there will be a time when left and right will overlap each other and when you use it was so. That is it for this. So, let me see with your smaller example 1432. So, 1432 here on line eighty, okay, so, my left this left is zero, because I'm talking in terms of index. So, right is 12344 minus 334 minus one is left and water so far is an initializer sale. So, while left is less than right which is true, and then water content is the height of left times height of right. So, height of left is one height of right is two set to minus two times one is two and right minus left three minus zero. So, two times one. Sorry, I made a mistake here in this getting a minimum of these two, but I put the * sign beside myself, okay. So, to be the minimum of the two, so, which is two and right minus left is three minus zero which turns out to be times two is six. How come... I'm sorry, in the manner of the current one, not the maximum. So, two appear when appear one three times one two value, but we want some water content is one thing and that would come as max water content would become three and so and then after that left is less than right the height of left is less than right. So left will be increased to one. So now I'm calling one MP. So, so for m two So, what content value would go to minimum minimum of which is two is minimum interesting in terms of height and right minus left right is three t minus one is two two intense to an end for maximum what would the water max water would be updated because three is less than four. So, it will replace with four okay and now in terms of four and two the lesser height is the right side. So, right will be reduced by one up here and then 97 to one into and out one and two again checking the water content. So water content here would be min of the height. So min of the height is three in forum between four and three minutes that is three times right minus left. So right is to have this one, two minus one minus one which becomes three. So now max water is already included in this tree so it doesn't need to be updated. So max water two will remain four and height of left which is four is not less than height of right. So the right motivated us to more. So right will be reduced back to one on two and then one and then this one condition you have really failed. eft there same effort is not less than right. So if you turn the max value of Max water, which is four looks like after me, and oh, yeah, looks good. So, sorry. Okay, so time complexity, I was just reading with them constant time and linear, constant space and linear time.

Festive Tsunami: Yep. So this question. Yes. Cool. I think that kind of concludes this round. Do you have any questions for me?

Adequate Gyroscope: Okay, how? Yeah, I mean, so when you do take the real interviews, so this kind of testing are going to get an example that is expected in the real interview too? Or does it need to be a some kind of test cases that you do?

Festive Tsunami: Right. I will say Usually, it's not uncommon to ask you to write a test cases. Okay. But like, it's more effective for you to test your code to make sure like, discuss it. To make sure that it covers basic, basic case, or the edge case, if you want to test by it's not common for you to, it's not common to actually to say, Hey, can you write a proper Python test unit test? For me? That's not, that's not common. Unless you are, you are interviewing, unless you're interviewing for QA. You are not so? Yeah. Yeah. So test cases are not. And that's something that we really focus on.

Adequate Gyroscope: Yeah. So, like, so how do you think I do and in terms of the speed of coding, in past I've got feedback that my, okay to come up with a solution, but I'm relatively slow. So what is your opinion?

Festive Tsunami: Um, I mean, your finishing in time, I'll say decent. Okay. Yeah. I think it's cool. I don't I don't think you're particularly slow. I mean, if people are very picky about that, then yeah, maybe you can be a bit faster. But I find it alright. Yeah. If you really you want something to improve will probably. I guess you're typing maybe, because like, you know, you know, you're always in your head. But then when you try to implement it still, that you're still thinking through it? Which I think it's good, because you're cautious. Which because you're cautious about it. You're very careful. So to me, that's, that's fine. But it really depends on the interviewers taste to me, I think that's fine. Yep. I mean, I don't I don't see anything, too, concerning. In this one. Also, you're the first one solving the to two questions within a time and so I guess, I guess, I guess, kudos to you. But then. Yeah, I don't know. Maybe maybe previous previously, the candidates were not too prepared. I was. I wasn't exactly the two questions be too hard. Because I also don't like those the extremely hard that ask you to, you know, solve them within 30 minutes. I mean, some people some people do do that. Some people do it, but personally, I found that if you if I were to interview you in my real company, then I am not going to ask people leetcode hard, because that doesn't really tell me the the data point wants to get, you know, extra dough for them. And again, it It depends on the interviewer right there to me, I rather see your problem solving logic in your problem that you can solve is something that's super hard and you can't solve it. That couldn't gather any data. That's like math. So Anyway, it does depend for philosophy on the on the interview process. Yeah. Cool. All right. If you don't have any more questions, then we'll end the interview here.

Adequate Gyroscope: Thank you. Thank you for your insight and thanks for time.

Festive Tsunami: Yeah, thank you. Cool. Take care. Bye.

Adequate Gyroscope: Thank you. Bye.