Alien Dictionary Problem (Python)

Watch someone try to solve the Alien Dictionary problem in Python with a software engineer from Google. Explore this problem and more in the world's largest library of mock interview recordings.

Interview Summary

Problem type

Alien dictionary

Interview question

Derive the order of the letters given a list of words

Interview Feedback

Feedback about Mighty Burrito (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem solving ability?

1/4

What about their communication ability?

4/4

Rock solid! Was able to quickly grasp the problem, code it up correctly, explain runtimes, and make small optimizations.

Feedback about Intergalactic Avenger (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

2/4

How good were the questions?

4/4

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

4/4

This was a pretty good interview, I like the question. I had heard of this question before but I haven't solved it or heard the solution. I was able to figure out the general algorithm (use topological sort) pretty quickly but there were still difficulties in actually implementing.

Interview Transcript

Mighty Burrito: Hello?

Intergalactic Avenger: Hey, how's it going?

Mighty Burrito: Hey, pretty good!

Intergalactic Avenger: Alright, so. Without further ado, I'm just going to jump right into a little algorithms question if you're up for it?

Mighty Burrito: Sure.

Intergalactic Avenger: The code isn't actually going to run as I have envisioned it, but it still might make sense to use a real language, so if you want to pick on of the languages they support here?

Mighty Burrito: Sure. Alright, I've done Python.

Intergalactic Avenger: Okay, excellent. So, let me know if you've seen this question before. The idea is that you're going to be given a dictionary of words. Not english words, they are words of some magical other language that orders their letters differently than we do. So you're trying to deduce what the order of their letters are in their language, given that you're given a list of words that are sorted alphabetically. So, I'll give you a hint, just to use as an example here. If their alphabet is the betters B, F, G, Q and you get a list of words that are sorted in this magical language. So, there's a couple of different parts to this question, but I just want to make sure before we get started that you understand the basic concept.

Mighty Burrito: Yeah, makes sense.

Intergalactic Avenger: Okay, so. The kinds of things that you can tell from this list for example is, if you look at the first letter for example, obviously B comes before F comes before G. You can tell that just by looking at the sequence. But then after that, it gets a little bit tougher, You have to figure out, well where does the Q go? And you can see for example that FBQ comes before FGF, so that kind of gives you some hints about where it all is. So, the first step is that I'd like you to build a graph that has these relations in it. So, essentially the graph will have nodes where the nodes will just point to another node that it is in front of. Let's just say that we have Class g for graph, and it will have as its functions like add() and...

Mighty Burrito: What's c1 and c2?

Intergalactic Avenger: These are the letters that you have. So if you said add(E,F)

Mighty Burrito: Oh yeah, I see I see, sure.

Intergalactic Avenger: And that is basically an edge. You can remove() an edge. We'll say outgoing(), so that's all the outgoing edges from a given one. And incoming(). Alright, so given all of this, we start by coding up something that will make this graph and encode all of the relationships between the letters.

Mighty Burrito: Sure. So, I guess the rules are just generated by if you look at the characters. So if we look at the first character, we're basically just given that B > F > G. We can also tell that B > G as well. If all characters before the given character are the same between two words, then we know that the next character we can use order the two characters. That makes sense. Sure. So, let me just think really quickly about the most efficient way to do this. So I think... This is going to vary a lot of edges per the requirement. Let's see. I think the best way to do this is recursively, and just pass it in the graph and a list of words to process. And these leader functions will take in a bunch of words. I can either pass in an index or I can pass in a sub-word, and it's going to be better in this case to pass in an index, more efficient. So this will add all edges in the list where all characters before index are the same. So the base case would be processWords(wordList, g, 0). And the passing of this sublist isn't really efficient. It's probably better to probably just pass in the original list and a list of indexes, because string copying is expensive. But I will do that later, I was going to make this simple first. So, let's see here. So we can just generate an ordering from this. I'm going to write this kind of inefficiently first, and I can go back and optimize that. Okay, well this isn't a complete function. I'm just going to write out the parts I know I'll need. So basically here, now I have an ordering that I know. I just want to add edges from every character to the characters in the rest of the list. So, I don't want to add duplicated edges, so I'll have to check for that.

Intergalactic Avenger: I mean, you can assume that adding the same edge twice is a no op.

Mighty Burrito: Sure, in that case, I don't even need line 35 then. That makes it slightly more efficient then. That function is going to do this. I could just make that a part of the... So this adds all of the orderings that we know from this. And then we need to also recursive add all the things where the first letter is the same. Let's see here. So we can make a bunch of sublists. So we can say wordsByFirstLetter. And I'll do wordsByFirstLetter... That should be index. Alright, we can do for listLetter in wordsByFirstLetter... I think the way you iterate over dictionaries is... I think you do this, is this right?

Intergalactic Avenger: When you iterate over a dictionary, it just gives you the keys. But, if you say wordsByFirstLetter.values or you can say items if you want the keys and values.

Mighty Burrito: I think I just want values. So this will recursively do that. I think that's right.

Intergalactic Avenger: Okay, so let's work through a couple... Can you just walk through how this is going to work for a couple of these little strings? Or you can even make shorter strings than the one that I've given.

Mighty Burrito: Sure, I'll just use the normal alphabet, it just seems easy to verify. Alright, let me just verify before I run through the whole thing. Let me just make sure it makes sense to me.

Intergalactic Avenger: I think in line 51 you meant to say range here?

Mighty Burrito: Yeah, I think this is actually right. The algorithm looks right-ish to me though. I'll just double check now. So say we have this list. So I'll iterate through all the words in the list. And so for this first one, we call this index of 0. Oh, I need to check the ending clause. Eh, do I? I need to verify that the index is not too high. Are all the words going to be the same length?

Intergalactic Avenger: No.

Mighty Burrito: Okay. Let me think about that really quickly. Okay, so length of a word is less than the index because if the index is one and all the words are two, we still need some. Okay yeah, this is right. So, I'm going to start with this. We add aaa, I should make sure that I don't have an edge here. So this will add aaa and it will also add wordsByFirstLetter[a] and that will have all of the words because they all have the same first letter. And then the next iteration of the recursive function here is going to be called on the same list with now an index of 1 and it's still an empty graph, which is fine.Then this will have abc, so the ordering will have abc, so that will be abc, which is good. We will add, a goes to b, a goes toc and then the next thing i will be 1, which will say b goes to c, and that should be it.

Intergalactic Avenger: So a question I have here, you're adding a to c, is that necessary to add. Or can that be deduced by something else?

Mighty Burrito: I mean, no not really. I was just adding the complete graph, because we know that by... I don't remember the name of the rule. Because we have a to b and b to c, we don't need a to c. Because we're eventually going to be doing a topological sort on this.

Intergalactic Avenger: Right, yeah, okay. So you see where I'm going with this? I think transitivity is the word you're looking for. So a to c is as you said, kind of redundant information there, so how about we get rid of that, because that will sort of speed things up a bit, and make our list a little bit smaller.

Mighty Burrito: Let me just think about this really quickly. Yeah, that should be right.

Intergalactic Avenger: Okay. So. How many copies are we making here of this list?

Mighty Burrito: Yeah, so I guess that's the other thing I was going to do. So really what we should be doing is we should be passing in another list. We should have a main list of words and we should really be passing in indexes for the second thing. Does that make sense? Instead of appending these things to the actual list, we can just append the index. We'll want to do. There's a better way to do this it feels like. I forgot the Pythonic way to do this, I can just do this the other way. Does that make sense?

Intergalactic Avenger: Okay! Alright, so we have lists of indexes into the word list. And what are you passing... Wait, so. Hold on a second. This is missing a parenthesis I think.

Mighty Burrito: Oh, yes, you are correct.

Intergalactic Avenger: Okay, so this is the array, this is the list of subindexes. So this is indexing the entire list. And that's index... Ahh, okay. And then the next subindexes is going to be this wordsByFirstLetter? Oh, if this... And the values of that... Alright, that was good. Okay I see that you've already looked into the crystal ball and realized where the next step is in all of this, and you've even said topological sort, so sounds like you're ahead of the game there. So, that is the next step. So given this graph, which you just made, can you pull out the letters in alphabetical order?

Mighty Burrito: Sure, so I guess the easiest way to do this is to find the node that has no incoming edges, remove that, and remove all of those edges from that node, and then recursively do that. I probably want to store the number of edges to each node. Otherwise I'm going to have to loop through that entire array, when I can just put all of this into the heap.

Intergalactic Avenger: Alright, I guess I did leave out one thing that you're probably going to need.

Mighty Burrito: Yes? So, here I am going to recursively get the node with... Oh actually, let me not do that. Okay, so I need to find the one with no incoming edges first. So we just need to find the first node that has 0 incoming edges. I'll do that first. Can I get an isEmpty() function on the graph?

Intergalactic Avenger: Sure.

Mighty Burrito: Okay, cool. I guess I might not even need that. It's probably not necessary. I could actually check if the 0 is None, which is probably safer anyway. Wait, I still have to output the list.

Intergalactic Avenger: Yup, sounds good.

Mighty Burrito: The nodes have a value?

Intergalactic Avenger: Um, so. As I was imagining it, these are actually just characters that it's going to give you back. Or strings of length 1 I suppose.

Mighty Burrito: Oh, okay, sure.

Intergalactic Avenger: So, they're kind of like the ID for the node.

Mighty Burrito: Sure. So if there are ever remove a node and there are now multiple 0 going to it, it means that the list is not well defined. What do you want me to do in that case? Error? Or just pick one?

Intergalactic Avenger: Just pick one arbitrarily. That's exactly right, it's not unique. Sometimes you might have more letters than you have words. There's no way to tell in that case. So just one of the possible correct orders.

Mighty Burrito: Okay, I'll need to store the list of 0 nodes then. Does remove() in Python return the element you remove?

Intergalactic Avenger: Um... Yeah, so remove() actually... I think it just returns a null. remove() actually is actually probably not what you want. Because remove() looks for the character, and removes that from the list. So I think what you want is pop().

Mighty Burrito: Oh, okay. So there's a pop()method.

Intergalactic Avenger: And, it's funny, because basically it removes the element at the given position. So it's not really like popping the stack in a sense. But, well...

Mighty Burrito: Oh, wait so pop takes an index?

Intergalactic Avenger: Yeah.

Mighty Burrito: Oh, okay.

Intergalactic Avenger: Yeah, it's funny. The naming is a little bit weird.

Mighty Burrito: So does pop() actually return the element too?

Intergalactic Avenger: Yup. Yeah, I have to remind myself. I was actually just looking at the Python docs right now. It's a funny one.

Mighty Burrito: Let's see. I think that's right.

Intergalactic Avenger: Alright, excellent. That looks very good. Cool! So, really quickly, what is the runtime of this whole process here.

Mighty Burrito: Sure, so the whole alphabet is pretty simple. This should be, let's see... So we do a pass over it. And then we do remove(). remove() is going to be called once for every edge. So that would be O (number of edges). The total cost of number of edges is equal to... So that would be the case where you actually have every single... It would be this original loop if I had i*j and you had the entire alphabet in there. So the length of the alphabet is say Y, so that it doesn't sounds like n. So we would say that it would be O (E) = O (Y * Y). Y is the number of letters in the alphabet. Or at least the number of letters that we see in the words given. Let's see the processWords() function. So we have i in range(0, len(subindexes)). So I guess the worst case scenario is that every single word is the same. And they're all the entire alphabet.

Intergalactic Avenger: That would be a pretty bad case.

Mighty Burrito: So, in that case, we're going to do this function, and then do it again over and over. O (number of words * number of letters). Is that right? I'm not really confident about that. Let me think about that. So, the length of the input is going to be the length of the total of words every single time. The work that we do is going to be the number of times it recursively calls itself, which is Y. So we have N * Y so far. And the work done per function is we go over each word and we do a constant amount of work. This doesn't exactly seem like the worst case scenario. So at the very least, it's N * Y.

Intergalactic Avenger: Where N is the length of the word?

Mighty Burrito: Yeah. Or Y is the length of the alphabet. N is length of words list. Oh, you're actually right, it should be the length of the longest word, not the length of the alphabet. Sorry. I'm just trying to prove to myself that this is actually the worst case. So if we take wordsByFirstLetter... I think this is like... Okay, so actually the rule we know is that we always process each character once, so this is right, this is right actually. So the reason that I know this is true is because we're never going to compare the same character twice. Or more than two times I guess? Does that make sense? So I know it's the length of the word times the length of the longest word.

Intergalactic Avenger: Alright, okay so we have the length of the list, the length of the longest word, and we have the number of letters in the alphabet. So how do we combine them?

Mighty Burrito: So, I guess the simplest way is to combine them first. But, the length of the longest word is strictly larger than the... In the worst case, it's string is larger than the number of characters in the alphabet.

Intergalactic Avenger: The longest word is longer than the number of letters in the alphabet?

Mighty Burrito: If we think about the asymptotic runtime.

Intergalactic Avenger: So in the case I gave above, the alphabet is 4 letters and the longest word is 3.

Mighty Burrito: Sure, sure. I guess, asymptotically, the longest word can be bigger than the length of the alphabet.

Intergalactic Avenger: Oh, I see what you're saying. So yeah. The longest word could certainly be longer, the word is unbounded.

Mighty Burrito: So, I guess in the cases where the runtime is really bad, I'd expect that to dominate over the number of characters. I guess strictly speaking, you can just sum them if you don't do anything smart about that.

Intergalactic Avenger: No, that's it. Alright, excellent. Very well done. It sounds like you almost knew the problem from before, or you definitely knew a lot of the concepts, which was excellent. I only have a tiny suggestion. It's quite minor. It can kind of help make your code look a little bit cleaner, and a bit easier to follow, especially in these kinds of settings. So there's few tricks with Python that, especially having to do with if statements and while statements, like what evaluates to True and what evaluates to False. It's a matter of style, for sure. But, I think in general people like the style where you are sort of minimalistically showing what's happening. So for example, if you look up at the top, Line 43, if len(m.incoming) is 0. Well, actually, that is exactly the same statement as is m.incoming. So in Python, an expression that results in a list or a set, or a dictionary, anything with a size, if that size is 0, then it evaluates to False. It makes it a little bit cleaner to look at. Same thing with this while loop here, like while len(zeroNodes) > 0. That's actually exactly the same statement as this. Another thing is that the range operator uses 0 as it's default first argument. You could just say range(len()). Obviously, these are small things. It's a little more idiomatic to say like range(some number). And in some cases, taking advantage of some of these Python boolean cooersions does make the code a little cleaner and shows a very idiomatic knowledge in Python. But yeah, other than that, very well done. Very quick, correct solutions. The whole thing. I'm very impressed.

Mighty Burrito: Cool, thanks. It was fun.

Intergalactic Avenger: Alright, well. Then good luck with all of the rest of your interviewing endeavors.

Mighty Burrito: Cool, thank you.

Intergalactic Avenger: Alright, take care.

Mighty Burrito: Bye