Python Interview with a Slack engineer
Watch someone solve the transformation dictionary problem in an interview with a Slack engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.
Interview Summary
Problem type
Transformation dictionary
Interview question
1) Given a dictionary of words, determine whether it is possible to transform a given word into another with a fixed number of characters 2) Modify the approach so that transitions between varying quantities were possible 3) Modify the code to work as an API with lots of words added to the dictionary, but few tests 4) Determine the largest sum of a contiguous subarray
Interview Feedback
Feedback about Winter Griffin (the interviewee)
Advance this person to the next round?
How were their technical skills?
4/4
How was their problem solving ability?
4/4
What about their communication ability?
4/4
Really great overall - impressed with the quick answer on the graph problem! Just study up on those dynamic programming problems and I'm sure you will not have any trouble with interviews!
Feedback about Spasmodic Pizza (the interviewer)
Would you want to work with this person?
How excited would you be to work with them?
3/4
How good were the questions?
4/4
How helpful was your interviewer in guiding you to the solution(s)?
4/4
I liked the graph search problem disguised as a string manipulation problem. I also liked the follow-up question about how to make the system more efficient in the case where we rarely add a new word but isTransformable() is called often.
Interview Transcript
Spasmodic Pizza: Hello?
Winter Griffin: Hello?
Spasmodic Pizza: Hey, how's it going?
Winter Griffin: Good, how are you?
Spasmodic Pizza: Good. Can you hear me okay?
Winter Griffin: Yeah I can hear you fine.
Spasmodic Pizza: Okay great um... So for this interview we're going to try to do this in about 40 minutes. I have... I guess before we get started, about how many years experience do you have as a professional.
Winter Griffin: Like two and a half.
Spasmodic Pizza: Okay cool. I just like to use that to guide the questions appropriately. Okay so let me know if you've seen this problem before, but I am going to paste it in. So what we're doing is we're writing a function to determine if a string can be transformed into another string and each string... So the example is I have two strings, the start and end string, dog and hat. And I have a dictionary of words that are transitions for the strings, that are better possible words that can transform into. We want to see if by changing the word one letter at a time, if you could turn dog into hat. So in this dictionary I have all these random words and there is a path that exists like that. dog->dot->hot->hat And so if I was to call this function is_transformable(), it should return true. And so we want to write a generic function that will do that, is_transformable().
Winter Griffin: Gotcha. So, okay so I see that the start and end words are not necessarily in the dictionary.
Spasmodic Pizza: No they're not.
Winter Griffin: Okay um cool. So I guess like my first thought... Use a graph. So each node is a word and two nodes are connected if they differ by one letter. So are you saying that we can't insert letters at the beginning or at the end right? So if start is like a three letter word and end is a four letter word, then it's automatically false?
Spasmodic Pizza: Yeah so in this problem we're kind of bounding it to just single letter replacement.
Winter Griffin: Okay gotcha.
Spasmodic Pizza: You can assume that start and end will always be the same length, and that the dictionary is well-formed, and all the words in the dictionary are at the same length.
Winter Griffin: Okay so then we can just do like breadth-first search. By the way, I have not written this problem before, but yeah. So I think this would work, I'm trying to figure out if like there's a more efficient way to do this. Okay so we look at... Yeah I think this is going to be my approach. Um and in terms of like run time, it's going to take... Breadth-first search could look at... If you look at every node and every edge, so run time is... It goes O(V+E) where V is number of nodes. That is um... So we at most look at every single word in the dictionary, which is about as good as we can do right? I guess we could like prune some of the words off...
Spasmodic Pizza: Yeah I don't think you can really do much better.
Winter Griffin: I think we can do better. Since we know the destination, since we know the start and the end, we can do like a bi-directional search from like the start and the end, and that actually... It cuts the runtime and yeah... Where's that music coming from?
Spasmodic Pizza: It's just my laundry machine that plays a short melody when it's done.
Winter Griffin: I guess I can just define one letter. So basically this method tells us if two nodes are valid connections.
Spasmodic Pizza: Okay.
Winter Griffin: I'm seeing how this will work. So basically this algorithm is going to be... So the total run time is O(n^2) because we're going to like catch at every word that is able to connect with every other word. Yeah so it's going to be O(n^2) total. Based on the number of edges, it's also O(n^2).
Spasmodic Pizza: Okay.
Winter Griffin: So and then let's do breadth-first search. I put like a flag that's like if seen before.
Spasmodic Pizza: Okay.
Winter Griffin: Actually, this won't work because like if you just mark seen as true and we encounter a node that we've seen before, we don't know... Because I'm doing bi-directional, search I wouldn't know if it's like if seen by the first search or the second search. Actually I'm just gonna make the simpler, I'm going to like scrap the bi-directional search idea and just go with like a simple breadth-first search, at just the beginning point.
Spasmodic Pizza: Okay yeah that sounds good.
Winter Griffin: Okay so the final function... So we're going to do is... Okay so first we create the graph and then we do self.breadth_first_search(). If you just return self.breadth_first_search()... This should work. That looks like it. So we'll use the example you gave me.
Spasmodic Pizza: You can use like dog and ice.
Winter Griffin: dog and ice? Okay. Yeah that makes sense because ice is not connected to anything else. Whoops sorry, can you hear me?
Spasmodic Pizza: Oh yeah I can hear you.
Winter Griffin: Yeah my bad, I hit like f5 because I'm just like super used to doing that to run and build. Graph is not defined. Okay so that is line 49.
Spasmodic Pizza: Oh I see the asserts just throw errors if it doesn't work.
Winter Griffin: Yeah basically I'm using like an assert statement at the bottom.
Spasmodic Pizza: Okay cool um yeah everybody writes their breadth-first searches a little differently. Um so so what if we did allow deleting characters and we have words of different lengths? How would you change your algorithm, you don't have to code it up.
Winter Griffin: I would just changed like how we link. Like all we have to do is like change the function that determines if two nodes are linkable. So if they're just like one letter apart by if you just have to insert one letter or delete one letter to get to the other word, then you can create an edge between that. Like the generic breadth-first search algorithm would still work.
Spasmodic Pizza: Okay and let's say you were designing this for a really high scale system where you have lots of words being created, but you only get occasionally asked to verify if you can transform from one word to another. Would you would you change the way your data structures are set up or how would you modify the algorithm?
Winter Griffin: Yeah I see what you're saying. Um so basically you're saying if we have many words, so n is large, but is_transform() is called like not so often, then I would do some kind of pre-processing where... Yeah you could do like pre-processing where you have like a two-dimensional matrix, like it's like an n x n matrix and then you just do some pre-processing for like every single node and figure out if like the first node connects to the second node, then that entry in the matrix is true and then if not it's false and the matrix is like symmetrical and then when you call is_transformable(), you just look up in the matrix and just return it, so it's like constant times for is_transformable(), but we have to do like a lot of pre-processing.
Spasmodic Pizza: Okay. Do you think you could write a function that would sort of illustrate the pre-processing step?
Winter Griffin: Yeah so I'll do it in the graph class. so do self.matrix equals... So we don't know how many words are going to be... I'm just going to do self.matrix is like an empty... maybe like an empty 2 x 2 matrix for now.
Spasmodic Pizza: Could you make the pre-process step just take a word, so it's like an API and I add a word to it every once in a while.
Winter Griffin: Oh I see what you're saying okay. First you add the word. Okay no I lied. You can do n = node() with a new word. Now you do for previous_word in self.words. So we just link with every other previous word. But we don't want to link with itself, so we link all the previous words with this word and I automatically detect if we're able to link them or not. And then we do... For the the two by two matrix, so self.matrix, we have to.... And so the matrix starts out being empty, and then we have to do... So each row is a list... So that means like this matrix should just grow every single time, like by one to the right one to the bottom. Then so... then we go to the pre-processing. Then we iterate through all the nodes... So what that means is for is_transformable(), we can... We have to figure out what index... This matrix is just annoying, I'm just not going to deal with it. I'm just going to make a like a hashmap.
Spasmodic Pizza: I think that this is a problem it's pretty well suited to Python actually.
Winter Griffin: Yeah. Okay so self.matrix... When you add the words into self.matrix... So you go to another hashmap. So all the words are in the matrix and so if this is true and... Okay so then I return self.matrix. So the check is this work. You have to do... So for this pre-processing step we would do... So we have to like call ahead of time everything we need.
Spasmodic Pizza: It looks like on line 117.
Winter Griffin: Oh that's true. Only adding is that's true.
Spasmodic Pizza: Okay yeah awesome, yeah that's great. Yeah good job. Now if you'd like, I can ask you another question or we can just be finished, that's up to you. I have some shorter questions.
Winter Griffin: Yeah let's do another one.
Spasmodic Pizza: Okay so let's say we have this down here, we have an array of integers and we want to print the max subarray sum. And so in this case the max subarray sum is going to be the sum of 4, -1, -2, 1, 5, which is equal to 7.
Winter Griffin: Okay so we could... I'm thinking so we could have two pointers and then... So it would just kind of let itself to like an O(n^2) algorithm where you just like... one pointers iterates more slowly and other point in just runs ahead and you find like the sum of all the numbers in between, so that's the brute force solution. The faster solution would be... So I mean I'm trying to think... There's probably like a dynamic programming solution where you have like a two-dimensional matrix and then you do the maximum cell race sum...
Spasmodic Pizza: Yeah I mean so if you go down that path it kind of is equivalent to the two-pointer method and so it is a dynamic programming problem right? And the way you formulate dynamic programming problems is to get them away from like you know O(n^2) or O(n^3) solutions. You're making a decision at each iteration right? So there is an O(n) solution and you should think about if you're iterating through this loop, through this list of numbers, you have to make a decision around your sums, so we're just trying to pull in that direction.
Winter Griffin: Okay so you've got to figure out it if it's going to increase or decrease your sum, then it's probably like... If it's going to decrease yourself it's not worth checking if you can just prune that entire subsection. Um so okay, so if I create a 2x2 matrix like I two dimensional matrix and then like... So basically if we start... We don't want to fill in all the all those squares because when we do that, that's n^2, that's like the same as the brute force solution, so we just want to do like one pass through the matrix, so we just want to like start at some like corner and then just do like a staircase kind of thing.
Spasmodic Pizza: Yeah I think if you go down this direction, you're probably going to find yourself farther away from the solution, so um maybe if you think about it kind of more inductively, like you have a list of just negative two, right? The max subarray sum is negative two. And let's say you have a list of negative 2 and negative 3, max will still be negative 2 right?
Winter Griffin: Right I see.
Spasmodic Pizza: So we have -2, -3, 4, max is 4.
Winter Griffin: Right um so that seems kind of recursive where... Okay so all we need is just like a one-dimensional array, the answer is a one-dimensional array and we just fill it out. So the answer so basically basically... If you're only looking at the elements before i. So answer zero is just, that's a base case, answer zero is just a zero. So what we do is... We look at the previous answer, which is i - 1 and if the current number is bigger than the previous answers, then we want to include it. Whatever the previous maximum. But we don't know what the previous max subarray sum, what is like contiguous with this current number, that's like the issue. So we can't just... Okay so well, let's keep going with this example, so we have -2, -3, 4, -1, max is still 4. So if the current element is greater than the previous max of array sum, we want to include it but we don't know if it is contiguous, so that's the problem.
Spasmodic Pizza: Yes so there's a property of this that you can exploit, right so you know when you look at negative 2, then you add negative 3. Now you know that every you know permutation of these two numbers is not gonna be helpful, and so negative 2 is your maximum at that point. When you add 4, are you better off including 4 with the last two values? No because they're negative right?
Winter Griffin: Right.
Spasmodic Pizza: So you can kind of choose to always reset your current max, or your current sub-array.
Winter Griffin: Gotcha okay so basically if the current element is bigger than like the max sum we've seen in the past, that means the max of array sum is like the current... It's like a one-element, just the current element. Okay so but then this gets tricky because... So we keep going with the analogy, so once we get to 4,-1,-2. And let's say we get here is still four. So then once we get to another positive number where we get to one. The issue here is that... Oh it is okay, I see. So five is bigger than we've seen previously, but it's not just equal to five.
Spasmodic Pizza: Yeah so you need to keep track of some more data to iterate.
Winter Griffin: Right so... Let's create like a struct that's like info. So we record the maximum so far, start index and end index, and then... So we track previous maximum and if the current number is bigger than the previous maximum that we definitely want to include it, which means...
Spasmodic Pizza: Yeah so we're like almost out of time, so I'll just explain it to you. Basically at each step here you have current max right? You also have the the candidate sum, way to put it. So when you start you know your candidate sum is zero and your current maxes is negative infinity right? You come across -2 so you add that to your candidates sum. That's larger than the current max. You look at -3 and you know that because -2 is already negative, you add -3 to it, it's going to be even smaller, that it's better to to just examine -3 as its own sub array, and either way it doesn't beat the current max, so you ignore it. And so four, you're not going to want to add it to the previous candidate sum, because the previous candidate sum is negative. But four is greater than current max. And so basically what you end up doing is that every time your candidate sum goes below, is negative, then you just reset the candidate some sum to zero because you're never going to want to include a sequence of negative values if they bring the current sum below zero because then you might as well just start a new array with a positive value you see.
Winter Griffin: Okay so make a decision with every element.
Spasmodic Pizza: Every iteration right. So like your candidate sum at all these steps... The first two steps... Is going to be 0. And then, it'll be 0 to here, so when you start here, it will be 4. So that will be 3 and 1 and then you'll say ok well 1 plus 1 is 2, I don't have to reset the whole thing. Yeah and then 5 and it kind of goes from there, so it's sort of like crossing the boundary is the consider in this problem.
Winter Griffin: Okay.
Spasmodic Pizza: Cool. Overall you did pretty well. Most people don't do both of these problems really. I usually don't do these problems at once. Um do you have any questions for me or anything?
Winter Griffin: Yeah so like what what company do you work at? I run my own startup so it's just me so...
Spasmodic Pizza: We're called ------, we're a marketplace that connects creative people, like yoga teachers and musicians, to elderly people and facilities like nursing homes, assisted living, independent living, stuff like that.
Winter Griffin: Ah, that's pretty cool.
Spasmodic Pizza: So yeah, are you are you looking for a job right now?
Winter Griffin: Yeah I am actively interviewing for jobs.
Spasmodic Pizza: Cool yeah I mean my company is pretty small at this point so we're not really hiring, but I can reveal my identity to you at the end of this I guess. But um ya know I think you did really well on the graph problem and the dynamic programming stuff is just a matter of you know going through every practice problem in a book until it sticks. But yeah and I I think it's really good that you were comfortable, like I'm not a Python programmer, but it's always good to see that somebody is very comfortable with the syntax of their language. Like you can write an object without having to like look up how to do a constructor and all that, so it was really good overall.
Winter Griffin: Great thanks, so are you just doing this as like a volunteer kind of work or like why are you interviewing people?
Spasmodic Pizza: So you get paid to do this. It helps fund my entrepreneurial ambitions, yeah.
Winter Griffin: That's pretty cool, awesome.
Spasmodic Pizza: I dunno nice it's yeah, it's just like a big job so. It's fun I already give interviews all the time so yeah as a programmer.
Winter Griffin: It's pretty cool yeah. Maybe I should do some of this. It was nice meeting you and yeah thanks for the feedback.
Spasmodic Pizza: Yeah good job, alright have a good day.
Winter Griffin: You too.
We know exactly what to do and say to get the company, title, and salary you want.
Interview prep and job hunting are chaos and pain. We can help. Really.
