Python Interview with a Walmart engineer

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

Interview Summary

Problem type

String permutation

Interview question

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Interview Feedback

Feedback about Phantom Storm (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

3/4

work on finding time complexities.

Feedback about Mythic Unicorn (the interviewer)

Would you want to work with this person?

Yes

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

The interviewed provided me with excellent feedback. Insistence on run time complexity was good, and helped me realize my shortcomings.

Interview Transcript

Phantom Storm: Hello.

Mythic Unicorn: Hello. Can you hear me?

Phantom Storm: Yes I can.

Mythic Unicorn: Okay, awesome. All right. How are you doing?

Phantom Storm: I'm doing fine. How are you?

Mythic Unicorn: Good. Okay, I guess we'll just dive right into it. I'll put a question, you can select the language of your choice.

Phantom Storm: Okay. Yeah, I'm going to do it in Python3.

Mythic Unicorn: Okay, let's say...

Phantom Storm: Okay. One of the first strings permutations is the substring of the second string. Okay.

Mythic Unicorn: So something like AB versus this other s2, you will return a true here. And if this gets separated by something, then you'll return a false.

Phantom Storm: Got it. Yeah. Okay. Yeah, so it's actually like two problems in one. The guts of the problem is finding all permutations of the string s1. And when you do one permutation at a time, find out if the permutation is present in string s2. And if it's present then return true. So that's one approach to do it. Are there any other approaches like perhaps using dynamic programming? Maybe, but I'm not sure about that. But let's, I can try the first approach of like finding all permutations for... Okay. So, so finding out permutations. The permutations can be found using... Okay, so permutations are like take each string and then take characters of each string and rearrange it in a different order. There is actually graph algorithms to do the permutations like depth first search... it's either depth first search or breadth first search, I'm trying to use one of them. And then we can go doing that. Let me go. Let me write an outline and then define it. Okay. Find... So how do I get the permutations of a string? Usually, like there are higher order functions in Python available. Like it has tools and data tools can provide permutations and...

Mythic Unicorn: Let's not do that.

Phantom Storm: Yeah, no. Yeah, I get it. Like that's not the point of this. So permutations, I'm trying to recall I'm trying to see the depth first search or the breadth first search will be the most suitable one for the permutation. So let's start with the start with AB. So after selecting a, I have to find out all combinations of the rest, that's B. And then I have to select B and find all permutations of the rest of the string. So, the way to do that is... okay, let me see... Okay, then. So we have to find out the permutations of that... of remaining. So, the way to do that is, okay... Okay, I think so, let's try to do it recursively. And if I do it recursively it's actually a graph where the A is connected to B. And to do it... find all the permutations of everything. Okay. I think breadth first search has the option to kind of like find out, okay, so it's not really depth first search. So we have to take one, and all the different, all the different permutations, except for the character, big one and all the different permutations except for the character, so when breadth first search is involved, we have to have a queue and then pop information from a queue and then put them in order. So yeah. Okay. So, okay. So what do I place it in the queue? So, the gap, the string itself is a permutation of that character, so let's start with the queue with value of the string, and string of... we'll see if the queue exists, then start with the index. Okay. I'm still devising a strategy for finding the permutations. I have done it once. But I'm kind of like lost in terms of how to write a permutation right now. So I'm trying to find out a strategy and then I'll be able to write it. It's breadth first search, that side I know and then the way to write breadth first search is to kind of like have a queue and an index and then and permute using this index.

Mythic Unicorn: Okay, since we are having kind of problems with permutations, how would you do permute of 123, a string like that, like 123. How would you permute 123?

Phantom Storm: Okay, so I take one and permute two and three. And I'll take two and permute one and three. I'll take three and permute one and two. And permuting two and three, so for, two and three.

Mythic Unicorn: So what strings will it generate?

Phantom Storm: So, what strings will it generate? Okay, yeah. 123 132 213 231 312 321 Yeah.

Mythic Unicorn: Okay, so like, what did you do over here the first time? What were you doing to permute?

Phantom Storm: Yeah, so in the permute, I was taking one character and and I was fixing on before the two characters, I was simply swapping actually. And what I was essentially doing is I was fixing on one character in the string and then returning the other character and fixing the next character and returning the other character.

Mythic Unicorn: So basically, last two characters, you're just swapping. Yeah. Okay, and then you somehow have to get back to 123 or do you continue from the last two characters?

Phantom Storm: I will have to get back to 123 and yeah, I'll have to get back to 123.

Mythic Unicorn: So from here, you again got back to 123 and then what did you do to get to 213?

Phantom Storm: I fixated on two and then consider the two characters one and three.

Mythic Unicorn: Okay, so you kind of swapped two and one. So two became first, plus you did permute of one three.

Phantom Storm: Yeah. Yeah. Okay. Yeah.

Mythic Unicorn: Okay, so like, do you see where I'm going kind of?

Phantom Storm: I see that okay. I see in terms of like the most important hint of like when there are two characters, you just swap, I just swapped them and then I fixed on each index which means that I am I will have to go one character index at a time and, and permute the rest of the characters and when I'm permuting the rest of the characters if it is actually two characters I am swapping If not, I'm permuting against the rest of the characters. So it for... Okay, I mean for three characters it will look but I do not know what will happen for the four characters but let's start I will start with the three characters in the code and then I think I can modify it for the end characters.

Mythic Unicorn: Yeah, okay. What what will happen if there was only one character?

Phantom Storm: If there was only one character, you just return that.

Mythic Unicorn: So what does your ending condition kind of become?

Phantom Storm: Okay. So if my return values if the length of the character if the length of the string is one, just return it if the length of the string is two, then swap it. Otherwise, you kind of like go through the iterate through the iterate through the indices of the character, pick one character and then permute the rest of the characters.

Mythic Unicorn: Okay, so let's do that.

Phantom Storm: Okay. Thank you. So...

Mythic Unicorn: Also, sorry, I think I missed this... How will you get from 132 to 123 back when you have to go to permute one three?

Phantom Storm: So, how would I get back to 132 to 123 back? So, I was imagining that there's a higher the top level for loop is the one that is actually keeping one character and then when okay... So, the permute function should have... the permute function should should kind of like should kind of like for two character permute string it should return both the three two and two three which means that...

Mythic Unicorn: That gives us 213 and 231, but how do we get back to 123 or like 123 and 132 we get with the two character permute but how do we get back to 123 after that? Did you get what I was saying?

Phantom Storm: I think I slightly understand.

Mythic Unicorn: So, with the one, when we do a permute of two three, with one we got one plus two three and one plus three two. Yeah right? Now, like if there are more than like this is only for three characters if there are more than three characters then what do we do right? How do we get back to 123?

Phantom Storm: So, do we... I mean we okay. So, I think we need to place the character the place the stress string in a stack and then kind of like go forward with analyze all the values in that stack and then push it. Is that?

Mythic Unicorn: And like how will the stack get back to 123 or back again?

Phantom Storm: So, if we pop the value from the stack and then analyze all the values in the stack and then we we permute the values and permuting the values will give 123 and 132 and then we... the permuted... I'm lost... I think I still I mean I am not getting how we are getting there but once I get that question, I'll do it.

Mythic Unicorn: Keep going with what you were thinking.

Phantom Storm: Yes, yes, I think once I understand the question, I think I will be able to get it... It hasn't striked me yet. So let's talk the one permutation is one return, yes. If length is two... okay. So that's for like for two characters, for index in range of length of S. First character of index and remaining two, so let's assume that I pick up one here. And the remaining is actually everything before one and everything after the one. Okay, and we have to do up a new permutations, the meaning and the plus the permutations of remaining. That's the word. This is not complete, but I hope this will help me find the problem. So I am having a array of results, and for each index and the length of years, I will go take a character, and here are 123 I'm taking one and then remaining as a two three. And population of two three will be... So, I'll have one with permutations of two, three and permutations after three if length is equal to one.

Mythic Unicorn: So, the permutation function returns the list, right? It will give you will add everything like to every element of the list?

Phantom Storm: I am wrong here, it should not be a single computation function. So, this I will have to write another thing. Which should be... I want to... So, if it is actually I have... otherwise, I'm still thinking. I think I am, I know that this is wrong. So that's why I'm kind of like, thinking to get back. So, how do I do permutations? I think to do the permutations... take an index and permute the rest of the things so that is that, that until here is correct taken index and then permute the rest of the things and when I'm permuting the rest of the things if I am having... So, it's actually permutations is actually BFS, and then BFS, what you do is actually have a stack and you pop the value and find out everything that's connected to it, which is again, the different permutations and add it back to the stack. And so I'll do something like that. Okay. So, I mean, I'm going past this 123 but I'm going from the some other example I have. So then you have the remaining equals the same logic of the index. And so what I'm doing here in the permute is actually putting a string in the stack and then popping this thing off. And I'm actually going from the value popping this thing off and then going to the length of the string and permuting the character of the string without this I will... Okay, I will have the value of index plus the remaining into the stack. And when I do this way, what happened is the stack always go through. So if stack has ABC, then I will have ABC as pop and then one, zero one two the index, I'll have okay. Value is equal to this one. Let's just give some list of words. Okay, and then you're doing kind of stack public kind. So, what happened here, okay. So, I have done the list of words with the permute so permutations when I go here... Permute with... okay. And all permutations will be actually we are defining a global here. So, I would have it in the list of words. Okay. I would just do permute. Yes. Okay. Sorry?

Mythic Unicorn: I think you don't have the return.

Phantom Storm: Yeah, it returns None. So I am actually using a global here to kind of like keep track of an already seen permutation and doing some kind of like breadth first search here and and seeing if that's the thing. Oh you mean for this? I don't know why this... okay, yeah let's... Shall we try it?

Mythic Unicorn: Yeah okay.

Phantom Storm: Let's see if that's true. Yeah. I think I'm lucky, but yeah in terms of like my understanding of how I used to do like I said I had done some kind of like a permutation problem way long before and I was struggling to recollect it, this was the cause of the method I was trying to recollect in terms of like having having a stack and popping the value from the stack and then having an index for a particular value and then having a permutation of the remaining value, which I'm doing here, and keeping track of the permutation and global value, which is like a list of words. And if I had already seen it, I will not permute it, but if I had not seen it, I'll permute it in the form of like, the recursive value of the stack, and keeps going. So yeah, this is...

Mythic Unicorn: A couple of more test cases. Let's go with the length of four.

Phantom Storm: Okay. Should return true. Let's see if it does. Okay.

Mythic Unicorn: How would you kind of go for a corner case. Okay.

Phantom Storm: Okay, corner cases. Okay. Let's see if the same thing this... and then just reverse that completely. Let me see. Okay, my empty strings was not a good thing. Was this fine? Okay, I think... Yeah, and this thing was like an extreme corner case.

Mythic Unicorn: Okay. What would be the runtime for this.

Phantom Storm: Yeah, the time complexity, this is actually... So it goes through at the highest level, it goes through a for loop of the length of the string with, let's assume if the length of the string is n, and then it has to go through each of the n and it has to look at the all the different permute values of it. So my understanding is all that different permute values is like you take one and then different things, one and different things, one and different things. So it's like, sorry, I'm calculating... Okay. So n... it's an n. So we are having n. And for each n, I'm kind of like permuting, all the different n. So it's n factorial, because I think each of them will be going out one at a time and then finding out if the value is present in that. So that... was that correct?

Mythic Unicorn: Yeah, yeah. So I yeah, I just want to know, the time complexity for this.

Phantom Storm: Yeah, runtime complexity. So we are going for a n in the for loop. And then for each n, I'm still kind of like, getting again in the traversing the entire tree with the n. It's n factorial. It's my it's n into n, its n factorial is my understanding of the time complexity. Okay. Yeah.

Mythic Unicorn: N factorial for the strings, right?

Phantom Storm: Yeah, it's n into n factorial is what I'm kind of deriving. But I'm if n into n factorial is same as n factorial.

Mythic Unicorn: How many permutations? Like the list of words how many can it have?

Phantom Storm: Oh, okay. Yeah, it's that. List of words have the permutations of, so it's three. And six, actually, it's it this is n factorial. So yeah, yeah, yes, string of length n will have n factorial permutations. So n factorial is going through all the different permutations on getting that thing. It is... The runtime complexity of this is we have n for the number of characters, and then the number of permutations in the string is n factorial, okay. In fact, it is the loop again. So for this particular implementation, I have like, how many times I'm executing the stack here? I'm executing this stack while loop... It's not n factorial times, it's actually... n. And then I will be having n. The complexity here looks to me that it's actually n^2 actually. The reason I'm explaining that is, we are going through n for let's assume that each of the characters, and then this is another n for each of the characters. And that is the... that's the worst case complexity that we are looking at: n^2.

Mythic Unicorn: Yeah. So n^2 in the worst case complexity? Yeah, you're saying?

Phantom Storm: Yeah. I'm deriving it, so I'm not entirely sure about this.

Mythic Unicorn: And where can be? Okay. And then the list of words has, will have how many permutations?

Phantom Storm: The list of words will have all the permutations of a string that will have n factorial permutations. Like, n factorial being so for example, if we have 123, it's supposed to have all the different 123 to have, it's supposed to have all the different things.

Mythic Unicorn: So how many permutations do we have?

Phantom Storm: For four... So the one that's actually 12 into 24? So we're supposed to have 24 lengths, and if... Yeah.

Mythic Unicorn: So you think the permute function should go through all the permutations?

Phantom Storm: The permute? I didn't get question come again.

Mythic Unicorn: Basically, the permute function, it has to get all the permutations, it will have to like, go through all the permutations, right?

Phantom Storm: Correct. Yes. Yes. Yeah. So the complexity is not actually n squared, it's actually n factorial. That's my, that's the understanding. Yeah.

Mythic Unicorn: So n factorial for the permute function and n factorial for the checking in the word and is also order of n. So it basically becomes n into n factorial. In the end, can we improve the time complexity? I guess we're 45 minutes in, so just to give you the idea of where you can improve the time complexity piece.

Phantom Storm: Yeah, like, in the beginning, I was saying, I was saying that this approach seems like the straightforward to me. So I was going with this, okay, this is a costly approach in terms of n factorial, and then finding this one, and into n factorial. The time, if we have a completely different approach, where then if I use some kind of like a bottom up dynamic programming, where I think I can, I can use some kind of like values in such a way that that I will be able to store all the different characters of the string one as some kind of like a map, and then go through the second characters in such a way that if each of the characters in the second string corresponds to the value in the map, then I increment it and then move the window. So I can use a completely different approach, like for example, a sliding window, kind of an approach and kind of like recollecting now after solving this in the first approach, okay, if I have like a sliding window, which goes through all the different characters in the string from the length, a length of the first string and make sure that each of the characters is present in that string, and increment the sliding window in such a way that when I find each of the characters present as a string, then that kind of an approach will be far more efficient than just the n into n factorial approach. Unfortunately, it didn't strike me immediately when I started this problem, but I think that will work and the time complexity of that will be like we are going through the entire list through only once and we will be going through each of the each of the characters in the s1 once. So, it will be of the order not like n factorial, but it will be in much lower, like for example, it will be in the order of length of the second string into into the length of the first string. So, that can be one approach. But I was able to explain the second approach? A sliding window approach. So what I was trying to say is I didn't write it, but i'm not... So, I realized that this is like very costly approach. So, what I was trying to say is, if we go to the second string and then take substrings at a time here, okay, yeah, sliding windows two at a time? And if both of them present... No. Okay, then go for the... if both of them present no. Use some kind of like a sliding window to solve this problem be a completely different problem that will be more efficient. Okay. Here.

Mythic Unicorn: The thing is, you don't like... Okay, I'm kind of, again have to take care of characters instead of on character frequencies, I guess.

Phantom Storm: Yes, I will have to take care of character frequencies correct. So I will have to take care of character frequencies and make sure that that in each sliding window, all the character frequencies in the source string format. And if that is met then it's true, if not, it's false. So that would have been the most efficient way of solving this problem. The time complexity of that approach, if I had gone with that is like the length of the second string, multiplied by how many times I'm going for the first string, if I'm making sure that the first string characters are that... worst case will be like, much smaller than that, like, length of the second string multiplied by the length of the first string would have been a time complexity of the this approach. The second approach I'm seeing. Here in the permute function, if I had gone with the first approach itself, is there a way to kind of like improve the complexity here? I'm thinking... So, can I reject any of the characters? Yeah, really. Yeah, I am not able to think of any optimization and permute function, this approach where I have to exhaustively get all the permutations before I land up on the solution here. It seems to me that we have to exhaustive permutation of our character in terms of an optimization in terms of implementation is that any other thing? I this is a standard breadth first search. I don't see here. So my answer to can I improve this approach can I improve this will be to use a different algorithm, which uses a sliding window and matching frequencies rather than going with this. Yeah.

Mythic Unicorn: I think sliding window is a good approach. What do you think the runtime complexity of the sliding window is.

Phantom Storm: So the runtime complexity will be of course, the length of the second string s2 multiplied by, we have to... So, we have so far... We go each we go one window at a time. And then find out the frequencies. We go on one window at a time and then find out the frequency of the characters. Let's see. Okay. Great. So this is worst case, okay, so I kind of like for each character that going, it's so, I am having that, divided that. We are going through each character in the second string, and multiple each... We are finding out all characters present for the second string. And we are going for like each character in the worst case that will be of the length of the second string multiply the length of the first string. It's definitely less than that, but by some slaps value, but this is the... if you have missed the length of the second string on the left, and that was frustrating, how much are we going?

Mythic Unicorn: Like what is usually the sliding approach time complexity.

Phantom Storm: The sliding approach runtime complexity is usually the sum of the two strings actually, like we go. We go to the second string length with the... Oh, okay. It's actually the sliding approach complexity is usually of the order of like m plus n, which is like the length of the first string with a length of the second string. And yeah, and even here, we are having the same enough the second string with the length of the first string. And are we doing anything further? Nothing. So that might be the answer here too, like of the order of m plus n. Yeah.

Mythic Unicorn: Okay. Awesome. Sounds good. I think for feedback, like it's good to have in your knowledge that permute, and all those kinds of normal functions... You came up with the solution pretty quick. But like, since it's not very... it's a very costly solution of sorts. Right? So like, takes time to get to the actual sliding window approach, which is a better solution. Yeah. But otherwise, you got to the sliding window approach without much without many hints or anything, so that was a good thing. Um, and, yeah, I think pretty much it. I think you need to spend some time on figuring out time complexities of stuff.

Phantom Storm: Thank you. Yes, I realize that too. I'm when I'm practicing. I kind of like think the solution is important. And I can derive the runtime complexity if I understand that well, but I just realized that that is not the case. I need to when practicing also I need to derive runtime complexity once to solidify my understanding, so that I can do it. Yeah, yeah.

Mythic Unicorn: Okay. I think otherwise, it was really good.

Phantom Storm: Thank you. Thanks a lot for the interview.

Mythic Unicorn: Oh, yes, definitely. Thank you. Bye.

Phantom Storm: Bye.