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

Given a list of lists in a lexigraphic ordering, return the ordering of the characters in the language.

Interview Feedback

Feedback about Teflon Artichoke (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?

2/4

I will write interview feedback here as if I were interviewing a real candidate. (The rubric is generally: <2.6- strong no 2.6-2.7 - no 2.8-2.9 - weak no 3.0-3.1 - weak yes 3.2 - 3.4 - yes 3.5+ - strong yes) A candidate will usually receive a passing score (3.0+) if they get a working solution by the end of the time period (excluding any extensions) Overall: [3.2/4.0] Problem solving: [0.8/1.0] - Candidate has seen the question before, but I asked candidate to solve anyways. He had a solid foundation on the DFS variant of topological sort, and had good explanations for me when I had prodding/followup questions to his code. He clearly understands the problem as well as the code he writes. (I suggest looking into Khan's algorithm for topological sort as well, I personally find it easier to reason about). Unfortunately, we did not have time to get into extension questions, which would have been helpful for me to better evaluate his problem solving skills for questions he had NOT seen before. Coding: [1.5/2.0] - Candidate wrote correct code, and was able to translate his thoughts to code fairly easily. His code was nearly bug-free, which I found to be impressive. I also really liked how the candidate broke up the code into easily digestible (and testable!) functions, which helps keep things organized. The points I took off were for code speed and execution - I would expect that a candidate who is familiar with the problem can code it up very quickly, but getting a working solution took the full hour. However, I will note that I think the candidate has a lot of potential to code much faster - it seemed that the majority of the time spent was on explanations and talking through the code. I think if this part can be cut down (via more succinct summaries before and after coding), then there is a lot of room to gain points back here. Misc: [0.9/1.0] - Candidate was friendly and personable, as well was easy to talk to. Communication during the coding portion could have been more focused, however, which would have both saved time as well as offered more clarity in the candidate's thought process. I liked how the candidate brought up edge cases in advanced and had a test-oriented mindset. In general, I would be happy to work alongside this candidate! Summary of feedback/things to work on: 1. I would say the candidate's coding correctness is very good, the main area of focus is communication. - Good to explain thought process, check in with interviewer, then code, then check in with interviewer. - No need to spend lots of time on brute force solution/time complexity unless interviewer specifically asks you for more elaboration. Can be good to check in with interviewer whether they want you to go into this before you jump into your explanations. 2. Coding speed - Again, probably related to 1., but writing code faster would be helpful. - You can do with fewer comments/pseudocode. (feel free to keep it if it helps you stay organized however!) - In exchange, you can talk out your plans with your interviewer if it is faster, and once the interviewer agrees with your thought process you are good to go! - Python could also be another way to help this as well Overall good job! And good luck with your upcoming interviews - you got this!

Feedback about Contrarian Burrito (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

1/4

Interview Transcript

Teflon Artichoke: Hello?

Contrarian Burrito: Hello, can you hear me?

Teflon Artichoke: Yep, can you?

Contrarian Burrito: Yep, I can hear you. All right.

Teflon Artichoke: Yeah. How are you? Thank you so much for doing this.

Contrarian Burrito: Yeah, for sure. And how are you doing?

Teflon Artichoke: Pretty good.

Contrarian Burrito: Cool. So yeah, I guess the way this works is, um, have you have you done an interview on our platform before?

Teflon Artichoke: This is actually my third.

Contrarian Burrito: Okay, great. So I guess you're familiar. But obviously, every interview will be a little bit different. The way I like to run my interviews is, well, I guess first, I'll ask you, if you want sort of feedback in the middle, or do you want me to treat this as sort of a mock interview? Like as if it's a real interview? I just give you all the feedback at the end?

Teflon Artichoke: Yes, definitely. The second one, just all the way at the end.

Contrarian Burrito: Cool. And then I guess, second, I guess the way I usually run my interview, in that case, is a potential interview, I'll introduce myself, give sort of a little bit of time for you to talk about your background and stuff as well. And then we can jump right into the technical questions. And then at the end, I'll save some time for you to ask any questions you want and then provide feedback, either in person or offline at the end via a written format. Does that sound good to you?

Teflon Artichoke: Yeah, that sounds great. Yeah, sorry. Can you hear me? Okay?

Contrarian Burrito: Yeah, I can hear you. It cut out for a second, but I hear you okay.

Teflon Artichoke: Yeah. Yeah, you cut off for a second too. So I wonder if I could? I might, can you give me one second? I'm just gonna go to a different place.

Contrarian Burrito: Yeah, take your time.

Teflon Artichoke: So okay. Yeah, let me walk over to the kitchen. And while you got so how long are we thinking here, by the way, for the actual interview itself?

Contrarian Burrito: Yeah, usually around 50 minutes, 55 minutes for the interview. And then, yeah, couple minutes at the end, on either end for questions or anything like that. Hello?

Teflon Artichoke: Hey.

Contrarian Burrito: Hey. Okay. Carry on.

Teflon Artichoke: Yeah, and I had to switch to a different wifi. But okay, I'm all set. I'm sorry about the delay.

Contrarian Burrito: Real quick. Which language did you want to code in?

Teflon Artichoke: I like definitely C++. So here we go. Okay.

Contrarian Burrito: Great. So I'll paste the question at the top here. And then feel free to take your time to read it and understand it and let me know if you have any questions.

Teflon Artichoke: Oh, hello.

Contrarian Burrito: Hey, sorry. Can you hear me okay?

Teflon Artichoke: Yeah. Did you cut out or did I cut out?

Contrarian Burrito: I'm not sure what happened there. But now it's okay, yeah.

Teflon Artichoke: Yeah, no. Well, I mean, that was fine. I was just reading the interview question. Okay. Okay, I think I get the picture here. So what we're asking is we're going to get going, the first thing I like to do is I kind of like to write the contract or the function. And then I get into the nitty gritty. So this function, we'll call it, you know, we'll call it determine language. It's going to take, it's going to take as input a list of words, list of strings. So can I call that a vector of strings for convenience sake?

Contrarian Burrito: Sure, yeah.

Teflon Artichoke: Okay. And that's right. That's all it takes. And it's gonna return a vector of I guess, characters here. Is that correct? Okay. Um, okay, great. So what we're saying is, you know, we can determine sort of a... Oh, shoot, I'm so sorry. I just realized this question looks familiar. I think I do have, I think I have seen something like this before.

Contrarian Burrito: That's fine. And if anything, that's actually good, because I have some interesting extension questions afterwards. So if you can get through the first part quickly. That's totally fine.

Teflon Artichoke: Okay, cool. So, right, the, okay, so we're asked, and, you know, we don't know the ordering of the characters in the alphabet, but we know, looking, but we know that the words list is sorted alphabetically, so we can make decisions based on that. So for in this example, that you've provided me, we have p first, because according to this P comes before B, and P comes before K, although I couldn't. I mean, maybe U could come first too. I think, well, anyway, so I guess P or U at this point, we know comes first, and then well. So then, let's see, I guess we'd look at all the tiebreakers past character zero. So to determine... So here, we can also say that U comes before B. Okay. Right? Because PBK is the same here. So you don't have to come down to this tiebreaker, U comes before B, what else? And KBP comes before U okay. And that was my first question was, it could have been P or U that comes first. So that's and I was looking at the last two. So that's why we say P, then U and then B N K? I guess. K comes less because right, a K comes last because that's what we know from looking at the first character. Okay, so um, yeah. So I guess, before going to the algorithm, just what I like to define the edge cases and corner cases, just so I sort of have in the back of my mind as I'm going through this. So this could include like an M could be an empty list of strings, maybe.

Contrarian Burrito: Yeah, I guess that could be a possibility. Sure.

Teflon Artichoke: Okay. I mean, I'm not even sure if the code is drastically different in that case. What else do I got here? Could there be multiple? Could there be multiple orderings? Oh, it says, similarly, we can find another order. So that I assume that we can return any order that we get?

Contrarian Burrito: So I guess, yeah, so for now, let's assume that there's a single correct output for a given input.

Teflon Artichoke: Okay. Okay, got it. Um, okay. And I guess it's like, we're assuming that this is like a valid, you know, there's no, this is actually sorted correctly, then I guess for now all I can think of is empty words, as an edge case, although I'm sure I can think of more. Anyway, let's get to the algorithm here. So I guess one way we could do this, and this would take probably a really long time. So I'm going to call a brute force approach, is going to be generate every ordering. Okay, so for every single ordering, and I'm going to define ordering as you know, anyway, we order all the characters that are representative in this language. And is that going to be only alphanumeric characters? Yes, we said Latin alphabet. So I'm going to say, can I say lowercase letters too or?

Contrarian Burrito: Yeah, I mean, okay, we can just assume lowercase.

Teflon Artichoke: Yeah, yeah. So for every single ordering. You know, excuse me, traverse words and, you know, and confirm that or... Excuse me, and determine if you know, ordering maintained in word where word is one of the one of the words. So actually, why don't I do this... If ye, return ordering. If no, don't do anything. And if we exit that loop, that means you couldn't find one. I guess we'd return empty vector, which but although I guess we're assuming we do find one. So does this approach like makes sense in terms of it technically works or any point?

Contrarian Burrito: Obviously, it would be extremely computationally intensive.

Teflon Artichoke: So yeah, yeah, yeah. And I think I would evaluate it something on the, like we'll say O of m, where m is the number of characters in this language. And n were, like, for this step would be o N, and N being the number of characters in the language. And then for every word is obviously this. O of n, but actually, we're traversing the words, too. So that so you know, we'll call this o of L, where L is the length of the longest word, so. So it's very long o of m times n. These are all compounding. So we definitely got to think of something better here. A more optimized approach. So what can I say here?

Contrarian Burrito: Yeah. Every single thing, what is m? Just like in?

Teflon Artichoke: Oh, yeah, sorry. Why don't I just put here, m is size of alphabet of alien alphabet? So like, number of like, the size of our alphabet is 26. Right? The size of the number of unique characters in the language would have been a better way of saying it and its size.

Contrarian Burrito: Just to double check here, that would that would be larger than O(m).

Teflon Artichoke: Right. The numbers? Oh, yeah. I'm sorry. Yeah. I don't know why I'm saying it should be O(m!), I believe. Yeah. Yeah. Good call. Thank you. And then L is obviously I think, the length of longest word. Okay. So yeah, so it's going to be O(m^2*n*l) l could be off by a little bit, but definitely big, big time complexity, right. So to optimize this, you know, the reason I say I've seen this before is because I've done problems where we've had to map excuse me represent strings with graphs, and I think that makes sense here, because we could do what's called a topological sorting. Are you familiar with that?

Contrarian Burrito: Yeah.

Teflon Artichoke: And I think, okay, so I mean, I don't even explain what it is. But I think, yeah, basically, you know, populate a graph. And I like to use an unordered in this case, why don't I just define it right here, populate unordered. And this will give me a map of, what am I going to say? Here's what makes sense characters to... Yes, it would be chars to, to unordered set of chars, I think that way, and that way. And this is, by the way, I'm representing the graph as an adjacency list, so and more specifically, an unordered map where where a character is mapped to the set of characters that need to be, you know, traversed after it. Does that? Does that make any sense? That would, that would come after it.

Contrarian Burrito: Like a list of children, right? Something like that.

Teflon Artichoke: Yep. Yeah, exactly. Exactly. Yeah. Okay. So we populate that populate by traversing words. Actually, it might be not as simple as traversing words. What would what would I need to do? Hmm. Well, the way I would traverse words would be... okay, okay. So I mean, I guess I could look at, I think what I do is I would look at two strings at a row at a time. So if we look back at line nine, excuse me, we would, there's going to be between adjacent I mean, this is the beauty of it being sorted alphabetically. Between two adjacent strings, there's one character, it gives us information about one one character or one or two different characters. So unless they're of different length, in which case maybe not but so for example, here we know that p is less than b, and then between This string and this string? Well, it's the B's or tied, let's move over. And the Ps are tied and the Ks are tied. So all the way, what this tells us is that U is less than B. So that would be our thought process. How do I describe that? Yeah, maybe by traversing words, two at a time. And yeah, searching for first non same index, or here. So, um, that we'd have that sort of note to self look out for same string lengths, right? Because in those cases, we could technically not be informed anything. So I don't know if that's going to be a hiccup for me. Anyway, that's how we're populating the graph. And then once that's done, we're going to perform a topological sort. On graph, and, then I guess we are, then we're, oh, I mean, I have It's been a while since I've been in topological sort. Usually, I use the stack, the topological sort, like return to stack or updated a stack. So I would, you know, pop, you know, populate a vector with results of topological sort. And return that. Oh, when I say...

Contrarian Burrito: Yeah, we can go into that after. Let's start with maybe coding up the first part, which is as you mentioned, like looking for the first like, the line. 23.

Teflon Artichoke: Yep, yep. Okay. So let's see, we have an unordered map. character to an ordered set of characters. And by the way, can I assume that every can we assume? Can you hear me by the way?

Contrarian Burrito: Yes, yes.

Teflon Artichoke: Okay. Sorry, I got a message saying reconnecting or something. Can we assume that every character in... Okay, so every character we need to worry about will be present in one of the words. Is that a fair statement to make? Like, the fact that D was in India? Okay. I was just thinking about that as we for this step. But yeah, okay. So this is our graph. And then for every what was the instruction i said, traversing words two at a time, searching for first, okay, so we do something like this. So for, we're going to loop over words, with a twist, where we're going to actually stop at the second to last index, because what I'm going to do here is I'm going to call a helper method, that's going to... Yes, helper method is that's going to... so let's do this, the helper method is going to do so find, you know, find knowledge, I don't know, I want to delegate to this helper method, something, the logic that will make the character comparison, you know, character by character within a word. So, you know, find next, or how about add to graph. So what this is going to do is, it's going to take a graph, it's going to take word index i and it's going to take word index i plus one, that's what I want to do. So and the reason I'm doing y plus, and I'm doing y plus one, and that's why I'm ending not at the last index, but the one before that, so. So we'll never be out of bounds here. What this method which I'll implement in a second is going to do is it's going to traverse these two words that I pass in one by one and update graph. Once it gets to the end, once it gets to the to that, you know, critical point where the strings differ, so and, sorry, I didn't mean to interrupt. Yeah, go ahead.

Contrarian Burrito: Oh, no, yeah, that makes sense to me.

Teflon Artichoke: Yeah. Okay, great. So why don't I just throw this in here? I want to pass it by reference here. So we're being sure to update the actual graph rather than a copy of the graph, okay, and then say word one should say w one and w two. Okay. So how about this? Okay, so we'll have an end. We'll have an end index that's going to be initially set to zero. And while maybe I could pseudocode this, while both bounds for both words. Excuse me. Okay. Well, and, you know, and index, so w one index at w one, and w two are the same increment index. So what I'm saying here is while they're both inbound, and then additionally, once we, if we look at what that index is that both strings if those are the same, if both of those conditions are met, we'll increment index. Once that's done, you know, if those in bounds, excuse me, both index were in bounds. Bounds for both words, that means that we exited the index because this was no longer the case. Now, add edge. Otherwise, I mean, we don't even need to do anything we can just because it's a void function we can. That's all we do. So I'm going to code this out. So I would add, the smaller one would be the one that comes in word one. And we know that because word one comes forward to so we're going to say let's add in graph at index at the unordered set mapped to by w one. And let's insert... Did I get that? Yes. Let's insert w two at n. And that's saying that that character from w two comes after character from w one. Yes. And that's it. So. Okay, so that's how my add to graph method works. Is that does that seem like to make sense to you need me to clear up anything? Yeah.

Contrarian Burrito: Yeah. One question I have is, what other information we need for the graph. So right here, we're generating the, the list of children for each, I guess node, right?

Teflon Artichoke: Yes. Yeah.

Contrarian Burrito: We're doing a topological search, I guess depends on how you want to do it.

Teflon Artichoke: But how we want to implement the topological sort?

Contrarian Burrito: Yeah, okay.

Teflon Artichoke: Okay, maybe I can do that. Next, whoops, maybe I can drop some notes for that next. The way I do, I'm going to call the TPS because I still don't know how to write topological sort, you know, it's gonna need, it's gonna need the graph definitely. And it's going to need to, you know, what, I just realized, I'm going to probably, I'm going to have to implement this recursively, which is not as space efficient as as using a while loop. But that's better than nothing. It's going to need needs to know knowledge of the graph. It's going to need to take an ordered set of characters and this is going to be will called visited, visited chars.

Contrarian Burrito: This is a depth first search method, right?

Teflon Artichoke: What was that?

Contrarian Burrito: This is like the DFS method.

Teflon Artichoke: For topological sort?

Contrarian Burrito: Yeah, yeah.

Teflon Artichoke: Yeah, it is. So I guess, my idea that we would, how do we do this, we would, you know, we would add to... basically, we're going to we're going to visit all the nodes of, you know, a given character, so actually, we need that. So we'll say, curr char, we're going to visit all of its children. And we're going to, we're going to recurse on the children. And whenever we get, and once we're done recursing on the children, we would actually push that to the current node to a stack. Which I, so and I'm calling it reversed order... As a reminder to myself, when it's all said and done, I gotta reverse the order, because what it's doing is it's populating the stack, it's pushing into the stack in a way where the, you know, the letters that come last in the alphabet are pushed onto a first.

Contrarian Burrito: Yes. Right. Okay, that makes sense. So, I think I think this is a fine way to do it. Okay. There's also another algorithm called cons algorithm, which I personally find is easy to reason about, but if you're familiar, and can, I'm more comfortable with this method, that's also fine. So it's up to you.

Teflon Artichoke: Okay, it's called a pons algorithm?

Contrarian Burrito: It's called cons algorithm.

Teflon Artichoke: Cons. Okay, but I was just thinking, I would definitely check that out after this. But okay, so let me before I get to the TPS function itself, I want to see in the public function, or the determine language functions, or what else I need to do here. So I would perform a topological sort on the graph. Okay, so that means I need the let's first create these. So that's going to be empty initially. And actually, these should all be passed by reference, by the way. Okay. So I think, and this is reversed order. So I think the idea is I would loop over my looping over here. Oh, okay. Well, I guess I'm looping over the graph itself. So I set the iterator to the beginning of the graph. Well, it's the case that we're not at the end of the graph. We're going to do something special. So excuse me. So all that we're doing is we're checking if we've already visited this character. So that would be it is I think we can say it first. Yeah. So if that if that gives us the end of the... wait a minute, what am I doing here? It's visited cards. Okay, right. If I think I just need to call I think I need to be calling the find function here, not the not using the square brackets. And because it first is going to give us the character itself the key of the graph. If that takes us to the end of the graph, that means we haven't done anything with it, which means we need to call TPS with it first. Graph visited chars and reversed order. Okay, else we're done. Last thing we do is okay, so when we have this, right, the earliest characters in the language would have been would have been pushed to last because we traverse it's children and then once we're done with all the recursion, we finally get to the early the first couple characters in the language. So that means while the okay let's initialize return vector that means while the lots of case that reversed order is not empty, while that's the case, we're going to my indices are always messed up here. I must have offsetting parentheses somewhere in here that's making it throw a fuss. Okay, so while that's the case, we're going to push back and return vector. Are we pushing back we're going to push back front or top I think of stack. And then we're going to pop. Call the function here. Okay. And then lastly, we would return the vector. So other than the fact that I haven't implemented the topological sort of kind of things, you kind of seeing the way I'm going here.

Contrarian Burrito: Yes. So just to double check. You initially... Okay, yeah. I think that makes sense. I'll keep looking at it as you implement the the topological sort.

Teflon Artichoke: Right. Okay, so what I'm doing here is, okay, I think I first need to... Okay, um, I'm wondering first, do I push into the visited characters? Do I first push into this? I think that would make sense. If so, what I'm saying here, so. So visited... Chars, push, insert, and then I do curr char. And actually, why don't I pseudocode the rest. So I'm not just spitballing ideas. So you know, iterate over curr chars. You know, children, which is the set that maps to in the graph. And every child of curr chars, what are we going to do? If okay, if visited chars isn't... if we haven't visited child... We haven't visited child, we're going to say...

Contrarian Burrito: Sorry, can I interrupt for one second? Yep. The determined language function. Can you tell me what visited chars? Explain like, line 61?

Teflon Artichoke: Oh, right. So the point you don't, so I don't want to be... I know that some of these characters will have shared children. So the idea is that I don't want to duplicate. You know, when I visit indicee, the, excuse me, the children of a given character for the first time, I want to sort of do all the work for that particular character in that recursive call. And I don't want to ever in that way. So in that way, like even here, I'm checking have we already done the work another way of saying, Have we visited the child has have we done the work here already? Because I mean, let me let me just let me check.

Contrarian Burrito: Oh, sorry, go ahead.

Teflon Artichoke: No, I was just gonna say, maybe I can walk through an example of what I'm planning to do here with the inputs. But like, okay, I mean, I mean, that's something I could do. Yeah. Should I just try to maybe walk through an example? Like, simulate?

Contrarian Burrito: Yeah, I guess. That's the part that I'm confused about is we are looking like basically what line 61, we're iterating through every single element in the graph, right? But in like an arbitrary order.

Teflon Artichoke: Yes. And yes, yes. Oh, once we do that. Okay, I think I see you're quite confusing that I'm, we're iterating through and then we're checking. Have we already iterated through this at this point yet? Is that is that the confusion?

Contrarian Burrito: Yes, I guess like what I'm visualizing is in the graphs, you could have a node that has incoming edges and outgoing edges. And that could be the first thing that we start with. And so your, your algorithm would be running the topological sort on that point, and then probably marking those as visiting stuff, and then returning to maybe the root of the graph at a later point, right. Is that how I'm understanding it?

Teflon Artichoke: Yes, yes. Okay. Okay. So, let me think about this. So it is it is a problem if we mark a... Okay, it is a problem if we did... what was I'm sorry, can you explain again, what you meant by the node with incoming edges and outgoing edges.

Contrarian Burrito: Okay, I mean, I also might be misunderstanding something here because to be completely honest, I'm not used to seeing the recursive algorithm. I am familiar with it. But I guess I just want to make sure that I'm not suggesting you to do something if you're doing it correctly. So I want to make sure I understand your solution. So iterating from line 61, you're starting at, like, I'd begin. That's, I mean, graph is just an unordered. map. So but it could be any node, right? Yep. So it could be one that is just in the middle of the graph somewhere. And that has both incoming edges and outgoing edges, right? Yeah. So basically, if I understand this correctly, when you are initially checking, like when you first start off with algorithm with the very first element that you pick in this in line 61, it could be something that's like in the middle of the graph, isn't it? Yeah, just in and out. Yeah, at that point, you run the topological sort.

Teflon Artichoke: So I, you know, I still think that actually, my approach would make sense. Because in that case, because we only care about the, we really only care about the outgoing edges of that given node, because we will because want to make sure we push those to the stack before the given node. Now, any node that has an outgoing edge to you know, the place where I'm iterating at, I mean, that will be pushed that, you know, we know for sure that that's going to be pushed to the stack, after the call this recursive call, because at the end of this recursive call, we're going to push the current character to the stack. You know what I feel like I'm sort of I maybe I'm not being super clear. Do you think I could maybe drop map out the TPS a little bit the helper function a bit more? Sure. Yeah. Yeah. Okay, so we haven't visited child. So right, then I'm just define the child. And once we're done recursing, on everything, we will. Will we remove? Okay, so we'll definitely add current chart stack or push curr char to stack but is there anything else we need to do? Actually, I think this might be a lot of it. So before, so actually, can I take this time to to actually run? Is my algorithm or run what I'm thinking this will do? Yeah, just just just to verify that, especially the TPS part, because even I'm like, not super sure about this. So. Okay, so what would the graph would look like this, we would have I mean, if add to graph is working correctly, the first, the knowledge we get from P from these two is that P comes before E. So I would say P, E. Right? Okay. So this is an... The next thing tells us that U comes before B. That seems right. D comes before B. And what is the next observation we're going to say that to B comes before K. The last thing we say the last observation we make is that P comes before U. So does it make sense how I got this as my adjacency list. This would I mean, this would technically be like a bunch of characters, but because it's such a small graph, it just happened to be one to one. Yeah, okay. So, okay, so right now the stack is empty. And what else? What else do we need get reversed order visited characters as empty? T. And that's it. So, okay, so we're iterating. But let's assume that we're remember in this in this recursive call, in this first call to the recursive function, we're iterating over the graphs, let's assume we're iterating over the graph. Let's pretend it actually worked in sort of, like 01234 here. So the first thing we're doing is we're checking if P is in the graph, if we go, and that's specifically happening in line 79. The first time it's not. So that means we're going to pass P into this recursive function. And we're when we arrived here, so curved char is P. And so for every child and curr chars, every child of curr char, which is just B, we're gonna if we have an if we haven't visited the child, we haven't visited B, so we're going to recurse on child, okay. Now, Oh, and by the way, we pushed, I meant to say we pushed P into visit characters. Now we're going to push... now because the call stack, I'm just going to make the new curr char underneath it, we recurse down the single child, which is B. So for every child of B, which is K, whoops, and also we populate B into visited characters, so for every shot of B, which is just K... Oh, shoot this, U should have been here, I just realized I was just wondering, where's Ks? I'm sorry, I'm all over the place here. But, this is what the dictionary should look like, is that I'm sorry. Yeah, or the map should look like, okay. I thought something was off. So curr char B. And now we look at, now we recurse on these children, which is just K. And we recurse. Any, we push k into this, and will. And recurse, on K's children, there's nothing to recurse on. So that means we push K to the stack. And now we go up one recursive call with recursion, all of these children's were pushing B to the stack. And now we go to P, and we just recurse on B so now we recurse on U. And oh, okay. So I see an issue here. Yes. Okay. So we're not really taking into factor the fact that U comes before? Like, I mean, what I'd want to say is let's recurse on.

Contrarian Burrito: I think that's fine. As long as you know, when you're at U that you already visited B.

Teflon Artichoke: Yeah, I mean, okay. I mean, maybe that's the point of... Yeah. Yeah. So it's okay, if we, if one of our child nodes is one that we visited, because if you visited already, that means we pushed it to the stack, right. Does that mean

Contrarian Burrito: Yeah, so on line 54, that works, because once you've visited B, and push it to the stack, mark that as visited, so basically, when you're at U, at that point you don't have any children.

Teflon Artichoke: Yeah. Yeah. Okay. Okay. So that means and then yeah, that means we can push U to the stack, because we recurse on U. But I mean, we recurse on U's children, but more specifically, we recurse on the non visited children. So there was nothing there. And the last thing we would have done was pushed U to the stack, and then returned to this first recursive call. We've iterated on all P's children. So we're going to push P to the stack. And you know, after in the main determined language function will reverse this and we'll get P U B K. That becomes P U B K, and that was the output that U requested. Does this make sense?

Contrarian Burrito: Yes, that logic makes sense. The part that I still, at least mentally I'm not clear on is what happened is the order of the like, sorry. Like, what is this something like this? And you started with U. Would that still work? I'm not sure that I'm not sure that it will. I don't think it I'm not sure whether it's correct or not. In that case, it might be. I just started to work through it.

Teflon Artichoke: Yeah. Wait, sorry. What was what? What was what's different here if we started with U?

Contrarian Burrito: Yeah.

Teflon Artichoke: Okay, um, well, wait, this is a loop. Well, this is a problem, right? We can't have. You're saying B comes before U. And then... Oh, I see. I see. Okay, this isn't necessarily a problem.

Contrarian Burrito: It's in like... This assumes that the way we went to this problem, we know that we started out with a letter that's at the very root of the graph right.

Teflon Artichoke: Yeah. Oh, I see. I see. Okay.

Contrarian Burrito: It might work actually. I'm not sure.

Teflon Artichoke: I mean, and are we sure this and are we sure this is like a valid input? Wait, no, it would. It would, because here's what would happen. We would recurse first on B, right? B, we would first... Yeah. Because we're recursing on its children, and we're recursing on this first right not the U. So what would happen is we would, you know, I guess we would, we would recurse on B which means we recurse on its children K you know, whatever. So now we push K to the stack, then we push B and then we return and then we and then we recurse on U. So the I mean, the fact of the matter is that I still think that the children nodes all children nodes are being pushed before they're right. We would have pushed B before U in that case. That and that fits with this be should go before you right?

Contrarian Burrito: Yes. Wait. Okay, I see eventually get to. Okay. Yeah, I think that makes sense.

Teflon Artichoke: Yeah. Yeah. Yeah, I mean, I mean all the recursing here, we just want to make sure. I mean, we want to, we need to make sure that no matter what happens here that B is pushed before U on the stack.

Contrarian Burrito: Yes. So eventually as you iterate through every single element in the graph, you'll eventually hit the root node and then at that point, you'll populate it. And then if you start at some node in the middle of the tree, then you'll like regulate that tree, but then you have to start back up from the root node at some point. And then you'll see that that node, like whatever the starting node of that has already been visited in this subtree is...

Teflon Artichoke: Exactly, exactly. Okay. Yep. Yeah. And yeah, I mean, that was a good way of saying it, like, you can think of every node as the root of its own respective tree. And, and so anything that comes below the tree will be called covered in that recursive call. Anything that comes above it will become will be covered in the next recursive call. I'm sorry, I did I just say next twice. I meant an okay. All right. But I think if you get the picture, I'll just, I'm gonna go ahead and finish this. I hope there's not too many compiling errors here. Should I? Should I try run it?

Contrarian Burrito: Yeah, that's fine.

Teflon Artichoke: Okay, can't wait to see this. Okay.

Contrarian Burrito: C++ is a gnarly language for programming interviews. It's rough for interviews. It's a lot of mental energy to...

Teflon Artichoke: Yeah, I mean, it's my first love the side of it sorry with the language I learned all my CS classes in. And so it looks like the problem for one of the first problems here is that I need to include a libraries unordered map. I'm going to say unordered. Else here. Okay, so that should take care of a couple of... Can I clear this? Let me reset. Still a bunch of stuff. Okay. Okay. Wait. Oh yeah...

Contrarian Burrito: Do you mean like a using STD or does this...

Teflon Artichoke: I mean I think that's an issue but okay. So strange stuff. Okay, so it's actually seeing it okay. Yeah, just helped me to string. So... Oh, maybe it's because maybe it's because... Am I implementing the right one more time? Oh, oh, I see what you're correct in saying that using the namespace definitely makes a difference because you would otherwise have to do. So let me reset this. Okay, okay, this is we're already working cooking with fire here. So what is in like your we're using an long unsigned int? Oh, maybe I can just define it as such kind of integer expressions. Yeah, let me just define it as such. And okay, what else? Oh, I didn't declare a stack. Okay. And inside the stack include the stack class. Also the vector. Okay, as you can see, I use too much LeetCode where they do they hold my hand too much. Wait, let me reset this. Okay, so there's almost a... Yeah, let's see. Okay. Do we have time to maybe run some test cases? Because I just want to run maybe though. Yeah. Okay. So let me at least run this one. I want to run at least this and the empty one. Just empty. Just just to get those two cases covered. So how about this? So we'll say the words right. Words equals to this. And this thing I'm implementing... It's not gonna like that. Okay, I'm just gonna do these each one manually. Sorry, words. Okay, pythons looking really good right now. Okay. I'll do it this time. Yeah, okay. Got it. Okay. All these needs semicolons. Okay. And then I'm going to call my initial function here. And so we'll just call it return vector is what's returned when I determine language words, then right order... Okay, let's give it a PBUB. Okay, we have a couple of extra characters for sure here. Um, so did I not? Why am I adding extra characters here? I mean, not my...

Contrarian Burrito: One thing in your graph function and see if you can identify any issues there.

Teflon Artichoke: Okay. Yeah. So, right, it makes sense, iterating across both strings. And what's the case that we're looking at the string, same strings are gonna add? If this index was less than, I mean, there's an enclosed in bounds for both words. Maybe the issues here. So does it make sense that... Oh, maybe the earlier word in the library? Should I be switching this up? Should it be? Right?

Contrarian Burrito: Because I guess think of when your functions start adding things? Like when does it?

Teflon Artichoke: Oh, right. Alright. Okay, so. Okay, so we need to, I think maybe we have the edges look a lot different than I think we do. So it does. So. Okay. We could be pushing. I mean, is it possible that we're, is it possible that we're pushing values twice to it? No, no, that wouldn't be the case.

Contrarian Burrito: Look at for example, compare, run me through what would happen in this function, when you compare the first and the second word?

Teflon Artichoke: Yeah, like PBB and PBKU? Okay. So we're looking at zero first. P and b are not, we would actually make this, we would first look at this index is less than that. That's fine. And index is less than two. That's fine. And this condition is not met. So that's problem. So we would immediately go here. Are is the index still in bounds? Yes, it is. And we're going to say the graph at index is always zero. So at graph at zero, at W one zero is we're going to insert... Yeah, I mean, it looks fine to me.

Contrarian Burrito: Right, what happens after we insert.

Teflon Artichoke: After we insert we would, we would return

Contrarian Burrito: Do we ever return?

Teflon Artichoke: Right, like after this?

Contrarian Burrito: Yes.

Teflon Artichoke: I think we returned because I don't see. I mean, there's no code here. Right? It's it's not. It's not some big while loop. I mean, this is what I was doing was just a fun way of saying that. What was that what you were confused about? Maybe?

Contrarian Burrito: Oh, is that incrementing?

Teflon Artichoke: Yeah, yeah, that does the same. Yeah, so this is probably still gonna give me the same thing. Yeah. Okay, but it looks like I'm basically I'm not marking characters as visited. When I should be... okay. Oh, wait a minute. Oh, wait, this should if we haven't visited this if means is it okay? Okay. PBUK. Please tell me that's what we said. PUBK. Yes, yes. Okay. Wait. Awesome. Yeah.

Contrarian Burrito: That makes sense. That makes sense. Yeah. Okay, I'm hearing that's my bad.

Teflon Artichoke: No, no, yeah. Okay, real quick. Can I talk about time complexity? And actually, can I also just try to push seeing what happens when I push nothing to this language?

Contrarian Burrito: Sure. Yeah. I'll give me some time because you spent time on that red herring, so I'll refund that for you.

Teflon Artichoke: Okay. Okay. Yeah. Okay, so I what's the issue here? Oh, well, that was one and let's... And what about if we just have one word? I don't. I think the one word situation should be fine. I'm still running. Okay. The one word character should be fine. It's just going to give me the order that it was... it's still running. Oh, I think, Okay, I think, Oh, well, this is kind of a weird case. Okay, so what happens is it didn't add anything to the edge, it didn't add any edge to the graph. Okay, so this is kind of an interesting kind of rare case where the last, so I guess what I would say is, the last thing I do is, you know, for, I'd say, okay, this is what I would do last, I would iterate over all the entirety of a graph. And for any node that wasn't in visited nodes, I'm going to push that arbitrarily to the returned vector, those characters, we don't it doesn't really matter where they go, I'd say, does that make sense? And that's the case with the one word so. So for so how do I, if I had?

Contrarian Burrito: Okay, well, I guess no one would want to return they want to make sense there.

Teflon Artichoke: Yeah. Oh. I mean, what I'm what's happening is I'm returning an empty vector. I mean, I could just, I could just return an empty word, I guess if the word size is one, okay. So if... So, I'll initialize the return vector actually at the top, so I can return it right at the beginning if I need to, so if you know word size equals one, or words size equals zero, return vector that's in short of hedge my, those edge cases there. And now we're, oh, shoot. Now visit, these are two different examples. If word size equals one, we're going to we're going to just iterate over the word.

Contrarian Burrito: I think that was correct, because when you have one word, you also don't know anything about the language. Right?

Teflon Artichoke: Okay. Okay. That's what I mean. Ideally, we would just, yeah, I think ideally, you would have just put the words in the order that they came in that particular word, but because it is a valid solution, but yeah, I mean, but you also said, Wait, you didn't we also say that? Sorry, go ahead. Go ahead.

Contrarian Burrito: In other words, if you have a single word, then you really don't know anything about any of the letters, I guess, because... Yep, yeah, I have a word like CVA. But that doesn't say that C comes from or V. So I think I only have makes sense.

Teflon Artichoke: Yeah. Oh, did I not change it back? Yeah, well, no. But for I mean, this was important. The word sizing, the checking for it, the word size is empty, because the code was breaking before. Let me make sure it's not break when I pass an empty vector. And now that I want to make sure that it's doing what it should, which is just returning empty vector and not break. Okay. So yeah, I think this is working exactly the way I'd like to I think so long as the conditions are, that there is a valid solution that includes all characters, and only one solution, this will definitely work all the time. In a case where there's multiple solutions, we could return great examples. That is what he pushed one word where any of those characters could come first. You know, it's, it's not probably. But yeah, so and but time complexity wise, I would say that, let's go across, let me go down to the, the code from line 73, constant time operation constant, constant, and then we're going to iterate over each we're going to iterate over each words, it's going to be O(n) with respect to words, and we're in that we're going to make a call to add to graph add to graph is just okay, add to graph is going to take as long as the longest word in words. So go running back to line 86. The Loop itself is O(n), where n is the length of words and add to graph is O(l), as I said in the brute force explanation where L is the length of the longest word. So overall, actually, this is O(nl). Does that make that make sense?

Contrarian Burrito: Sure, Yep. Yep.

Teflon Artichoke: Because add to graph is going to right, go down, iterate across the longest word, a couple more constant time operations. Then we're going to iterate over graph graph could is going to be as many as long as there are unique characters in the language. So I think I used O(m) for that last time, where m is the number of unique characters in this language. We're going to call t each time we're calling TPS and TPS. TPS is also iterating. Well, the work of TPS is done in in parallel with this for loop, because we're using this visited, we're always making making this visited cards check, as in have we already done this work? So in theory is that is also going to be O(m). But because that work is done in parallel to this loop here, the the overall loop is still O(m) because I mean, you could look at this block of code as in, we're just visiting every character. Yep. Okay. Every unique character, while reversed orders, empty, reversed order could have is going to have again, O(m), m being the number of characters and a constant operation at the end. So this is going to be this is going to be of O(n*l+m). Well, yeah, this and given that. Yep. Space wise, it's going to be let's see, the data structures are returned vector, that's going to be O(m), the graph is going to be O(m), yep, and another O(m) stack. Okay. So that's going to be O(m), where m is the number of unique characters in the language? Yeah. All right, this off the top of time is of m times L, M times L times m and spaces linear with respect to the number of unique characters, the O of m. Okay. And that's, let's see about that. Cool. Anything else you like? Yeah.

Contrarian Burrito: So we're running short on time, but I want to at least, sort of have you think about the extension questions that I like to ask him on top of this question. So I'll just say them, and then you can think about them on your own or something like that. The first one is detecting cycles, which is pretty obvious. You probably heard of that one. So I just but I think the ones that are more interesting are given, let's say you have this problem now with a very large input list. And a reasonable number of characters, but like a lot larger, but listen, like, many gigabytes in size. Yeah. How do you solve this problem? In a multi threaded fashion? That's one of the extension questions. And the second one is, if you have an input like this, we have a piece at the bottom. What sort of output would you want? And then how would you implement that solution? So those are the two.

Teflon Artichoke: Okay, and do I get to choose which one?

Contrarian Burrito: Oh, I'm, usually I asked them one after another. But I guess, given the time, they don't have that much time left. I'll leave those to you as an exercise for the reader.

Teflon Artichoke: So that's what I thought you were saying. Okay. Yeah. I mean, for the first one, I guess, using multi threading, so that means we need to have certain race conditions. Okay. So yeah, I'm glad you were leaving that as a as a problem for the reader because I actually need to catch up on multi threading, I don't know much about it. I know that there's something called race conditions. I know that I know what else I know that dead lock live lock, right? It has to do with having multiple CPUs set out to do tasks, and the CPU, the computers will interact and say, you know, I'm covering something. And so before a computer tries to do a certain task, it'll check if it's currently being performed. And that flag is set, I think is called the, I forget, but so how would that work here? I don't know. But how about this, how would you design your solution to handle this case? Why is this different this is different because A, B, C, D, E, F I mean how is... That would be the ideal output of this. Okay. I assume a, b, c, d e f. Why? So I don't understand that's putting a spin on it, though. I mean, I guess what they're saying is we could have also returned like A, D, E, F, B, C, or D, E, F, A, B, C.

Contrarian Burrito: This is how I see this because you don't know anything between.

Teflon Artichoke: Oh, okay. Okay. Okay. Okay, so the question is, okay, we're, this is different, because we're saying, like, only, you know, what should be including your output is only what you know, for certainty. So don't put C before don't put D before A if you don't know, it necessarily needs to go before it. Okay. Ooh, that's interesting. So what would I do there? I'd have to group characters together, which we know anything about their relation. Okay, but it's not just grouping together characters that have relationships, it's characters that I mean, not just...

Contrarian Burrito: For the second one, I think it's just splitting up the input list into many different shards and then having different threads processes. So it's not super complicated, but it is a little bit what you do in a multi threaded fashion.

Teflon Artichoke: Yeah, yeah.

Contrarian Burrito: Yeah, sure. I think sometime at the end. Also, I want to make sure I can answer any questions you might have. So yeah, I mean, if you have any questions as well?

Teflon Artichoke: No, I don't want to take too much more of your time here. But I think I mean, I think I'm all set. I mean, I'm very eager to hear what you have to say. I did have one question, actually, I'm sure you mentioned that you work at ----. The new grads, software engineering roles normally come out in October, and I actually heard that it might be coming out in January, it's been delayed, usually delayed, due, you know, off the top of your head if it's actually coming out soon, just the undergrad, new grad role.

Contrarian Burrito: So okay, in my experience, December is sort of the... Yeah, it's sort of a bad time, because you don't have as much headcount. And I'm just speaking from my own personal experience. I'm not sure about this. But I imagine now that's January or so, you might start seeing more openings for headcount. But again, as with the pandemic, of I really don't know how that affects. Okay. Okay. So yeah, I would say now is a better time then, like end of quarter four, which is like in December.

Teflon Artichoke: So maybe, yeah, well, no, because they're releasing, like the internships now. So it makes it like, as of today, they released two new grad roles that were like in, you know, for network engineering or something. So I it seems like they're, they're ramping. They're opening up the university rolls. But anyway, you don't know for sure. That's fine.

Contrarian Burrito: Yeah, I'm really not sure. All I know is that I did refer some people with like, really good referrals back in like, end of 2020. But they didn't even get an interview. So it doesn't make sense to me that I think it's just a headcount thing strictly. So I would imagine that it should be better than New Year, but I'm also not sure what our plans are.

Teflon Artichoke: Okay. All right. I'll keep on keep hope. I'll stay hopeful. But yeah. Can we talk about the feedback or you just want to read that?

Contrarian Burrito: Yeah, usually, I I just write it up. And then you can, I guess, take it later. I would say, just to summarize, I think one thing that I found, is that the speed of implementation, like it's clear to me that you know, you familiar with the solution of this problem. And so I would expect, so... Oh, well, first of all, overall, you did a good job, like, this is good code. It worked. I mean, that's like the main thing. So I would say if if I were to grade you on an interview, you would have passed. I think if you want constructive criticism, instead, I would focus on are implementation speed. And I guess, I don't know if, for example, one thing is that notice that you write a lot of comments and like to talk to a lot of your code as you're writing it. I don't know if you're doing that simply for the sake of the interview. But for me, I don't necessarily like it does help to have comments, but I think the amount that you had, was more than I than I like look for, in the sense that it doesn't. Okay, but it doesn't necessarily better for me to read the code, I guess, because I'm very familiar with the problem. So if it does speed you up to either write fewer comments, or, I guess talk less while coding, I would say that's perfectly fine to do. Because, Okay, that's good to know. Yeah. If it helps you of course, don't don't start doing that. I think you know, no, no.

Teflon Artichoke: But no, yeah, it's no, like I am doing it because I feel like that's what's expected. But clearly I'm going overboard.

Contrarian Burrito: Yeah, like, I think it's fine to write, say, before you write a function, say, Okay, this is what I plan to do, like this function will do this, and then just write it up without talking and then quickly. Okay, okay. And so yeah, that would save you some time.

Teflon Artichoke: Okay, for the helper functions, I really felt like, I was like, I wish I could just code this out. But I have to stop and pseudocode this out first, and then like, okay, so it's good to know that you were thinking that that's not necessary.

Contrarian Burrito: I personally found that you don't need to do that, as long as, as long as you and the interviewer both know what you're doing prior to you starting to code. Like, for example, when you tell me this function add to graph, I'm going to iterate to this, add the elements to the map. And then that, I think after that, as long as I'm like, Okay, sounds good, then you can just code without having to talk to each one. And then at the end, you can quickly summarize like, Okay, this is what this function does, which just makes sense in an interview, because like, I don't know, if I if this does what I want, or that looks good, and then you can move on. Okay. personal opinion on it. Okay, there. Yeah, I guess like, I don't know how familiar you are with Python. But in general, I would say, as a general interviewing tip, I think I find that people who are interview who work in Python, generally, on average, have the best chance of passing just because they spend a lot less time thinking about stuff that you would have to do in other languages. So it might be a good investment, obviously, if you have an onsite coming up to do what you're comfortable with, but sort of for the longer term, I think Python can be just a general help for speed and stuff.

Teflon Artichoke: Yeah, I know that I need to get much better and much quicker. But okay, yeah, I'll definitely take that into account. Okay, I feel like I had one more thing I wanted to say maybe I'm all set. Oh, like, was it? I mean, we, we went kind of long. Do you think? Do you think that normally, they would have cut me off or something?

Contrarian Burrito: Oh, yeah. If it's a real interview, I will make sure to push people faster, or give hints to... Well, I guess for you, you didn't need to enter because you're familiar. But generally, if I find that people are taking too long, I will give more hints to accelerate the progress. Or just, you know, when there's five minutes left, like I guess that 55 minutes, I'll cut them off and say, Okay, this is good for now.

Teflon Artichoke: Okay. Yeah. Oh, okay. So I mean, like I was, I think I was within an hour. So okay, I thought I was wondering if this was a question that was meant to be done in 30 or 40 minutes. And the fact that I was, you know, 15 minutes over 20 minutes over that. Okay.

Contrarian Burrito: This is a tough question. And especially it's okay for people before. I like so my criteria for passing people is, if they get working code, by the end of the interview, I would generally say that the pass like, sometimes I do give candidates an extra five minutes if I think they're really close, and they can just finish it within that time. And that, you know, I get bonus points if they're able to get extensions and give good reasoning about them and even code it, but that's not necessarily an expectation for me, but it depends on the person also. I'm not sure. I can't say I speak for everyone.

Teflon Artichoke: Yeah. Okay. Okay, great. I really appreciated this. And I definitely love to do another interview with you again, if I mean, if I... This will be the last one I do before Apple, but I really think there's a new application opening soon, so I'll keep you... Okay, thanks. Yeah, do that.

Contrarian Burrito: Yep, sounds good. And good luck on your interview. I believe in you.

Teflon Artichoke: Thank you very much. Thank you. Appreciate it, goodbye. Have a good one.

Contrarian Burrito: Yep. Bye