interviewing.io

Netflix Mock Interview (Java)

Watch someone solve the recover binary search tree problem in an interview with a Netflix engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Recover binary search tree

Interview question

Given a binary search tree with two flipped values, recover the BST without altering its structure

Read more about the questions

Interview Feedback

Feedback about Sterling Daemon (the interviewee)

Advance this person to the next round?
Thumbs up
How were their technical skills?
3/4
How was their problem solving ability?
3/4
What about their communication ability?
3/4
1. Try to avoid recursion and stack if possible (talk about pros and cons during interview), like in this case could have been possible. 2. Try to think out aloud if possible, larger moments of silence during the interviews is not good. Since its telephonic a periodic ping might be good for the communication between you and interviewer.

Feedback about Hot Broccoli (the interviewer)

Would you want to work with this person?
Thumbs up
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
Great interview and interviewer. Sometimes I didn't understand the interviewer's pronunciation but it could be my listening skills.

Interview Transcript

Hot Broccoli: Hi, are you able to hear me? Sterling Daemon: Yes, hi. Hot Broccoli: Great. So sorry I think I'm a minute late. So let me just lay the outline of how the interview would go. So I will give you a brief interaction about myself. I would like to hear about what you are up to nowadays and then we'll jump into the coding question. We will reserve approximately 45 minutes for you know, for the coding question. And beyond that we can go through the feedback. If you have any feedback for me, I'm open to hearing that. So that's how we would go through this session and as I talk with you I'll also be taking some notes so that I can you know consolidate my feedback at the end of the interview. So that's it, any questions on the process? Sterling Daemon: Yeah I think I'm clear. Hot Broccoli: Oh great. So okay so I'll give you a brief introduction about myself. And yeah of course I heard about audio issues on this platform. I haven't run into any so far, but if you are not able to hear me out just let me know you know if you want me to repeat something or clarify something just let me know. Great so I'll give you a brief interaction about myself. I have been in the software industry for 10 plus years. I have been working on as a back-end engineer primarily throughout and focusing on Java and related technologies. And at present I am working for a media company. So yeah so that's about me, why don't you you know tell me something about yourself. Sterling Daemon: Yeah absolutely. So I'm I'm a recent graduate, I graduated like last December from Carnegie Mellon University and I'm currently looking for full-time software engineers. Is particularly and back-end development and I also use Java a lot. So yeah so you mentioned you are working on the Java back end technologies. So I'm telling you you're using like Java servlets and the pre-spring framework right? Hot Broccoli: Not exactly Java servlets because spring generally abstracts out a bunch of things for you, so so yeah its spring and related technology. So things are evolved and I think spring is gaining a lot of you know focus so it's spring and then you'll have some back end. You'll have probably hibernate to integrate with the back end to optimize on the database front and then you know if there's a real time streaming requirement you would integrate with Kafka or something like that. And then you know you'll have some kind of jobs which are doing a kind of back-end processing which will optimize your real time lookups right? That's the typical model that you will find no matter where you go in the backend world, right? But yeah yeah, that's about it. Sterling Daemon: Yeah unless some interesting. And yeah and I'm since I am a new grad I don't have any working experience so that's very hard to for me to find a job. And recently I've been like practicing like solving coding problems and also learning full stack development on my own, hope that helps. Hot Broccoli: Yeah definitely, so I would suggest like since you keep yourself open to full stack because I have seen that kind of trend especially in the startups. So they are looking for full stack developers typically you know when you are starting up. But in case of bigger companies it's a different scene. They have the clear distinction between a front-end engineer, back-end engineer etc. So I think as a new person keep yourself open to learning the full stack and then you know, go along with how your career takes you basically. But yeah that would be my two cents. Sterling Daemon: Yeah yeah thank you for that. Hot Broccoli: Yeah sure sure sure definitely. So yeah, any other questions before we start? Sterling Daemon: Yeah I think we can start. Hot Broccoli: Perfect okay so are you familiar with this Coderpad kind of environment, like are you doing this for the first time? Sterling Daemon: I think I'm familiar with okay, I've used Codepad.io, I think if you're... Hot Broccoli: Okay yeah, it's comparable to that. So do you want to select your programming language of choice. Sterling Daemon: Yeah I will select Java here. Hot Broccoli: Perfect and then you can run it and then it should run. Yeah that's it. So yeah so now let let me copy the code the question over here. I'll be pasting it in on line five. Sterling Daemon: Okay. Hot Broccoli: So you're given a binary search tree. Are you familiar with binary search tree? Sterling Daemon: Yes I am. Hot Broccoli: Okay, so two of the elements in the binary search tree are swapped by mistake. So I want you to write a method which would take in a binary search tree and it would recover the tree without changing its structure. Sterling Daemon: Okay so is there any duplicating the binary search tree? Hot Broccoli: Oh for starters let's assume that there isn't any. Sterling Daemon: Okay okay so some elements are swapped and it's a balanced search tree, so the left child must be less than the root of their parents and the right child must be greater than the parent. Would you mind giving me a few minutes to like sketch something on my paper to think this through? Hot Broccoli: Absolutely yes. Sterling Daemon: Thank you thank you. Hot Broccoli: Sure. Sterling Daemon: Okay. I think for this simple two examples of... This is one example for this simple example. I think of what I can get... well I can think of immediately is that comparing like when we can like traverse like for example preorder traversal and and look if any one is like out of order. Like for example if any like node violates the variant property, like for example here 3 is the left child of 1 straight left child of one and the left child should be less than the parent but here 3 is greater than the parent so we know that there's something wrong here so we can just swap them. That becomes the answer 3 1 2, but this is trivial, I mean this example is trivial. Maybe something happened deep in the tree how for example maybe for example it the trees might... Hot Broccoli: I'll paste a tree for you if you don't mind. This is what we say for example right? Sterling Daemon: Ok yeah um yeah like here, we can say that 2 is less than 4 that is correct. But 2 is actually one of the nodes in the right subtree of 3. So for binary search trees, all the nodes in the right subtree of a node should be greater than that if we don't have duplicates. So here 2 is less than that. We know something wrong with 2. We should swap 2 with 3, so to do this in algorithms, I think we can probably maintain a lower bound the upper bound. In the very beginning that lower bound is minus infinity and the upper bound is plus infinity. And we go left, which means let just do it here. We go left. This is left. If we go left then we are the upper bound because the left subtrees, all the nodes should be less than the root, so so our upper bound is 3. Okay and oh there is a typo. And if we go right, uh the lower bound upper bound should be 3 and plus infinity right? And while we are updating our lower bound and upper bound, we're also checking if the if the variant property is maintained. Like here 1 is less than 3, 4 is less than 3 is maintained. And also check if the nodes are within the bounds. So1 is within minus infinity and 3, it's correct. 4 is within3 and plus infinity is correct. And here one is the leaf node, so we stop there. So we go from 4 and we only have the left child, so left... So we update our upper bound so now the range should be 3 and 4. Yeah so that's lower bound and upper bound and we check 0 is less than 4 so the variant property is maintained. However two is now within this bound that means something is wrong with 2. So we kind of like lock like this node here and probably for a simple algorithm we want to like do it again. Like so 2 is out of bounds and 2 is less than this bound, so one way I can think of is to make 2 as the new lower bound. I mean because 2 is less than the whole range so we can make to the new lower bound and 4 as like the original upper bound so um... So 3 should be here this way, so should look for the node 3 and swap it with this 2. Hot Broccoli: Okay so are you maintaining a left and right for each node in this case? Sterling Daemon: Maintaining a left and right? Hot Broccoli: A left bound and right bound for each node in this case? Sterling Daemon: Yes right. Hot Broccoli: Okay so what will be the time complexity of this? Sterling Daemon: For this one since we are visiting like every node I think it's O(n). Hot Broccoli: Okay and how about the space complexity? Sterling Daemon: Things we are creating that this lower bound, upper bound for every node, I think it's also O(n). Hot Broccoli: Okay okay okay, um... Okay so can you think of something that where you don't need the space? Sterling Daemon: I don't need this all O(n) space. Well I think we can make this range global or like instance variable so that it's always that reference right, it's always that range, the same range. It's just it's changing every time we visit a new node. So it's always like O(1) because we just have two elements and everyone is using the same range, it's just the values of the range changes every time we visit the new node. So in that case I think the space complexity will be O(log n) where the heights, I'm sorry because sometimes the tree may be unbalanced, so the space complexity is the recursion depth of our algorithm so yeah, so with that we can reduce the space complexity to O(H). Hot Broccoli: Ok, so why don't we get started with the solution and then we can go over the other details later. Sterling Daemon: Yeah well I'm not sure if this algorithm is correct because I haven't fully proved it, I just feel like it maybe it works. Is it still ok to write the code now? Hot Broccoli: Well I don't know, why do you think it might not work? So in case you maintain a left and right bound per node, why do you think it might not work still? Sterling Daemon: Mmm I don't know, I just have that gut feeling. But I think this should work right? Because if this is the out of the range, we just check if less than the range where a more than square of the range and we like replace the corresponding bound and swap that bound with this node. So let me implement this algorithm and see if it works. So let me delete these things here and let's assume we already have this node data structure and has left and right pointer reference. And we should call this method maybe recoveredBST() and we're giving a root node. Okay and we maintain a range at the global instance variable which is the int[] range = {Integer.MIN_VALUE, Integer.MAX_VALUE} as lower bound and as the upper bound. Okay so if root is null, just return. Okay otherwise.. if(root == null) return. Then we go to our helper because we need to also maintain the parent reference here. So go to our helper with our parent as log, in this case, and our root is our root from our private void helper... Load current and load current... Okay so okay so when you check if this maintaining the invariant property, so if P is not long... Then we need to check if this current node is the is the left child or the right child of P. So if it's the left child you see is the P. Uh okay so here we're accessing its member, so probably see if it is null so we need to exit if C is null. Yeah and so if this is the case, we need to swap these two nodes. I'm just calling it swap function here. Actually we don't have to do with... So um we can do a temp. Wow we can just... So we just swap it... How can we swap. Can you give me a minute to like to draw a tree, I'm kind of confused here. We're missing a parents' parents' reference right? Because if we lose our current node up, we need to kind of like make the parents' parents' like a child reference pointing to the current reference, so I'm missing that. So let me just write a function that can handle that. I can focus on this later. So C and P and we should implement this and what can we return here. We can return boolean, that means we have already recovered the tree, so we don't have to go any deeper. So if it's the left child and if the current value is less than the current value, then we can swap C and P again. It's the same here. Okay if now the the invariant properties maintained and we check if the current node is within the is within the bounds, you actually let me just put the C.val and the P.val, we just pass by value P.val to this one because we can just use the integer like a integer to to find a node to make it simple. Here let me check if it's within the bound. If it's not within. If C.val is less than the lower bounds range zero then we can just swap that val with the lower bound and return true if C.val is greater than the upper bound, then we replace the upper bound which our current value. Okay and uh so after all these are done, we know the property is maintained and it's within the range, so the problem is not here and we should go deeper, so we can check both the right and left child. Here we just return true maybe, return false because it's not stopped here. Um okay we can go to the right and left. But before go to right we need to like change the range. Let me to change it to... if we go right, we need to update the upper bound so we need to maintain the old, so we to update back because it's like instance variable, it has a state, it's not stateless. So in this it's the same as range zero range one and when it updates our range... update our range to range[1] = current.val and we can do this now. So the parent now is C and the child node is c.left. If we have fix here, we can return true without going to the right, but otherwise we need to change it back to the original... Okay and we can... Now if we go right with we should update our lower bounds, so we should make range[0] our current.val. Okay and and we can do our rights or if our right is right, our right should be... helper so the parent node again is C and the child is C.right and before we return we need to we need to make it when you update it back to its original range, so range[0] is made back to its original range and we can simply return here. Okay yeah so there we're done with this helper method. We can go ahead and implement our swap method. So if we want to swap them... Hot Broccoli: This is done recursively right, basically? Sterling Daemon: Yeah we probably want to find both of their parents right. We want to find their parents and we want to know which node is actually deeper, like I don't know like... Node 1 is here and node 2 is somewhere here and node 1 has a parent maybe like this. Node 2 is down here so we should... Can I just update the value without like rearranging the references, is that okay? Or I have to like rearrange the reference, make P.right equals or I can just change and that val to be like... If I do this, I actually don't have to find the parents references, I can just modify the values and that's much simpler if that's okay. Hot Broccoli: I think I've done both of them. Sterling Daemon: Okay so first of all you... Hot Broccoli: Read the question, I say recode the tree without changing its structure. So I don't expect the structure to change, so maintaining the value should be fine basically. Sterling Daemon: Yeah good. So changing the value... First of all we need to find these two node. Let me get node... Yeah we we need a root as well because we need a root. Let me just put our roots as a global variable for simplicity. So this is much simpler, otherwise I have to pass root to these methods. Okay so so we can find load one and load two. Okay I think this works mmm... Yeah and we need to do the same for every for every v2, you just make a function or make a method here called find node given the value. Okay yeah I think I'm done with this. Hot Broccoli: Okay let's test it out. Sterling Daemon: Okay let's test with the last example shall we? Yeah so my root is three and we called this recovered BST method passing three here, and three is not allowed so we don't return and roots is three. Hot Broccoli: You mind writing a tree and then building a tree and then passing the root so that we can run and see? Sterling Daemon: Okay cool yeah sure let me just write the class private static class node. We have left and right and we have val. We can do a constructor with val and make our value equal to... So we can build our tree in the method root build tree. Okay then we can shall we do it in order like, in order prints. Okay and after I build this tree we have a solution object and we recover our BST with root.Let me just print in order first without recovering it. Shall we run it? Hot Broccoli: Yeah we run with it. Sterling Daemon: Oh line 149 what is it? Maybe the matching of the braces? Hot Broccoli: Yeah probably that is the reason. Oh yeah there's one more parenthesis required, I just added. That happens. Sterling Daemon: Um yeah let me run again. 114 missing some missing some return statement, what am I missing here? Oh it should be here actually. I should delete this. Okay... null pointer exception 134. Our swap is null pointer. So our final actually return a null. For this example we should swap 2 & 3. So let me print what we're finding here.Yeah we're finding three and three. Yeah that's that should be correct, why is it... and three. Okay now three is the root so we just return the root. Two is now the root. Oh right, because it's because it's not the right structure because that's what we need to do so we shouldn't depend on the invariant property to find a node, so yeah so we shouldn't do that. So instead of doing that I'm going to make the range of two nodes actually, two nodes instead of two integer value, so we can just... So when we meet the problem, we can just swap it right there. Okay uh with this we go to our helper method... where is our helper method? Yeah so instead of swap, we just we just changed the value of 2 nodes, we just do C and P and our swap here is just two nodes. Okay yeah I think we can run it now. Yeah then we can fix this specific tree. Not sure if we can fix other trees, but this one we can fix. Hot Broccoli: Okay so what will be the time complexity of this now? Sterling Daemon: Now the time complexity is still O(n) because we have to, you know worst case, we have to visit every node. Hot Broccoli: And how about the space complexity? Sterling Daemon: It's still O(height) because we don't have extra memory. We have constant extra memory. Hot Broccoli: So O(height). Okay why won't it be O(n)? Because your node in question would have a stack entry isn't that right? Sterling Daemon: Yeah that's the stack space so yeah we're not getting other collections so yeah some memory comes from the recursion. Hot Broccoli: How much of memory would be there on the stack, the total convention on stack? Sterling Daemon: Um how much memory... how much memory should be on the stack, what do you mean by that? Do you mean the limit, the upper cap or? Hot Broccoli: Sorry so how much of stack memory usage would be there in this code? Sterling Daemon: In this code I think it's O(height). I mean we're creating these two node, this node this old nodes here, but it it comes with every every helper and when we reach the leaf and return, we actually pop that stack and this node is also gone, so I mean in the same time at maximum. So there are like the heights of many nodes here. Hot Broccoli: Okay okay yeah got it yeah so uh okay I think, I think we have used the time to make a working solution, so that's good. So that's it about the coding round. So let's move out of it. We can run a few more tests cases probably, but we can do that later. But I think this is this is fine. Okay so coming out of this question, so how did you feel about the question? Sterling Daemon: What what what I'm sorry? Hot Broccoli: What did you feel about the question? So what was your thought process? Was it an easy one, was it a hard one? Or what was there some tricky thing? What was your thinking of the question? Sterling Daemon: I think the difficulty level is medium, it's not very easy because sometimes you know you cannot know the answer immediately, you have to like experiment and it's easy to ignore the upper bound, lower bound and just just look at the invariant property, so I would say it's medium. Yeah medium difficult. Hot Broccoli: Okay, got it okay, great. And before I share my thoughts on the on your round, do you have any feedback for me? Sterling Daemon: Feedback for you as an interviewer? Hot Broccoli: In general like the way the interview went and could have been more clear in some aspects. If you don't have at the top of your head, that's fine you can always document it later and send across, but I just wanted to know. Sterling Daemon: Oh well I think I think you're pretty good as the interviewer and give me the sample input and sample output, so yeah so I don't really think that that's... But I'm wondering when I have come up with this solution did you know it was correct or it was wrong? Or you didn't know either? Hot Broccoli: No, so all I wanted to see was how does it impact the space complexity. So from my side that because, initially if you remember you started with having a bound stored at each node, right? And then that would have added a bit a fair bit of complexity right? Now because you are using stack... Okay I'll come to my feedback right. So your solution is optimal in terms of if you remove the stack aspect of the solution it seems to be optimal. Okay there are different ways to solve this problem. But because of the stack if you see it there's also a extra load of creating the stack, putting all the local variables into it, then after offloading the stack right? So that's the additional work the CPU has to do. Now of course the CPUs are very powerful right now, but if you think of a very large binary search tree right, where in just two numbers are swapped right, so this may or may not work in that case. I mean because of the amount of storage that could go into the stack at that point in time. So there are many different way as I mentioned. So one of the ways as you yourself printed as in order tree right? So the simplistic solution could happen like you do in order traversal, you find out the two values which are out of place, and you just swap that. I'm happy that the code work because as an interviewer what I'm looking at at the end of the interview and what most of the interviews look in a technical telephonic screen is you should have a running code, right? It should run against input because that is very important. Even if it is suboptimal, if you have a thorough understanding of what are the pain points in your code and you have working code, you know what your time complexity and space complexities, and even if you have a slight hint of the way to optimize it, I think people would be pretty happy, or at least give you another opportunity by putting into a second round of telephonic screen, right? But that is very important I feel so because we are not talking face-to-face right, so I don't know like what you're up to over there so at the end of the thing if you have something running actually that gives me confident that okay. And you are debug something you know while you are running it and then that gives me confidence that okay you have gone through that process, you have some code that is running right now right? So this is good. Overall so if it were to me, I think I would it would be a leaning yes for me in the sense that if there was a prior interview which was also a leaning yes, then that is a good thing for you. But if you may have been selected for another round of telephonic screen or called onsite right? So that would have been my state if I were to speak with you. Of course there is there is a missing component in my interview which is like going through your projects and seeing what kind of exposure you have in terms of technical skills. So that's that's the part I would have tested on a few Java skills, data structures etcetera, which you know it's another part of this mock interview, but expect that from the interviewers too. So it would have been that that whole thing together would have consolidated my feedback in your case. But I think this is a decent working solution I think so and it is good that you could you know do it from end to end in terms of writing the inputs writing the test cases and then executing it right, so that's a good thing that came out of this interview. Sterling Daemon: Okay okay thank you so much, so if I... go ahead I'm sorry. Hot Broccoli: Yeah I'm done, you were saying? Sterling Daemon: Okay I was just wondering if you were interviewing me for real, would you pass me for the onsite or the next round? Hot Broccoli: Yeah so that's what I mentioned, so there is a small piece of your project work and because I don't have it. It's a anonymous interview right? So I don't go through that part. But I would have spent some time on it and based on that and this coding itself I would have decided, but if it were to just limit to this coding I think I would pass you. Sterling Daemon: And how is my communication skills, did I speak clearly? Did you understand me? Hot Broccoli: Right so coming to that part, so that's another point that I noted. I think you have to be a little more vocal of your thought process. There is a moment of silence that goes through intermediately, which is fine like you have already communicated to me that give me two minutes I'm thinking about it etcetera. But especially during the technical phone screen side, it's better to just do a ping in between, like talk out a loud what your thought process is because we don't know what you are up to over there right? If it is a face-to-face interview, then that moment of silence is fine because you are in front of me and I know that you are thinking on something right? But it's always good to not have a prolonged moment of silence when you are thinking. Sterling Daemon: So even if I'm like thinking and drawing something on my paper, I should like say my thoughts? Hot Broccoli: I'm not saying about the running commentary of your work but you can at least, you know, in between say that okay these are the aspects. I'm just thinking about the left bound, how will I do or you know something of that sort. So that at least I know that okay this is the way you are you're focusing on, this is the direction which are focusing. Or I'm thinking about recursion for example. I didn't know that you are going to go the recursion route until I saw it in the code say for example here. Though I'm sure you would have thought about it at some point in time etc. So these are some of the trivial things basically. Sterling Daemon: Okay I see yes yeah those are very valuable things, thank you. Hot Broccoli: Sure. Great ah well that's it from my side. I will also document a couple... I spoke couple of points in terms of feedback so I will document that and I'll submit and if you don't have any other questions, then we can end the interview or feel free to ask so if you have. Sterling Daemon: Yeah can I ask you maybe just the one last question before you go? Hot Broccoli: Yeah sure. Sterling Daemon: So so so did you actually prepare just this one question or did you actually have a follow-up for another question after this one for this interview? Hot Broccoli: Well I would have optimized basically because I don't like using stacks because of the thing on the stack aspect because that has a bunch of its own problems as I mentioned that there are various simplistic approaches to write. So I would allow to discuss on the pros and cons of those approaches versus the approach that you suggested, right? So in case of say having in order traversal and then swapping two values, your time-space complexity would have been O(n) because you would you would create that array right basically of n elements and then you would swap right? So there are certain discussion that I could have done but that's like a add-on bonus but again that's what I would say the 20% of it is. 80% of it is the code and the 20% of it comprises of the optimizations and your project experiences your know-how of the technology. So all those discussion comprise of this 20% for me at least. I am not sure about the other interviewers but certain interviewers, they just come and they'll give you two problems. Just solve it and that's it. So if you run both the things you are done. So you know things that people do in today's job market. Sterling Daemon: Okay okay I see. Hot Broccoli: I may not even talk. I think I spoke a little bit during that. We had a good interaction throughout the interview, but do not expect that with everyone. Some other interviews keep - I mean keep quite basically throughout the interview. So you may not get too much of insights or anything which is fine I mean, but that's their interviewing style. So but keep in mind about that - like it can be a one-sided one wherein they're just expecting you to write the code and run it so some other stuff especially yeah. Sterling Daemon: Yeah I see I see. Hot Broccoli: Great so that's that's all. Sterling Daemon: mm-hmm okay. Hot Broccoli: Do you have any other questions? Sterling Daemon: Sorry what's that? Hot Broccoli: Did you have any other questions? Sterling Daemon: Did I I'm sorry I didn't catch it. Hot Broccoli: Did you have any other questions? Sterling Daemon: Oh no no thank you so much for you know yeah. Hot Broccoli: Yeah definitely so good luck with your preparations yeah. Sterling Daemon: Thank you thank you so much. Hot Broccoli: Yeah, have a good day, bye. Sterling Daemon: You too, bye.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.