C++ Interview with a FAANG engineer

Watch someone solve the target sum 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

Target Sum

Interview question

1) Given a BST, return the nodes that are visible only from the right side. 2) Given an array of values and a target value, does there exist a series of subsets of the array such that the sum of all values in the subset equals to the target.

Interview Feedback

Feedback about Aerodynamic Hobbit (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?

3/4

Good job solving the problems. Not too much feedback since you managed to solve both problems.

Feedback about Chaotic Llama (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

3/4

How good were the questions?

4/4

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

4/4

1/4

Interview Transcript

Chaotic Llama: Hello. Can you hear me?

Aerodynamic Hobbit : Yes, I can hear you now. Can you hear me?

Chaotic Llama: Yes. Okay. Thanks. How are you?

Aerodynamic Hobbit : Good? How are you?

Chaotic Llama: Yeah, great. Thanks. Yeah. So I guess to start with, do you want to tell me a little bit about yourself, your experience, and how long you've been doing the interview prep?

Aerodynamic Hobbit : Yeah, I have around like 10 plus years of software development experience, mostly on the server side programming. And I have been preparing from like, last six months, and I have an on site scheduled from Facebook on in next week.

Chaotic Llama: Oh, awesome. Yeah, I have my, my first phone screen with them in two weeks. Yeah, so I guess to start with, I'll give you a problem. And if you've seen the problem before, then I can give you a different one. But this question will be good, because I think Facebook tends to ask a similar question. So I will, I'll put it here in the comment down here. So you're given the root of a binary tree, and you're standing on the right side of the tree, return all all of the nodes that you can see order from top to bottom. Have you seen this question before?

Aerodynamic Hobbit : Not exactly. So, with our root of moving yourself standing in the right side of the node and the values of the nodes, we can see order from top to bottom. Okay. So, I'm imagining that this tree has at least one node like this root. And the right side view means like, we this binary tree has different levels. And for each level basically we are saying that we have to pick the rightmost node, right? So that will be like the right side view. So for example, if we say like clear something 123456. So, basically, as I said, we will be 136 and we have to return from the order from top to bottom okay. So, one thing that comes to mind that we can do like the first your creation and like level by level, we iterate over the tree and being the last element of the last element of that that level and add it into the result array that we have to return. The only thing... So, then, there may be like depth first search solution as well, but since breadth first search and depth first search in this both case will be like linear complexity, time complexity. So, and from a space point of view also since we will be maintaining a queue here. And in the depth first search space, complexity will be again, in the worst case linear. So we can pick either on the solution like breadth first search or depth first search. So basically, I will be using BFS and then do level traversal was the approach that I'm trying to mention here and then not the last element.

Chaotic Llama: Yeah, I think that's fine.

Aerodynamic Hobbit : All right. And we don't have we can use like tree node kind of structure here something like the syntax of this C++. So normally we'll be having like a value and there will be like two pointers pointing to the left and right node. And we are not going to create the tree I think we'll get a pointer to the root as the input of the function right?

Chaotic Llama: Yes.

Aerodynamic Hobbit : So, we can see. So, we have to return values of a node. So, we are going to return an array basically. So I can say some function name as input we are getting this root node. In the worst case scenario, if it's either a null is just returned empty. Otherwise, what we will do is that we are going to maintain a few here we will start with the root node first will be the result array that we are going to create while we are traversing the tree and during the creation queue should be non empty. Once the queue is empty, that means we have completed the whole traversal of the tree. Then create basically or the area and before doing that I will. So one what I will do is that I will when I am iterating over the queue at each level, basically whatever is the size of the queue, I will take the last element of the queue and insert into the array before we iterate over the list. So that we are making sure that we have the exact element that we need here. So we can say in this case like the tail the last element of the queue here, which will be willing to take the value of it and then agree to. So initially, we had the root only so we inserted the roots values and then create the array. Right so we'll then take the key we'll take the first element, which will be like the leftmost element and this time they start on the level traversal and we will say that if we find a left node, then we'll push it into the queue here. So, if we see the end result you are going to push only when we are starting the level drivers and since we are sure that we are going to get into last but just for the testing purpose, if these check your like it is 123456 case. So when we starting then queue has the element one in the start and result we are pushing as one here so. The size of the queue is one of the time we take out the first node, and we see that we have like two and three as the left and right child here. So queue has the element two and three, two is at the front three is at the back. And second time when we come into the while loop, we see the size of node is two and in the result basically we were number three, which is the back of the queue, the last element and so, when we are iterating over the node two, which has like for example, four and five as left and right child and three has only suppose for example on the left node not the right node. So, six is the left node on the three. So, what happens here that queue becomes first straightforward and funds which came from node two here and when we are creating over three then there is no left node, but there is a sorry there is no right node but there is a left node as value is six. So queue will become six here, 456 so when we come for the part later on the travelers then in there is basically pushing the value six this way, there isn't as one through six. So in the edge case, suppose for example, only two there's only one node as four. So right side, we still is like, should we be doing it for and we'll make that will happen like when we are at node two and sizes one we will be inserting one of the node for queue in the end will be only four and the result will change to four here. So in that way, we are making sure that if there is any element as this thing, at least one then also we are inserting it into this. Okay. Does that sound okay?

Chaotic Llama: Yeah, I think that makes sense.

Aerodynamic Hobbit : And the time complexity is linear. Since we are iterating over each node only once and space complexities. Maximum in this case will be the label number of nodes at any level. And if this is like a full binary tree completely, so like height h tree has like 2^4 edge nodes in the last level.

Chaotic Llama: Sure. Yeah, that sounds right. Yeah, if you want to go ahead, do you can come up with like a test case and test it.

Aerodynamic Hobbit : So this was the one test case that I was looking like 123456. And other tests can be like, the are using that to run code or?

Chaotic Llama: Yeah. Do you want to do you want to try and run it to see if it works because I'm not. I normally do Python so we can try it out.

Aerodynamic Hobbit : I actually have to create the tree for it. Suppose we have one there.

Chaotic Llama: So if you want I can give you the full definition of the tree node from leetcode.

Aerodynamic Hobbit : Yeah, so it's working. So like for one node, we got the only one here. Then it's like since I have to generate the test case manually, so I will have to create the nodes, you know, understand the left and right pointers. Like, yeah. So this is the case in which like a root node one has the child two and three, for example. So I will create left node two, and node three. Oh, yeah, one increase per day. Similar writing it should work.

Chaotic Llama: Yeah, I think that makes sense. And the solution seems to be working. We still have plenty of time. If you want I can give you another problem.

Aerodynamic Hobbit : Yes.

Chaotic Llama: Same thing here. Let me know if you've seen it. So in the bottom, can post it here. So you're given an integer array of numbers. And an integer k, you have to return if it's possible to divide the array into k non empty subsets whose sums are all equivalent.

Aerodynamic Hobbit : So for each sub segment have the sum. Same sum basically. K non empty subsets. Yeah. And subsequently, you'll hear like the contiguous sub arrays, right? Yes, not the sub sequence, okay. So for example, in this case, k equal to four and there's so that we can divide somehow, like...

Chaotic Llama: You would have to create four subsets from num and those sums are all equal to each other.

Aerodynamic Hobbit : Like can't see like which subarray but perhaps it is true like.

Chaotic Llama: Yeah. So, you will have these subarrays here.

Aerodynamic Hobbit : Four subarrays we have to find in which you will have 51423 and 230. So, oh so, it's non empty subsets basically like so, this is a set and all like if we get the power set of this set, then we have to pick the subsets and and we are able to have like 23232 times because there is like three existing two times here.

Chaotic Llama: Yes, and also two existing two times So, you can utilize each number once.

Aerodynamic Hobbit : Okay, so it's not a contiguous subarray is like a subset actually. We can take like, because even though they are not contiguous, yes, right, I understand that. Like, all to raise the power of n subsearch that can exist for this set, we have to figure out with subsets have the thing some. Okay. So brute force method, I think there will be generating all the subsets first, and then, you know, iterate over all the subsets and check the sum. So, but it's like, generating all the powers, and generating all the subsets is like, why, like, it's a huge, like a space, or mysteries point of view, or even it's like a huge, going to be a huge array if n is large. Yeah, so I don't think that that would be good a scheme to generating like, and this means that we like lot waste of resources just to generate first, somehow, we have to figure it out. Like what I'm thinking is that since we have to have k equals of some sort first thing the sum of the whole array like one like the accumulated sum, and then divide by K, so that we will know like, what is our target sum that we are looking for, right? And if we are not able to divide it by k, then we can limit the return immediately false since it's not possible, right? And I hope that k is not zero, right? And it's a valid number, right? k should not be greater than more greater than number of size of the numbers array right. Or, or if it is, like we can we'll just return false anyways, like if, if I'm not able to divide the sum of this number, a number by k by k with remainder zero that means like, I can't divide this into K, because some set so that will be like first check that first initial check basically.

Chaotic Llama: Yeah, you can assume that k will be less than or equal to the length of nums.

Aerodynamic Hobbit : Okay, so what I'm thinking like again with sum of the sum of the numbers divided by the k, the remainder, remainder is not zero so written for time so this like initial check says we can't do I think a call subsets and then... Yeah element four here then then try to pick try to pick k minus one elements. So, since every subset has to have k elements, so, if we pick first one and we have to pick like k minus one remaining as many subsets and if we are able to form like one of the k one of the subsets having to elements those elements will not appear into the any other subset right since we are going to divide it into k. So, from there we can think of like we have some sort of some sort of more some sort of marking that we can make on each element whether we have already used it or not kind of today will kind of prune our search for the elements. So, we are not doing to check for those elements which we have already formed with the sum the sum total divided by k. So, somehow I'm thinking about having a check array okay. So, I will mark as used. So, there is a like a total sum the sum of nums area which is like a total and target is targets for each subset is your total sum divided by k, right? Yeah. So and sum targets. So, once we are able to find one of the subset which has so much targets, all the elements we use in the subset will mark it as a used element, so we're not going to visit them perhaps. Then this problem is like kind of depth first search kind of like I start with the one element as start index for example. So, start with index zero. And look for what elements can be used to the target sum or it so when the next time when we are iterating over it like suppose for example for the fall we found the one as the sum is five. So when I am for example in the one to recreate I'm not going to iterate over it since I marked it as a used element. But I will start with the three I will consider like other elements. So good case will need three comma two here. So those indexes are not use. And then when I meant three, and yeah, so when I my three, basically, and I'm trying to explore, I will not use five, but I will consider two as an element. And since three and two will make us five, I will say that, that is the sum. And four is like, meeting with number one here to make the sound. So, when we reach here, like the end, we are have consumed all of the elements. So, this is what I'm thinking like, it's a kind of recursive function, which will keep on looking into the elements and try to form the sub some recipes. And does that okay.

Chaotic Llama: Yeah, that makes sense. I think that's a good starting point.

Aerodynamic Hobbit : Yeah, there may be some roadblocks here, which I haven't considered, but there seems to be like a starting layout that I can work with. Okay. So, and we have you ever been bold here and you can give names of key importance here and key right. So, first thing is that we get a total sum that I was talking about here, we can use a steal function library function accumulate, which will give me mistakes basically the start and end accurate for the array and start adding some starting currency. That will be like that total sum. Now, here, I'm going to check if so, here, I will just make an edge case here this table to zero because that is a disaster case, I don't want to divide by zero in any way. So, I will just say false. And this is our target some kind of bar that will be divided by k. And here I will say that the total sum percentage K. So remainder if it is not 0 and if it is not, if it does not and then that is not zero. That means we are going to return false since since there is no way that we can divide it into k equals k subs some subsets. Okay, this these are like error checks here then yeah, then we can have like a mark then I was talking about like, which element has been visited or not the size of this and then we can see the road and then it unfolds perhaps there's nothing to check. Okay, and the size is Initially, the whole marker is false for all of the elements. And then I have to use the recursive function basically. So I will just say something like, let me figure out the signature of the recursive function logic might be. So I'm going to found the recursive function after iteration I'm going to return as a Boolean element here. So first element is certainly the number itself. Then the second element is this mark. Marks which will keep on changing over the duration of the recursion. Then there will be like some sort of starting index. With tools like from where we are they started being for each recursive point. And then they will be like, okay, here is the song that we are k on this target some doesn't make any sense actually, since k is a target. So this time it is not the target so much. This is like, how many of subsets are going to be there? Right? For non subsets kind of. Yeah. And and yeah, we'll have to find the current sum. So, when we are doing because if not we'll have to keep forming this current sum and how many of them we have used? I guess. Yeah, how many of the current sum and how many numbers are used here that's going down and down to target to do this on device. Yeah, this is IDE sorry, P is like key concepts read. So, this is the target I'm sorry I got confused. This is actually that we got confused. So, this is the target from that. So, k is the number of subsets and divided by total sum is like, total sum over k will be the target. So, this is like a target. So, here, we have a number of very marks already starting index that will start from case then the more subsets got and some is like for each subset, I will track how long is the current value of the sum and how many number of elements I have used going through and, and the target sum that I should look for. So, this seems like a starting signature, I will keep changing here some of them might not be used. So, this is a kind of recursive call also. If we say that this case will be like if current some we reach to the target that means we have got a subset and we'll say that the current number of elements should be greater than zero as well. So here, we'll just say that you found one of the one of the subsets and this time then we have found one other subset we can return true from here on because we have to find other substances also understand.

Chaotic Llama: What does curr num represent?

Aerodynamic Hobbit : It represents like how many numbers are involved into this particular subset. Later, one of the groupsets only. So like for example, one comma four in this case current num first will be one and then in the end will be two. Okay, I'm dragging here, just to make sure that at the end, this current is always should always be like greater than zero. Whenever we are forming a sub set. I'm not considering like an empty some empty subset or something, just to make sure I don't know what to return from here. This I'm just thinking like, what to do here. But like from a creative point of view, like I will start from this next year. And I will say that I'm need to go to the end of this array. And then I will check whether whatever index I'm going to start from or to consider for the subject that should not have been already marked in the marks array. If only it is marked as false, then we can say, starting is true. Through and we have to mark as false as well to kind of backtrack that we'll have to find on all of the combinations here. So here and discarding next will be like, I left one model and some remains carry on with them some has changed. So this is a new contribution from the number. And I'm also increased by one. So here, we check if there's a return when, if this is a tool return, I don't know when we are going to spend too much time not sure if this is true. Okay, so here we'll have to find like if we found one of the subsets as the value, then perhaps call this function again. That's from marks, and starting again at 0 to start the whole process again. And k will have to reduce by one, because we own one of the subsets. So we'll have to look for k minus one subset now at this time, but then something that will go to zero current numb will also go back to zero and look for the target here. Yeah. And I understand. So, if we keep on reducing K and we can the case when get the value to one that means we have found all of the subjects and this time like we started with suppose for example four and be reduced to three first two first and then come back to one that means like, we have all of the subsets and found at that particular time. So here we can say case one then we can true from that point. If we are not going we are not able to within to form in between them. We have to return false in the end. Yeah. Good evening. Okay, so let me think if I have missed some things if k is one then we'll return true scoring so much target then and current num is greater than zero then I'm going to explore more other subsets otherwise we'll start from starting next next time and look for in the market that is true for that element. And backtracking is needed here because when we are exploring and setting as the marks as true, but if if we are not able to find the proper subset then we have to reset it as false and that time. Yeah, do start exploring again. So, for example, if I take one example smaller one to suppose this is proof that we can take this example itself so this time with four here so I look forward to quarter and some and the target sum here is 2755 is some targets on that we're looking for. So when we start with value then mask array is false for it. So I will have here which is like all all phones here quiet rooms start with for each index it is we wrote in the current summary okay then when we are doing the loop we see that index zero is false if and that is true here. So we might as true and then again call the recursive function with again new index one and some current summers for k for plan numbers one and in surely starting current num is one when you say started with one at that time we start iterating from the second element three we again monitor this through we have two tools, total values here then we start from three here and the current sum less clean up some images. Yeah, there may be some kind of rolling here that I got current some more than the targets. Oh yeah, there may be negative values as well in this right.

Chaotic Llama: Let me check. I think I think all of the values can only be positive. Yes, the zero or positive values.

Aerodynamic Hobbit : Okay. So because when we get this current sum more than the target some then perhaps you can short circuit the iteration at that time, rather than going till the end? No, this time I'm going to land completely so far, that I can seems it later is if it is, if I get time. So, this time it will keep on going and and then there will be no like no reaching out to the the like current sum will never be as a call to target. And this will never be returned less true in the end. And we'll mark that all of them to fall back again in fine. Print four marks, store.

Chaotic Llama: Yes, I mean, I think this looks good for now. And I can give you the reference to the problem and you can try it out yourself. But in terms of the solution, I think you you have it.

Aerodynamic Hobbit : Yeah, there's really some like or declaration that I'm doing, perhaps.

Chaotic Llama: Yeah, there's there's definitely room for optimization, because you're already exploring some branches with a existing combination of subset, which you might have found earlier if they're able to create a subset of target sum. So. So yeah, you can do like, either through memorization or some other strategies, you might be able to, to optimize that. But you can check out the solution here, on 93. The, the reference there, there's also a solution to this problem that is based around bit masking. Okay, using bitmaps to generate the two to the n subsets. But it's quite complicated. I think it's useful. And it's like a fancy way of doing it. Personally, like, I had to really put a lot of effort in understanding how it works. So not sure how useful it is. But just for your reference, if you if you feel like it. In terms of feedback, to just quickly give you I think, pretty much everything you're doing. It's fine. And especially I think for Facebook, they want you to code quickly, because I think they may ask more than one question in the interview, so. Yeah, I think this is fine. Like you can explain your approach and then get into coding. Yeah, good job.

Aerodynamic Hobbit : Okay. Thank you. Thank you.

Chaotic Llama: Thanks. Bye.