Python Interview with a Facebook engineer

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

Interview Summary

Problem type

Group Anagram

Interview question

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Interview Feedback

Feedback about Meta Nougat (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

4/4

What about their communication ability?

3/4

Strengths: + TC came up with optimal approach for both problems. + TC wrote easy to follow code. + TC correctly analysed the complexity. + TC wrote bug free code for first problem. Improvement Areas: - Articulation could have been better for second problem. - TC could have more clearly analysed the complexity of first problem.

Feedback about Red Maelstrom (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

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

4/4

Interview Transcript

Red Maelstrom: Hello can you hear me?\nMeta Nougat: Yes\nRed Maelstrom: Sorry for being late yeah. So yeah we will be spending like 45 minutes on coding exercise. I will give you last 10 15 minutes for feedback\nMeta Nougat: Yeah sounds good.\nRed Maelstrom: Cool cool awesome. So yeah, here's the first question. So yeah, so basically, we'll find like, try to solve a couple of coding questions and at the end can share some feedback around how it went.\nMeta Nougat: Okay.\nRed Maelstrom: Yeah. So, this is first question like you have an array of string, you have to do the anagrams together, so to string anagrams of each other, if they have same characters, for example nat and tan, these are the anagrams of each other. Ate, eat, tea these are the anagrams of each other. So basically you will have one single list of string and you have to return the list of, list of list of strings.\nMeta Nougat: Right, okay. Let's see. So, okay, that's that's great okay. Okay, so I think, one, one way I could, I could do this is let's see. So one, one naive approach would be, go, go iterate through strings, iterate through the input, and then create some sort of dictionary where you have, you know, eat and then here. The value would be the indexes where you know, the indexes that are sort of the same same anagram right. For example. So for example, we have eat, then we have, eat is at zero, right? Oh, sorry. Yeah, eat is at zero, then ate was at the third, third index. And tea is a first index. So right. And then yeah, do have the dictionary where you have, like, yeah, at each level indexes with the good anagrams, right? And then same thing with nat. Same thing with bat, right? Bat will only have zero. And then we'll have like, what nat is at four, fourth index, and tan is at the second index? And then we iterate through the dictionary and say, okay, like, for each level for each entry in the dictionary, append a new, a new sub array, like not a new subarray but like a new, yeah, append an array to, to the array, like with you know, if we have a result, array, and then append, bat, append. Nat and, you know, all the all the words, all the anagrams together. And that, yeah, that will be my first approach. Let's see. But, I mean the thing with this is, oh, sorry. Go ahead. Yeah.\nRed Maelstrom: What would be the complexity of this one?\nMeta Nougat: Yeah. So for the complexity would be, let's see. So, okay. So I would have to iterate through strings once, and then, what to do. I was thinking, okay, in order in order to check the, so let say I checked. Let's see. So let's say okay, I iterate through strings. So let's see, eat. Right. Iterates through input, input once. And then for each one, n log n. Let's see, counter. N times, okay, so what I was going to do is so sort, every, every string, so that, you know, like, Okay, we're going to go to eat, right? I mean, if if dictionaries empty, then we put eat, and then that I sort the word tea. And, yeah, so. So sorting tea would take n log n. And we're doing N log N for each and every word. So right off the bat, it would be n squared log n. Right? Because I'm doing n log n, every like, you know, for every every word. And then let's see, n log n, n squared log n squared n and then I will have to do this but yeah, but yeah, so. So yeah, it would be at most n squared log n, because all other operations are smaller. Right? Like, like iterating through a dictionary is smaller than N squared log n. And appending the worst is smaller than N squared log n. So yeah. Yeah. So it's O of n squared log n. But I guess we can, I can do better? Or would you like me to go through the optimization? Or do you want me to code this approach?\nRed Maelstrom: I think I'm okay with this. Let's try to code this.\nMeta Nougat: For sure. So let's see. So yeah, so I'm going to use Python. So we have like group anagrams and then we have input string, or just strings. And yeah, that's our input and then we need to generate a new dictionary, anagrams dictionary, just dictionary, and then we have the result array and then four word in strings, we say something like. So we have sorted word equals sorted word and then if sorted word, let's see so we have anagrams dictionary equals anagrams dictionary, sorted word equals anagrams dictionary dot get? So what this does is return the value associated with the key sorted word. And if and if there's nothing at that, you know, if that key does not exist, then just return zero. And oh, wait wait wait, oh never mind, I need a yeah, I'm not. Yeah, I need to return to index. So this is was not actually in let's see, I need to\nRed Maelstrom: So, can you help like what gets called sorted word common little use, like if okay, It's a default value if it is not there?\nMeta Nougat: Right. So actually, so yeah, this is I mean, I need a I need a append. Yeah, I append the index. So this this would not work. Yeah. Yes. So for each word in strings, actually, let's do while because I need the index so I equals zero. I is lower than length of strings, right. And then word is equal to strings. I and then say something like if sorted word not in anagrams dictionary then we say you know anagrams dictionary sorted word equals I, else oh right. So, we will need to put like a list here because we are collecting all of the all the indices and then else if it exists then we say oh yeah we append this we append the dictionary to the existing. So, now we have so now we have the dictionary here right?Now, we need to generate output. So for this we go for key value we can do for word anagrams indices or indexes\nRed Maelstrom: Do you need to increment the i?\nMeta Nougat: The i oh yeah yeah my bad. Yeah. Otherwise it would just run infinitely yeah. Thank you and then for each word in this in we have anagrams dictionary dot items. So we get each level right of the dictionary and we say okay let's see, again then we're going to iterate through each, each index in indexes list right? Indexes list and then we're going to say okay, we're going to have like a current or like temporary group anagrams? Yeah. This and then then we're going to append the anagrams or rather the words at the index. Right. So append so we have strings in Right, yeah. And then when it's done doing that, then we're going to append temporary anagrams group to results. Right. Result dot append this right. For index in indexes list yah. Okay. And then after that, you just return results. Yeah. Yeah, that's. Yeah. Yeah, that's that would be my answer. I can optimise it. Maybe. The thing is, sorting is one of the most expensive operations here. Right instead of that we can we can, like, use the counter method and count the count how like the frequency of each character instead, yeah. So let's see then wait I mean counter. The one thing about changing, sorted like change, instead of sorting it, we would have to use counter. But counter, counter returns a dictionary, right? Dictionary of, you know, characters and is that the case? So that is we can not put that as a key in a dictionary because a dictionary is editable, right? It's mutable right? So keys cannot be mutable. So we should like think of something like yeah, let's see.\nRed Maelstrom: Can you create your own counter?\nMeta Nougat: Oh yeah, yeah, we could and we could return maybe let's see, instead of a dictionary we could maybe a tuple that's that's the one like what that's one of the few immutable data types so yeah. Yeah, okay.\nRed Maelstrom: Can you go over the tuple.\nMeta Nougat: Sure yeah of course let's see yeah okay. Let's see word okay. So we have word and then instead of sorted word we say or we could create a new, a new function here like counter and then get word right? And then yeah. So we say okay for character in word, let's see. So we have oh wait can we, I'm wondering if we can put a dictionary inside a tuple, would that yeah and I mean in theory a tuple in theory is immutable. Ok yeah I can try that out would be faster. So here, so okay. Counter. Okay. Character, or like, yeah, see? Character. Counter. Equals counter yeah and then put that into a tuple like yeah this and this and then is character counter let's see oh wait oh yeah I need a comma here to make it, to make it a tuple if yes it's a tuple with just one item and you'd have put a little comma here and then if, if character counter not in anagrams dictionary right then anagrams dictionary is character counter sorted words yeah and the key would be the tuple itself like the counter the tuple with the counter so yeah if character counter not in an anagrams dictionary. Yeah okay to counter yeah I think this is better. Word yeah okay yeah this this this should be faster then.\nRed Maelstrom: Cool awesome, let's look at the second question I'm just pasting it on top. Let's say you have a sorted array, two integers k and x, you have to return the k closest integer to X in the array. For example, if you look at example number one K is equal to four and X is equal to three. Closest to three is like three itself because it has zero distance from three so three goes there. Two and four both are closest to each other a distance of one so both k goes in. Out of like four and a five and then like either you can include one or a five both would have been, both could have included but in that case like we'll choose the smaller one. So one will be. And if you take a look second example, closest to minus one are like 123 and four because for you is like far more further than minus one. So yeah, it's not necessarily that x will be a part of array.\nMeta Nougat: Okay\nRed Maelstrom: So, so yeah, so given array K and X you have to return the K closest, K elements which are closest to x.\nMeta Nougat: Okay. Okay. Makes sense. Okay. A oh wait, so we're looking for okay, that K closest integers to x. Okay. Excellent. X is three and then we're looking for the four closest to to three right the 4 closest to three. Okay. And then in this case, integer A is closer to X. Okay. Okay. So that's why three is closer to itself because it's zero right.\nRed Maelstrom: Right right.\nMeta Nougat: Okay good right makes sense makes sense\nRed Maelstrom: There are two choices, we use the smaller one, one and five both are at distance two from but one is smaller than so we choose one\nMeta Nougat: Makes sense. So can we assume that we will not get repeated integers\nRed Maelstrom: That's a good question. There could be repeating itegers.\nMeta Nougat: Oh we will not get repeated integers?\nRed Maelstrom: We can get repeated integers.\nMeta Nougat: Okay. Yeah, that makes sense. Okay. What if we have for example 123345? Like\nRed Maelstrom: Yeah, so in that case like both three will be repeated right?\nMeta Nougat: Okay. Okay.\nRed Maelstrom: And it's like there would have been this case like two comma two comma three then this would have been like the two comma two. Because like you will use these two rather than that four.\nMeta Nougat: I see interesting. And for example, in this case, right? Like cause here is, A is three and X is three. So this is zero equals zero. But like they're both, they're both equals. So we just put both?\nRed Maelstrom: Yeah.\nMeta Nougat: We just put both okay. Okay, interesting. So my approach here would be something like let's see. So yeah, we would need to look for x first. Right? Oh, can we assume that x will be inside our input array.\nRed Maelstrom: No, you can take a look at second example. X is not in.\nMeta Nougat: Oh, yeah. Oh my god yeah, you're right, right. Right. Thanks. Okay, and can we assume that we'll have like let's see. We'll have let's see, that we'll have at least k integers in our input array\nRed Maelstrom: That's a good question. Yeah. That's yeah, that you can assume K is less than equals to total number of elements.\nMeta Nougat: Okay, sounds good. Thank you. Okay. Okay, so we say something like. Let's say okay. Yeah, so Okay, so I'm gonna I we have to look for, for x oh no wait no not x okay. So yeah we need to find for X but in case it's not in X. Like we need to look for the place where it's supposed to go you know given given a step right so I think we would we should perform some sort of binary search and you know determine the place, the index where it's supposed to go right okay and start from there. Perform binary search to find index of x right and then and then say and then start, so it should be let's see. I think, yeah, we should start looking from left to right. So that whenever, whenever the whenever we append a new integer it's in order, right? It's sorted in ascending, ascending order. So, in this case, let's see, let's say we got minus one. So we start with I mean in this case, if we don't have anything available to the left we just start you know with the right and say 1234 we just keep, we just keep appending numbers until, let's see how can we guarantee that let's see, they just um yeah, I'm having trouble like I was gonna say you know, we start from left to right in this example but what if we have something like minus 100 minus, 20 minus 20. Right I mean this whole this part of the array is closer to three because of x then this side right? Right let's see okay that's a bit tricky.\nRed Maelstrom: Do you know the range in which, from which you will get the key numbers\nMeta Nougat: Ah, that's a good question.\nRed Maelstrom: Once you find the index\nMeta Nougat: Once you find the index. Yeah, so it should be like, up to like whatever we have for example. See, that's a good question. Yeah, 0 wait 1 let's see like the you mean the difference between like a and minus x? Like what's the maximum and minimum ranges of this\nRed Maelstrom: Nope it mean's that if you are like this index three, right. So, you have either just two choices, either you will go to the left or you can go to the right.\nMeta Nougat: Yeah\nRed Maelstrom: Can like, out of those two choices how we will determine which one to pick?\nMeta Nougat: Right. Yeah, so, we we compare zero with the one to the right. And say okay, yeah, we perform this operation or this operation. And then we append, right? Then we append whatever, whatever we, whatever the sort of, like whatever the, the closest integer is. So, we, we do that, and then maybe we maybe we can have pointers or something like that, we will move our pointer to the right and then we compare x with the one to the left.\nRed Maelstrom: That's a good. Yeah, that's a good thing yeah.\nMeta Nougat: Yeah. Okay. X with the one to the left and say, okay, if left is yeah, we then we compare maybe our right pointer with our left pointer, right.\nRed Maelstrom: If the difference of that pointer with x is like, which ever the difference has smaller difference. Then we gunna.\nMeta Nougat: Yeah, exactly. Oh, yeah. Yeah, we can have two pointers, okay. Yeah. Okay.\nRed Maelstrom: What would be the overall complexity?\nMeta Nougat: So, so yeah, so would be, so this is log n, O of log n. And then and then we iterate to this. Like at most one time? One time, so it's Log N. Oh, yeah. So it would be linear right? Since it is log n plus n, then n is greater than log n so it's just.\nRed Maelstrom: From where this n is coming?\nMeta Nougat: N is a number of integers in the array.\nRed Maelstrom: Why it would be N? Wouldn't it be the k?\nMeta Nougat: Why why is it N?\nRed Maelstrom: Yeah. Why it will be N, won't it be the K?\nMeta Nougat: Right. So\nRed Maelstrom: Like, you won't be going through all n elements. You're just at max K elements right?\nMeta Nougat: Right. Okay. You're right. Yeah. Yeah, you're right. On to. Yeah. So yeah, it'll be k at most k elements, right. So yeah, okay. It makes sense. So, it would be Log N plus K in this case.\nRed Maelstrom: Okay, cool. Yeah.\nMeta Nougat: Should I implement it or should we? Is it like, did we run out of time?\nRed Maelstrom: Yeah, yeah. We have like three four minutes like maybe if you want to. You can assume that you have a binary search don't worry about binary search, just implement the comparison part\nMeta Nougat: Right, okay. So, in this case we have the array and say something like, you know, we get the index from the binary search. And then yeah, binary search. Yeah, X, whatever x okay. So we have left pointer and right corner equals zero and then or actually indexed yeah index and then we have result here and then we have something like let's see if, and then we make the difference if the absolute of array left pointer minus x is lower than absolute of array right. Yeah, right pointer minus x if true or yeah. Or they are the same? So it's just or they are the same, then just append, we append, let's oh wait it's okay, great. Let's see oh, yeah, we append the left pointer, right. Append array? I mean, we append the left pointer.\nRed Maelstrom: Cool I think yeah, I got an idea like, you will be able to implement it. So let's move on to the feedback part of it.\nMeta Nougat: Sure.\nRed Maelstrom: Yeah. So I think like, for the first problem, you use the good naming convention, you use like, meaningful, informative name. Only thing like I think I could have done better is your complexity analysis, you could have use to return parameters that n is, number of strings in the list and size of a string. Right? These are two different things. And then it would have been like n into n log N. Yeah. You could have clearly like this, this complexity analysis with two different parameters, like testing them with just one. But yeah, I think it is a small thing. Another small improvement, which you could have done is when when you're iterating, through some range, right? I think for loop make sense, like for i equals to 02. I in a range, like you could have use for loop where like, you won't miss incrementing part. So when you're iterating through some range of values you could have used ranged instead. So these are the only two things which I think could have been done better. Apart from that, like you were correctly, you correctly identified the bottleneck of your implementation. You also suggested that rather than using sorting, you can sequence in our answer, so that's a good that's a good thing. You also mentioned about like that Python, does not allow mutable dictionary. We also identified the workaround by using that into the tupple. And like your code was easy to follow. Yeah so that was a really good. Like when you started the second question your attention to details was really great. You ask really good clarification questions, you asked like whether there are duplicates, you came up with a test case with a duplicate and expect, clarify what would be the output? You also will there be at least elements. So, those are really good questions, and that shows attention to details. Right. You were able to come up with a solution using pointers. Yeah, and you also, likely applying binary search, looking at array sorted. Right. I think you could have articulated your two pointer approach better, I think you needed to require some help to communicate that idea, right. So, that's, that will be that, that's one thing I think you can work on. And another thing is like, you could have just like first method, you could use some meaningful name for function rather than just a solution. But maybe it was a time crunch, which forced you to do that. So don't worry about it. So my first thing would be like, when you're practising on leetcode or something, right?\nMeta Nougat: Yeah.\nRed Maelstrom: Comment section, particular comment section where you try to write your approach in plain english words, so that you get in a habit of communicating like thinking or articulating your solution, communicating your solution well, so it will help you to get that block away. With the thought with which you solved it, you're trying to communicate two point anything, so yeah, rather than just coding in a leetcode. Also try to write down your approach in three four sentences like, so that like you, can you you get in the habit of like articulating your solution when analysing details before your implementation.\nMeta Nougat: Yeah.\nRed Maelstrom: Cool, but yeah, I think overall, it was good. This is really good improvement from previous interview based on this like it could have been. Hire call. Yeah.\nMeta Nougat: Great. Great. Thank you. Thank you for the feedback.\nRed Maelstrom: Cool, awesome. Yeah. I think, yeah, just just try to, like write down your approach before writing the code, while practising then that will help you to articulate your solutions. Well, apart from like, I think you ticked all the boxes, you did everything right. So yeah.\nMeta Nougat: Yeah. Oh, great. Thank you. Thank you. Appreciate it.\nRed Maelstrom: Cool when is your actual, when are your interviews starting.\nMeta Nougat: So I have one on Monday. But yeah, I'm still I'm still in college. Still an undergrad. So yeah, I want to I want to be ready for next year. Right. Like the upcoming the one I have on monday is, it's fine, but I really want to focus on the one next year. Like Yeah.\nRed Maelstrom: Cool awesome, yeah. All the best for your journey.\nMeta Nougat: For sure. Thank you so much.\nRed Maelstrom: Yeah, thanks bye bye.\nMeta Nougat: Bye bye.