Elemental Pigeon, a Google engineer, interviewed Samurai Unicorn in C++
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.
Feedback about Samurai Unicorn (the interviewee)
Advance this person to the next round?
How were their technical skills?
How was their problem solving ability?
What about their communication ability?
(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?
How good were the questions?
How helpful was your interviewer in guiding you to the solution(s)?
Very experienced interviewer and great question!
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 Cloudat 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
C++compilers. I have about five years experience. And yeah, as I said, I have a upcoming
L5? Samurai Unicorn:
L5yeah. 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
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
ABCDwe know that
ABCDis 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
C++. It's just that
MapReduceworks, 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.