Python Interview with a Walmart engineer

Watch someone solve the permutation in string 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

Permutation in string

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 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. Hi.

Mythic Unicorn: Hi, how are you doing?

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

Mythic Unicorn: Good. Okay, I guess 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 see.

Phantom Storm: Okay. Write a function to return true if s2 contains a permutation of s1. One of the first strings permutation is a 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. Got it. Yeah. Okay. Yeah, so it's actually like two problems. in one, the crux of the problem is finding all permutations of the string s1. And then you evaluate one permutation at a time, find out if the permutation is present in string s2. And if its 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.

Mythic Unicorn: Yeah, okay.

Phantom Storm: 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. Okay. There is actually graph algorithms to do the permutations like depth first search, is it depth first or breadth first? I'm trying to collect one of them. And then we can go doing that. Let me go, let me write outline and then define it. Okay. Find... Given two strings s1 and s2, write a function to return true if s2 contains a permutation of s1, okay. Find... So, how do I get the permutations of a string? I'll think of some way. Usually, like there are higher order functions in Python available, like it has tools and data tools can provide computations and...

Mythic Unicorn: Let's not use that.

Phantom Storm: Yeah, no. Yeah, I get it. Like that's not the point of this. So permutations, I am trying to recall... I'm trying to see the depth first search or the breadth first search would be the most suitable one for the permutation. So let's start with ab. If 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, a. So, the way to do that is, okay, let me see... This is... I do everything before i and everything after i. Okay, and then. So we have to find out the permutations of remaining. So, the way to do that is, okay... Okay, I take, so, let's, I'll try to do it recursively. And if I do it recursively it's actually a graph with the a is connected to b. And find all the permutations of everything. Okay. I think breadth first search is the option to kind of like find out, okay, so it's not really depth first search. So we have to take one and, and all the different permutations, except for the character, take one and all the different permutations for the character. So when a 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 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 the value of the string. 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's on my mind 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. So...

Mythic Unicorn: Okay. Since you are having troubles with permutations, how would you do permute of 123, a string like 123, how would you permute 123?

Phantom Storm: Okay, so I'll 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? So, what strings will it generate? Okay, yes. Yeah.

Phantom Storm: Okay. So like, what did you do over here the first time? What were you doing in the permute?

Mythic Unicorn: Yeah, so in the permute, I was taking one character and I was fixing on the... for 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.

Phantom Storm: So basically, last two characters, you're just swapping?

Mythic Unicorn: Yeah.

Phantom Storm: Okay, and then you somehow have to get back to 123 or do you continue from the last two characters?

Mythic Unicorn: Uh, I will have to get back to 123 and yeah, I'll have to get back to 123.

Phantom Storm: So from here you again got back to 123 and then what did you do to get to 213?

Mythic Unicorn: I fixed on two and then consider the two characters one and three.

Phantom Storm: Okay, so you kind of swapped two and one, so two became first. Plus you did permute of one and three.

Mythic Unicorn: Yeah. Yeah. Okay. Yeah. Okay.

Phantom Storm: So like, do you see where I'm going kind of?

Mythic Unicorn: 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 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 again the rest of the characters. So I mean for three characters, it will work, but I do not know what will happen for the four characters. But I'll start with the three characters in the code and then I think I can modify it for the n characters.

Phantom Storm: Yeah, okay. What will happen is there was only one character?

Mythic Unicorn: If there was only one character, we just return.

Phantom Storm: So what does your ending condition kind of become?

Mythic Unicorn: Okay. So if my return values is 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. Although otherwise, you kind of like go through the iterate through the iterate through the indices of the characters, pick one character and then permute to the rest of the characters.

Phantom Storm: Okay, so let's do that.

Mythic Unicorn: Okay. Thank you.

Phantom Storm: So 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.

Mythic Unicorn: So, how would I get back to 132 213 back? So, I was imagining that there is a higher, the top level for loop is the one that is actually keeping one character and then when okay...

Phantom Storm: So, the permute function should kind of like for two character permute string, it should return both three two and two three, which means that, 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?

Mythic Unicorn: I think I slightly understand.

Phantom Storm: 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, 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?

Mythic Unicorn: So, do we... I mean, we... Okay, so, I think we need to place the character the place the strings in a stack and then kind of like go forward with analyze all the values in that stack and then push it. Is that?

Phantom Storm: And like how will the stack get back to 123 again?

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

Phantom Storm: Keep going with this.

Mythic Unicorn: Yes, yes, I think once I understand the question, I think I will able to get it. It hasn't striked me yet. So, let us do one is if the permutation is one return, yes, if length is two okay. That's for like for two characters. Let's assume that I pick up one here. And the remaining is actually everything before one. I mean, this is not complete, but I hope this will help me find the problem. So I am having an array of results and for each index and the length of here, I will go take a character in here 123 I'm taking one and then remaining as a two three. And permutations of two three will be... So, I'll have one with permutations of two three and permutations after three if length is equal to is equal to one, no.

Phantom Storm: So the permutations function returns a list, right?

Mythic Unicorn: Yeah.

Phantom Storm: So the remaining will give you, will add everything like key to every element of the list?

Mythic Unicorn: I am wrong here, this should not be a single permutation 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 know that this is wrong, so that's why I'm kind of like to get back. So, how do I do permutations. I think, to do the permutations is take an index and permute the rest of the things so that until here is correct: take an 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, this 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 return it. So I'll do something like that. Okay. So, I mean, I'm going past this 123, but I'm going from the other example, I have stack. Okay. So, what I'm doing here in the permute is actually putting a string in the stack, and then popping the string off. And I'm actually going from the value popping this string off and then going to the length of the string and permuting the character of the string without this, so... Okay, I will have the value of the index plus the remaining into the stack. And when I do this way, what will happen is will the stack always go through? So not necessarily... so if the stack has abc, then I will have abc as popped and then one, zero, two as the index. I'll have... okay. Yeah. Okay, and then you're popping off stack. So, okay. So, I have done the list of words with the permute. So permutations when I go here... And all permutations will be, actually we are defining the global here. So I would have it in the list of words. Okay, I just do permute, yes. Okay, sorry?

Phantom Storm: I think you don't have a return.

Mythic Unicorn: 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 a breadth first search here and and seeing if that's the thing. Oh you mean for this? I don't know why this... okay. Shall we try it?

Phantom Storm: Yeah.

Mythic Unicorn: Okay. So let's see if that results in 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 then I was struggling to recollect it, this was 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 the permutations of the remaining value, which I'm doing here and, 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, I will permute it in the form of like, a recursive value with a stack and keeps going. So yeah.

Phantom Storm: I have a couple of more test cases.

Mythic Unicorn: Yeah.

Phantom Storm: Let's go over the length of four.

Mythic Unicorn: Okay. It should return true. Let's see if it does. Okay.

Phantom Storm: How would you kind of go for a corner case?

Mythic Unicorn: Okay. Okay, corner cases. Okay. Let's see if the same thing and then just reverse that completely. Let me see. Okay, my empty strings was not a good thing. Okay, I think yeah, empty string was like an extreme corner case. Okay.

Phantom Storm: What would be the runtime for this?

Mythic Unicorn: 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 the different permute values is like you take one and then different things, one and different things, one and different things. So it's... Sorry, I'm calculating. Okay. So we are having n. And for each n, I am kind of like permuting, all the different n. So it's O(n!), because I think each of them will be going out one letter at a time and then finding out if the value is present in that. So was that correct?

Phantom Storm: Yeah, yeah. So I... yeah, I just want to know, the runtime complexity of this.

Mythic Unicorn: 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 n in the end, traversing the entire tree with the n. So I am... and it's not such. It's O(n!). It's O(n!) is my understanding of the runtime complexity.

Phantom Storm: Okay. O(n!) for the string, right?

Mythic Unicorn: Yeah, it's n into n factorial is what I'm kind of deriving, but um, if n into n factorial is same as n factorial.

Phantom Storm: How many permutations? Like the list of words can it have?

Mythic Unicorn: Oh, okay. Yeah, that list of words have the permutations of n... So it's three. And six, actually, it is. It's n factorial. So you have a string of n, we'll have n factorial permutations. So n factorial is going through all the different permutations and getting that thing. It is the runtime complexity of this is we have n for the number of characters, and then there's a number of permutations in the string that's n factorial, okay. In fact of the length of n. So for this particular implementation, I have like, how many times am I executing the stack here? I am executing the stack while loop. Let's start n factorial times, it's actually... and then I will be having n. The complexity here looks to me that it's actually O(n^2), actually, that's the... 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's the worst case complexity that we are looking at. Hello?

Phantom Storm: Yeah. So O(n^2) in the worst case complexity?

Mythic Unicorn: Yeah. Yeah. I'm deriving it, so I'm not entirely sure about this.

Phantom Storm: Okay. And then the list of words will have how many permutations?

Mythic Unicorn: The list of words will have all the permutations of a string, that will have O(n!) permutations. Like, n factorial being, so for example, if we have 123, is supposed to have all the different for 123, it's supposed to have all the different things.

Phantom Storm: So for four, how many permutations do we actually have?

Mythic Unicorn: So for four, that's actually 12 into 24. So we're supposed to have 24 length? And if... Yeah...

Phantom Storm: So do you think the permute function should go through all the permutations?

Mythic Unicorn: The permute? I didn't get a question, come again?

Phantom Storm: Basically, the permute function, if it has to get all the permutations, it will have to like, go through all the permutations, right?

Mythic Unicorn: Correct. Yes. Yes. Yeah. So the complexity is not actually O(n^2), it's actually O(n!). That's my, that's the understanding. Yeah.

Phantom Storm: So n factorial for the permute function. So it basically becomes n into n factorial. Can we improve the time complexity?

Mythic Unicorn: Can we improve the time complexity?

Phantom Storm: I guess we are 45 minutes in. Or where can you improve the time complexity?

Mythic Unicorn: Yeah, like, in the beginning, I was saying that, this approach seems like very 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 you do in fact. The time, if we have a completely different approach, wherein if I use some kind of like a bottom of dynamic programming, where I think I can use some kind of like indigenous values in such a way 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 this string from the length of the first string and make sure that each of the characters is 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 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 string through only once. And we will be going through each of the characters in in the string once. So, it will be of the order not like n factorial, but it will be in much lower, for example, it will be of the order of length of the second string into the length of the first string. So, that can be one approach. But was I able to explain the second approach? Yes, 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 window two at a time and if both of them present, no, okay, then go for the bdg. Use some kind of like a sliding window to solve this problem, is a completely different problem that will be more efficient. Okay.

Phantom Storm: The thing is, you don't like, okay... I'm kind of, again have to take care of characters instead of... or character frequencies, I guess. 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 in each sliding window, all the character frequencies in the source string document, 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... 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 the time complexity of the this approach. The second approach I'm saying. 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? So can I reject any of the characters? Yeah, I am not able to think of any optimization and the permute function, this approach where I have to exhaustively get all the permutations before I land 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 there any other thing? This is a standard breadth first search. So 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?

Mythic Unicorn: Yeah, I think sliding window approach is an improvement. What do you think the runtime complexity of the sliding window will be.

Phantom Storm: So the runtime complexity will be of course, the length of the second string, multiplied by... We go one window at a time and then find out the frequency frequencies. We go one window at a time and then find out the frequency of the characters. Let's see. Okay. Okay, so this is worst case, okay, so I kind of like for each character that's going... So, I am having that divided. We are going through each character in the second string and each we are finding out all characters present for the second string. And we are going for like each character in the string. Worst case that will be of the length of the second string multiplied by the length of the first string. It's definitely less than that, but big by some slaps value, but this is the... this is the... Oh, sorry.

Mythic Unicorn: Like what is usually the sliding approach runtime complexity?

Phantom Storm: The sliding approach runtime complexity is usually the sum of the two strings actually, like, we go to the second string length with the... 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 the 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 to like, of the order of n plus m? 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 a very, like it's a very costly solution of sorts, right? So like, takes time to get to the actual sliding window approach, which is the better solution. Yeah. But otherwise, you got to the sliding window approach without without many hints or anything. So that was a good thing. 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 realized that too. When I'm practicing, I kind of like think that 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. When practicing, I need to derive runtime complexity once to solidify my understanding, so that I can do.

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

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

Mythic Unicorn: Oh, yes, sure. Thank you. Bye bye.

Phantom Storm: Bye.