Python Interview with a Google engineer

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

Python interview with a Google engineer: Edit distance string comparison - YouTube

Interview Summary

Problem type
Edit distance string comparison
Interview question

1. Given two strings s1 and s2, write a function that returns if the two strings are equal in a case-insensitive way
2. Expand the first function such that it returns True if the edit distance between s1 and s2 is 1 or lower
3. Expand the function to take a third parameter designating the comparison tolerance between s1 and s2 to be 'n' edit distances or lower

Interview Feedback

Feedback about The Mighty Eel (the interviewee)

Advance this person to the next round?
Yes

How were their technical skills?
4/4

How was their problem solving ability?
1/4

What about their communication ability?
4/4

Great job! You worked through the easy version of the problem very quickly and then were successfully able to build on it to get to more optimal solutions and added constraints. My only suggestion would be to be more vocal as you are thinking through solutions. It's good to think through a solution before starting to code, but it helps to let the interviewer know your thought process just to keep the conversation going and allow the interviewer to guide you at that step as well.

Feedback about Intergalactic Avenger (the interviewer)

Would you want to work with this person?
Yes

How excited would you be to work with them?
1/4

How good were the questions?
3/4

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

Interview Transcript

Intergalactic Avenger: Hello?
The Mighty Eel: Hey how's it going
Intergalactic Avenger: Going pretty good. Yourself?
The Mighty Eel: Pretty good. This is my first one of these so pretty excited.
Intergalactic Avenger: Okay so let's just dive on right in. So I'm going to ask you an algorithmic question if that's alright. So there's a little selector box on the top right of the coderpad. It says plaintext now and you can pick any language that you think makes sense for an algorithmic type question.
The Mighty Eel: I'll probably do Python.
Intergalactic Avenger: Python, okay those are usually good for these things. Okay we're going to start with the basic problem and add to it. So the first one is pretty simple and the idea is you're going to define a function that takes in two strings and returns whether they're equal in a case-insensitive way. So of course Python has this but we're going to work through a couple additions to this once we get the basic one down.
The Mighty Eel: Okay cool. So I mean there are other Python built-ins that could make this pretty easy as well. Like turning a string to lowercase or uppercase and then comparing them.
Intergalactic Avenger: You can use any of those. And we'll talk about the implications of using those and all that kind of stuff.

... [Truncated for brevity]

Runtime Complexity and Space

In the case where the strings are equal it's the same as before. In the case where they're not equal by 1, runtime would look like....it would also be between O(1) and O(n) and memory would be the same as before too. Memory would be O(1).

The Mighty Eel: Excellent. And now, the really tough one. So this is great, it's all good so far. And now I want to add a parameter where, instead of being hardcoded to 1, I could put a parameter at the end here for how many edit distance I'm willing to tolerate. So if I did like 2 here, on the last one there's 2 deletes instead of just the 1.

Intergalactic Avenger: Yeah I mean this is pretty hard...

... [Truncated for brevity]

The Mighty Eel: Yeah cool thanks so much, that was a lot of fun.

Intergalactic Avenger: Alright well take care and good luck with all your interviewing.

The Mighty Eel: Bye.