C++ Interview with a Google engineer

Watch someone solve the alien dictionary problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Alien dictionary

Interview question

1) Return a list of all the paths to leaves in the tree. 2) Given a lexicographically sorted list of words, return the order of the alphabet.

Interview Feedback

Feedback about Samurai Unicorn (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

4/4

What about their communication ability?

3/4

(1) Focus on negative testing, and position yourself as an user of the code you wrote, and try to break it. (2) Try avoiding non const references. (3) Think about scaling the problem, when there is an opportunity. Good luck! :-)

Feedback about Elemental Pigeon (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

Very experienced interviewer and great question!

Interview Transcript

Elemental Pigeon: Hello.

Samurai Unicorn: Hi.

Elemental Pigeon: Hi. Are you able to hear me?

Samurai Unicorn: I can hear you fine.

Elemental Pigeon: Okay, cool. Hi. So great. Nice to meet you virtually. This is about 45 minutes session for Google style interview, which is an algorithms interview.

Samurai Unicorn: Sorry, what is that?

Elemental Pigeon: Oh, so this is a standard Google style algorithm interview. Is that what you're expecting?

Samurai Unicorn: Yeah, I'm looking for on site level question.

Elemental Pigeon: Of course, of course. Absolutely. So, usually 5 minutes are set aside for intro and stuff and out of the 40 minutes, usually in Google, there will be two or three questions. The first one is expected to be implemented fully. The second one depends on how much time you have in hand. Actually, some discussion also depends. So today I have two questions. The first one is, you know, pretty straightforward. As such, the second one will be all in the next level. So you can expect the first one, I am expecting a full implementation. And the second one we can, if there is no time we can discuss. And since this is a practice interview, I'm telling you all these. And usually, of course, when you're going on site, they won't say any of these. But before that, just anonymously let's introduce ourselves, I'll start first. So I'm a sixth level software engineer in Google and I work in Google Cloud at this moment. And I have in past worked in mostly industrial systems and artificial intelligence. So currently, I'm working in digital systems. Tell me a couple of things about yourself. What are you looking for? Are you targeting Google especially with this interview, I'm assuming that you're probably planning to appear for Google or something?

Samurai Unicorn: Yeah, so I work for Facebook. I'm a compiler engineer. I write compilers. I write C++ compilers. I have about five years experience. And yeah, as I said, I have a upcoming Google interview in about five weeks.

Elemental Pigeon: Okay, nice. So and then you're targeting which level? L4 or L5?

Samurai Unicorn: L5 yeah.

Elemental Pigeon: Okay. Nice. Okay, cool. So let's begin then. So I'll just copy and paste the question here.

Samurai Unicorn: Do you mind if I go to C++?

Elemental Pigeon: No, C++ is fine. That's fine. So again, usually, I mean, you can run and compile here. Usually, in the Google interview, you don't need to run, but it's a choice. I mean, here you're free to do it. So, just what I will do is let me just copy and paste the question here.

Samurai Unicorn: Okay. So given a binary tree, return all routes to leaf path, okay. So, I'm thinking I can go from the top and basically DFS all the way leaves. While I do this, I can keep basically a path of numbers, that we have seen.

Elemental Pigeon: Sure. You can do numbers.

Samurai Unicorn: Okay, okay. So, can I write code?

Elemental Pigeon: Yeah, of course.

Samurai Unicorn: Okay. So, I have a global variable result. And I will need to keep basically as I go through the the tree, I need to keep what I have seen. So if not root, I basically reached the... Oh, it's not... I have to be careful because I need to check for... If not root, I don't do anything. If it is a leaf node, I basically concatenate with it it... Basically, plus equals to string. Otherwise, I do basically a DFS on my... Okay, so if this is I'm a leaf node. So, here I am not a leaf node. Basically what I do is I do a visited plus equals root. So, plus the arrow sign. Okay. And then I basically... Oh, I don't use this. So somewhere I need to, basically add this. And after I'm gone, so after I visited this, I need to basically take back my result. So because here we are processing the current node, right? We'll add the current node to it. And then we basically recurse down the left and right tree. But then after we are done with the current node, before we return to our parent, we need to basically take back what was originally so that our parent can visit other nodes. And I check root is null, we don't do anything. If root is the leaf node, I basically add the final value and then I push it back. And then I also need to basically... So here, visited was changed, so I need to get it back. So I cannot do anything here because a leaf node has a left node and a right node. So if we do anything here and don't handle leaf node, then we will be pushing the same path twice.

Elemental Pigeon: So that's fine. Yeah. So okay, so is that the solution? Or do you want to run or test it?

Samurai Unicorn: I could, but the problem is I need to construct a tree.

Elemental Pigeon: Okay, so here's the thing. So in this case, looks like... why don't we do one thing? Why don't we take one of these in the example.

Samurai Unicorn: Sure. So, basically, we have something here.

Elemental Pigeon: You can write on it.

Samurai Unicorn: So we dry run it. So here our list is empty. We have a root coming in, which is one right? So right here we have basically a one, something like this right, the first level. Then we go to a with DFS on to the left side. So two is not a leaf node, so it doesn't do anything. So we basically add two to it. Then we DFS on the left side, which doesn't do anything, right? Then we DFS on to the right side, the right side is five and it hadn't turned out to be a leaf node, so add five to it. And we return. We don't DFS anymore. But when we return here, because we add this widget to the remains unchanged, so we get this path already. But was it here, right? So we go all the way up to one. So we come back to one. Then we basically DFS on to the right side, which happens to be a leaf node, then we push again, we return and then we return because the left and right child of one has been handled, and which actually happens to be after we returned, this empty string. And we basically get this path as well here.

Elemental Pigeon: Okay, so... Okay, so one thing is that looks like in the implementation you have, you might end up getting parts like, you know, instead of that, the one to five is fine. But instead of 1 2 3, you're probably going to get...something like that.

Samurai Unicorn: I don't think so. Because... I first take one into the string, right? Then I go to two. Then I get 1 2 5. Okay. Well, I'm worried these two levels go all the way...

Elemental Pigeon: Right. But the thing is, here, you're changing visited to one arrow two, right? Yeah. Then when it goes to two, it will change to one arrow two, correct.?

Samurai Unicorn: Yes.

Elemental Pigeon: On the left side. And you have also used the reference here.

Samurai Unicorn: Yeah. I reassigned it on line 67.

Elemental Pigeon: You are right. But you have reassigned after visiting both left and right.

Samurai Unicorn: Yes. Yes.

Elemental Pigeon: Is that correct?

Samurai Unicorn: Yeah.

Elemental Pigeon: I mean, after you have DFS on the left side, and then if you look at the tree, it will go from one to two, left side, right? From the root 1 2 5. When it comes to five, yes. You have not modified visited. But on line 2, you modified the visited, correct?

Samurai Unicorn: Yeah, that's right.

Elemental Pigeon: So then it will be one arrow two. And then it will come back to one. But when it comes back to one, what do you think this visited contains from the left side of the tree?

Samurai Unicorn: When it comes back to one? It just contains the one with arrow.

Elemental Pigeon: How do you remove the two?

Samurai Unicorn: The two gets tossed out because of the assignment on the two level. So we are like the level two, before you add to it, you removed that with it. You begin to unwind to the two level, you reassign. Why don't we build a tree and let's see.

Elemental Pigeon: Let me modify this example once more. Okay, let's say I have one more here, like four, okay. So, in that case, it will come one to two to four right? Then it pops back up from the left side and this will contains one to two.

Samurai Unicorn: When you reach four, you will contain one to two. Yeah.

Elemental Pigeon: Then it will go to five.

Samurai Unicorn: You will contain one to two as well.

Elemental Pigeon: Okay. Someone is resetting this? Okay, fine then. Sure.

Samurai Unicorn: Yeah, yeah. So but, this assignment theory worries me a little bit because it's a copy of the string. So maybe we could basically record the integer size. And then we basically visited erase and visited begin plus size. And let me see if it works. So if you were originally one, and you've add two to it. Yeah, I think that will work. Yeah. Okay.

Elemental Pigeon: So what's the problem with the assignment?

Samurai Unicorn: Because it's a copy of a string, it's not...

Elemental Pigeon: Oh, you are trying to optimize it? Sure.

Samurai Unicorn: Yeah. I tried to optimize.

Elemental Pigeon: Cool. So how would you test this?

Samurai Unicorn: I think I'll build that tree. So that's a tree of this one. And I will also test things like null pointer. I will also test things like use only on the root. And what else... and I will test something with basically a leaf node is not a difficult thing because of this. Basically, two is not a leaf node, but it doesn't have the left children. So yeah, that's that's some of the cases I can think of.

Elemental Pigeon: Sure, so, maybe you can also think of stress testing? For example, you can give a very, very large tree. Also these are all for example, a good test cases that we have provided, maybe you can also create some bad cases. For example, you know, I mean, malformed tree, there are these giant trees or maybe what about you know, someone will say it is a binary tree someone has given it, you know, trying to fool you or something. So, those are all sort of negative testing you can try out. Also, for example, another different kind of testing is here, it says integer, right? But maybe someone given would be, you know, the content of the tree is different. All the indices on this tree is formed, it is hard to do. But also, maybe there are some in C++, there can be garbage pointers, and it can lead to crash and other stuff. You know, for implementation it is fine. But for in life, for example, maybe the tree data structure is corrupted. So we can have some exception handling, and so on, so forth. I mean, yeah, that would be cool. Yeah. So, let's move on to the next question. Find index here in this section. Let's see. Oh, let's say this one, right. So what what happens is that I mean, what the our task in hand is, for example, we don't know if any sort of language, right? It's not English, but it is just using the English alphabet. And our task is given a series, let's say it reads a portion of the dictionary of this new language, which happens to use the English letters, what we would like to find is that what are the alphabet ordering? So for example, someone gave ABCD we know that ABCD is in order, so we always give the ordering. So here is a bunch of words, which are lexicographically sorted, which are in dictionary order. And from here the output is that this is the order of the alphabets in this language. So a couple of more examples are as follows. So in our example, example two, if you see, as you can see in this case our output is X. And if number three is invalid case where it says that x is followed by z by, again, z is followed by x, so it cannot happen.

Samurai Unicorn: Okay, I see. So first of all, do all these things... Are they lowercase letters.

Elemental Pigeon: Yeah, let's assume that these are all lowercase letters. And if there are multiple solutions, any one is fine.

Samurai Unicorn: Okay, so I'm thinking this is something like... because if you're looking here, right, w definitely goes before e. So in the final alphabet, w doesn't go to before e. Similarly, e definitely goes before r?

Elemental Pigeon: Yeah.

Samurai Unicorn: We can derive this relationship. But then this one, the second one... r, we can't really... Oh, on the second one. Because we can only tell the difference of a letter, if their previous is their previous letters are the same. Because if we can already tell their previous letters apart, then the meaning of this letter, this column of letter is really, we don't really know. Right?

Elemental Pigeon: Can you say that once more?

Samurai Unicorn: So in the first column, w definitely goes before e and e goes before r, right? So if we look at the second column, we can't really tell what's the relationship between r and t? Because r could go before t or it could go after t. Because the w before it already dictates the ordering of the w r t... So this column here, we can't really derive the relationship of r and p. But if if their previous letters are the same, then we can tell. Right?

Elemental Pigeon: Yes.

Samurai Unicorn: Okay. So I'm thinking with this sort of... so basically, if their previous letters are not the same, then we cannot help. If the previous letters are the same, then we can tell the relationship. And with this relationship, I'm thinking we can build a graph, then we can do a topological sorting on the graph to get the order.

Elemental Pigeon: Sure. So how would you go about it?

Samurai Unicorn: So there are two parts to the solution, I think. One is basically analyzing the word is trying to extract the relationships between the letters. The second part, once you extract the relationship, you can basically insert the relationship into the graph. And once you do that, you can sort of do... then the second part is doing a topological.

Elemental Pigeon: Sure, sounds good. So would you like to implement or...?

Samurai Unicorn: No, I still have some... So they are the same.

Elemental Pigeon: So for example, let's go over an example. Let's go over the first example. How will you build the graph?

Samurai Unicorn: So I look at the first column, w goes before e, so I basically in my graph, I would have a w as a parent.

Elemental Pigeon: Okay, this is what...

Samurai Unicorn: I would do something like add to order. So this I'll give it a w and e, basically that indicates w goes before e in my graph, so I'll just do this. So then I will also add order e r, then that would indicate e goes before r, right?

Elemental Pigeon: Yeah.

Samurai Unicorn: So that's that. So then the second column, so this is tricky... Okay, so the second column, we need to check... Yeah, but now how do we break them into groups? Right... So I need to break them into groups based on basically the first column. Let me think. Why don't we do a brute force scan, see whether their previous letter is the same. So that's a, it's basically a brute force scan, breaking them into groups, but that's not really optimal. Right... I could do that.

Elemental Pigeon: So these are already sorted. Right? So for example, during the first column... maybe while extracting the relationship of the first column, can we can we break them up into groups?

Samurai Unicorn: We could, I'm still thinking, yeah. So when we say the first column, we know... Okay. So the second column group is this. Yeah, I guess we could, I guess we could. Yeah. So the second column group is this. And when we do this... Yeah. So basically, I think the start of the group is basically initially zero, right? So every time I go down, I locate whether lm equal to the previous one or not. If I'm equal to the previous one, I can be expanding on the... Yeah, I basically keep expanding on the... let me see. I start with zero. So initially, I only have one group, right? Initially, I only have one group, this is going to be zero to four, right? So I will construct the next column groups. So what this is, when I first start with a zero and zero is equal to zero. So I don't break into groups. One, one is equal to zero? I don't really, let's see... okay, zero is equal to zero, I don't break into group, one is equal to zero, I don't break into groups. So then I have two is not equal to zero. So then what I do is, I break 01 into a group. And now my starting point is basically what? Right? So one is equal to one, so I don't break them into groups. Two is equal to one, I don't break them. Then three is basically equal to three.

Elemental Pigeon: Why? Why are we breaking one and two?

Samurai Unicorn: Because they are both e and the... Sorry, it's not one and two. I mean, it's two and three.

Elemental Pigeon: Right. Yeah.

Samurai Unicorn: Yeah, sorry. Yeah. And then I have four and it's going to be with itself. Then when I reach the second column, I locate a group list. I locate the group list and I iterate on them. Then I keep dividing into other groups, and it's also possible this one doesn't really have one... if he doesn't have one... I think I skip, it doesn't matter. Yeah. Because you could have this. And this, you could have something like this, f and x would still be able to tell the relationship as they are still this. I mean, if we could just change this to e r. Yes, this will still be able to tell the relationship, why I only break generally new groups when I see different character in the second column. In this case, though, I break them into groups. Yeah, so basically, I have this thing to break them into groups. And every time I increment a column, if we in a group or column doesn't exist, then I don't want it. I don't break other groups. I just continue.

Elemental Pigeon: Yeah, sure. So so once you construct a graph like this, how would you detect an error? I mean, let's say... I mean, under what condition would you not be able to define the output relationship?

Samurai Unicorn: If we cannot do a topological sort of the graph. Basically, we'll have a cycle in the graph.

Elemental Pigeon: Yeah. Like the last example, that is one. If there is a cycle, we cannot. Is there any other condition where we cannot really define?

Samurai Unicorn: Let's see, if there is a cycle, we definitely cannot do it. Let's see. Well, I think it's possible to have multiple solutions, but I guess we discussed about that. Right?

Elemental Pigeon: Yeah. If there's more than one solution, anyone is fine. But is there, other than the cycle, any other way or condition where we may not have a deterministic solution?

Samurai Unicorn: What if a letter exists in the word but we don't have an order for it?

Elemental Pigeon: Correct.

Samurai Unicorn: What does that mean? That means we can put it anywhere, what what did they consider?

Elemental Pigeon: So we cannot define that. If the input is something like A B C B, then we know it is between A and B, but we don't know how C and B are ordered right?

Samurai Unicorn: Yeah. So yeah, basically this...

Elemental Pigeon: So we need more input to analyze.

Samurai Unicorn: Okay, okay. Yeah. Yeah.

Elemental Pigeon: Good. So that's pretty much the question I had, I mean, now we can we can kind of discuss about, you can write a pseudocode if you want. I think your solution is correct.

Samurai Unicorn: I think I'll write the code to try to break me into groups, how about that?

Elemental Pigeon: Sure. We don't have much time, so maybe write pseudocode instead of the full code. Try to break up the code in a modular fashion. So you can reuse the same functions over and over.

Samurai Unicorn: Yeah. So basically, I'll just a process column. And I also have the basically the vector. So basically this this will break them into groups and also I want to basically have a vector current_group, have a vector of int next_group. So this will break them into groups and and basically also compute the next groups and then I just do a topological sort. So, basically it will take take basically a vector of nodes. So, you will do a topological sort and basically return true if possible, false otherwise. And you will also basically, this will give me a string and the string is really just sorted string. And basically, I will also define something like a node. What a node does is... So, node is basically a public function or node, what it does is I have the character in the node, then I basically have integer parent. So basically, every time I only need to keep track of the parent count, right? So this node has some basically... let me see. Order function, I'm sorry.

Elemental Pigeon: Yeah, so the graph is a vector of node pointers. So, then how do you know the child or the next one?

Samurai Unicorn: Oh, yeah, we need to know the child. Yeah, we need to know that. So, it's going to be a basically vector of character children. So, yeah. Basically, all this does is would basically get a node pointer.

Elemental Pigeon: Is this a vector of character or vector of node pointers.

Samurai Unicorn: It will be a vector of node pointers. So graph is going to be p minus zero and node pointer equals graph p minus c minus a. And basically what I do is basically... Yeah, something like this. And of course, you're have to give the graph so this graph can be pre constructed. Yeah. And so, basically, every time we process a column we do basically for integer start equals so... First of all, vector G in current groups... Okay. So we do that and what do we do? Okay. If start basically... Okay, start is... we need to be careful how to do this. Okay. So if... Let's see... Okay, this is really tricky to figure out. So, basically I need to check whether I need to build a relationship. So, okay.

Elemental Pigeon: So essentially what we have to do is for the for that group we go over which index we are browsing right? So, for your first group, we are analyzing the zeroth position and then also it tracks which index we are browsing. And then we are going to browse those individual going over left to right. And whenever that changes, if the current one is not the next one, then we add additions.

Samurai Unicorn: Yeah, yeah. So, basically...

Elemental Pigeon: So in each group, just like you are preserving the indices, we need to preserve like the, you know, the words, we need to preserve which index we are browsing.

Samurai Unicorn: Yeah, yeah, I am preserving the indices. Yeah. So here, what do I do? So I locate if I am equal to the... so let's see... if the current one is equal to the next one, if the current one is equal to the next one, then... though I don't have, so first of all, I don't change the group. But I also don't add any order. Okay. Otherwise, I need to... that I need to fix up as a condition for, you know. So yeah, otherwise, basically, I'd order. So you add ordering and also then you need to basically group. Yeah. So in the last group it is a little bit tricky. Okay, so let's do this. And so the last group and yeah, and we need to push in the last group as well. So basically, the last group is going to be... so we did this and we are going to basically... Oh, okay. Okay.

Elemental Pigeon: Last group would be something like wherever your last index was.

Samurai Unicorn: Okay, so then after we break out of this and eventually we're going to... okay, so we're going to begin group, next group is going to, we need to break out this one. Hold on.

Elemental Pigeon: The last group would be essentially your begin group add to G one.

Samurai Unicorn: Yeah. So I'm still thinking where to add it. And he's going to be ending it. I'm not sure. So when you come here, you'll get this and you'll keep doing it. And when you will reach something, you will reach basically, this is no longer equals, then we basically stop right here and begin group gets adjusted here. And after way, let's say if we just have one group and the way it would have one group, we'll break it into two groups. Basically, what happens is the first group start... Yeah, I think that will add a last group to it and it's going to be inactive and yeah. That's how the way we can basically keep doing this until we basically we can keep calling process column and if current group is empty return. And there are something that if...

Elemental Pigeon: Okay yeah I think that's fine. So we leave the last group you're adding, we add it to current minus one or would it be the you know, the G one because we know...

Samurai Unicorn: Oh okay, you will be...

Elemental Pigeon: So, this is for just outside of this right. So, which means it falls off here and it should be this in g one and then it will move to the next group.

Samurai Unicorn: Okay, so here would be...

Elemental Pigeon: This would be in an index of that rule, because we are further analyzing the current group, right? Okay, that's fine. So cool. I think that's fine. So a few things is, that you have done great. So, one thing that I have noticed that you are using a lot of, you know the pass by reference, and in Google what I have seen is that we only use constant reference.

Samurai Unicorn: We only use?

Elemental Pigeon: So the reference is only passed using constant, so we cannot really modify it. And you also have a global visited here, right? And we don't use that. So keep in mind, this is just a style that we use? So whenever we need to modify it, you can pass a pointer instead of a reference.

Samurai Unicorn: Which line?

Elemental Pigeon: In the earlier solution, when we did the string visited. So it is fine. In general, this is absolutely valid C++. It's just that Google as a company, they tend to use constant references. And if there is some divide, it needs to pass by a pointer.

Samurai Unicorn: Okay, so how should I fix this? I pass in... So this particular example, do I just pass as a string or?

Elemental Pigeon: No, you pass a pointer to the string.

Samurai Unicorn: A pointer to a string, so I do this? Okay. Oh, okay. So you said the references are constants? And pointers are. Okay. Okay.

Elemental Pigeon: Let's keep in mind, but I don't think it's a big deal. It's just a Google thing. Yeah, I think other than that, you have done pretty well. We didn't have time to discuss the complexity. But it's pretty straightforward as such. So let's talk about the second question. So I just had that one, one piece of feedback, nothing else. If you have any other questions... So two things, actually. So one is the style thing and other is testing. So maybe you want to tinker away when the testing comes, think, you know, out of the box, that what portion can really go along, maybe stress more on the negative testing, since you're... so I mean, give a pathological case, give the normal case, give null pointer, single node, multiple nodes, full tree, skewed tree, all those things, and then also move on to the negative scripts to testing for all of those.

Samurai Unicorn: Okay, I see, I see, I see. How important are the testing? Let's say in the tree example, how important? How much emphasis do you guys put on testing?

Elemental Pigeon: So as such, if the interviewer or an engineer, you can ask for something, sometimes interviewer might ask you how to test it, and they would look for how comprehensively you're testing.

Samurai Unicorn: Okay, okay. But let's say, if I got a question correct? If I got an algorithm correct, but my testing is really lacking. Is that a possibility? Could that be a reason to basically to fail the interview.

Elemental Pigeon: I mean, so your motivation would be to get as strong signal as as possible, right? So you don't want to cut corners. So what would happen is that interviewer might say that, okay, he's, uh, he's solving the problems really well, strong coding, but maybe testing can be better. Now, okay. Everybody gives a strong yes. What if someone says, oh, maybe not? So I mean, if you can come, see, let's say, for let's assume that out of the five interviews, one of those didn't go that well, right, let's take the case. Now, let's say that there is an interview or some period interview didn't go that well. But out of the other four interviews, you have done really well on coding and algorithm. And now your choice is, either he can, you know, go software testing, or really good, the good testing. So you think, good side, don't don't leave anything open, because you can do the testing, right? So just think about it, think through, or put yourself in the shoes of the user. Assume that you don't know code and you're trying to break it. What are the tests you would do? Right? Once you think from that side, that will give you the perspective and your code... But to answer your question that no that in particular interview will probably not reject you for that interview. But they will also... it would not be hitting it out of the park. Because they were looking for a holistic view. So they'll say yeah, maybe you don't want that right. I mean, you want them to say that yeah, he is great. Or you can make it complete. Don't you know, leave a leave a door open for doubt. I think that's it. Okay. Great, but if you're not, you know, but then if one interviewer says maybe not. If others are very strong, then that will get superseded. Right.

Samurai Unicorn: Okay. I see. I see. So I also heard, is this sort of the scale your people use at Google?

Elemental Pigeon: Sort of the scale?

Samurai Unicorn: Yeah. I'm on line 51.

Elemental Pigeon: Yeah. Yes, this is a clear rate.

Samurai Unicorn: So how would you rate on this particular interview?

Elemental Pigeon: I would say something between hire and strong hire.

Samurai Unicorn: Okay, okay. All right. Okay. Yeah, I just want to know what the bar, is sort of what to expect.

Elemental Pigeon: I probably would not give strong hire, because if you're a strong hire is about everything is perfect. Hire is very good. So that's why maybe I would get higher and then verbally say maybe the testings were perfect. Didn't need some kind of prompting all through, then it would be a strong hire.

Samurai Unicorn: Okay, okay. I see.

Elemental Pigeon: How's your expectation, does it match with your expectation?

Samurai Unicorn: I would say I was thinking of maybe between weak hire and hire, maybe more towards the hire, but you said higher than I expected.

Elemental Pigeon: Because I was impressed with your second one, I mean, even if you did not do the coding your algorithm. And since we did this in limited time, you are able to say the algorithm, and you coded up the pseudocode pretty well. So that's why I really gave it a hire and I would put in a good word for that. So the initial testing... I mean, so it's definitely a hire following that.

Samurai Unicorn: Also the second question, I think, a lot of things, I broke it down by abstraction reasonably well, right? So the order I just, basically abstracted away, right?

Elemental Pigeon: No, these are good, this is reusable code, because you are reusing the same function. That is what the ask was. Also, if you remember, I mean, we discussed a lot in this practice interview, we discussed a lot as you were thinking through. In real life, the interviewer is not going to discuss with you. And remember that for each such discussion, they would probably say that, don't give an opportunity to the interviewer to say that. Whatever I say today, at the end is productive, but you know, listen to the interviewer. And whenever they say something, which it might be some hint, and if you take with take the hint and run with it, that is a plus point. So they would that okay he knows how to take a hint and go with it.

Samurai Unicorn: Okay.

Elemental Pigeon: It should be the same as Facebook. I'm sure you also conduct interview in Facebook, right?

Samurai Unicorn: Sorry.

Elemental Pigeon: I'm assuming you also are an interviewer in Facebook. Right? You also conduct interviews?

Samurai Unicorn: Yeah, I do. I do some interviews there. But usually in Facebook, we don't give very difficult questions. And actually, if you give a very difficult question, recruiter will find you and ask you, why you gave a difficult question.

Elemental Pigeon: I was just saying Google has a question scaling in. So usually, they will start from, you know, easy to medium question, the first one just for warmup. And then they will progressively go into more and more detail question. If you can solve faster, it will give them more questions. So sorry. You were saying something?

Samurai Unicorn: Yeah. So I was about to say about the same thing as what you just said. But I have another question. So I heard that they ask a lot of follow up questions.

Elemental Pigeon: Yes, sometimes. Sometimes they do. Yes. So for example, here I also asked one follow up question like other than the loop in the dag, where else can this fail? Right?

Samurai Unicorn: Okay, I see.

Elemental Pigeon: We would also discuss for more follow up questions like the scale. So Google loves to scale. And if your graph is too big, how to solve and the last round would be very abstract, in a sense, I mean, what if your algorithm doesn't fit in memory, how to solve, those kind of things.

Samurai Unicorn: Yeah, I feel a lot of Google questions they asked, like, what if the dictionary is too large? How to do it? What if something to large, how to do it? Right?

Elemental Pigeon: That's why I was mentioning that in this case, if the graph is too large to do, those kind of things. For every problem, think about how can you scale it?

Samurai Unicorn: I see. But just out of curiosity, how would you do it if the graph is too large? Because I don't have a distributed system background, but you do. How would you do it? I just want to...

Elemental Pigeon: Yeah, so you have to essentially divide and conquer, right? I mean, just like the MapReduce works, so you have to partition the graph and read and do everything. And then combine the results.

Samurai Unicorn: Usually, this sort of thing is divide and conquer is just a how do you divide that? How do you how do you combine, right? How do you merge eventually, right? So it's also case by case basis, different questions are different, but the underlying principle is about the same. Right?

Elemental Pigeon: Exactly.

Samurai Unicorn: Okay, okay. I see.

Elemental Pigeon: Okay. I think we had a lovely chat.

Samurai Unicorn: Yes, thank you.

Elemental Pigeon: All right. Thanks, man.

Samurai Unicorn: Yeah, thank you. Yeah. Okay, that will be it. Thank you. Bye.

Elemental Pigeon: Bye.