# 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. Read more about the questions - [Alien Dictionary](/content/questions/alien-dictionary/index.html) ### Interview Feedback **Feedback about Samurai Unicorn (the interviewee)** Advance this person to the next round? Yes 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 a 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? Yes 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. **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, I have a global variable result. And I will need to keep basically as I go through 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... Basically, plus equals to string. Otherwise, I do basically a DFS on my... > *Continuation of the interview transcript, code implementation and further interaction.* **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 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.