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.

Python interview with a Walmart engineer: Permutation in string - YouTube

Python interview with a Walmart engineer: Permutation in string

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.
Read more about the questions

• Permutation in 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: 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.
...
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.

The runtime 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, length of the second string multiplied by the length of the first string, would have been the time complexity of this approach.