Python Interview with an Amazon engineer

Watch someone solve the validate binary search tree problem in an interview with an Amazon engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Validate Binary Search Tree

Interview question

1. Given the root of a binary tree, determine if it is a valid binary search tree (BST).
2. Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
3. Given an array of points where points [i] = [xi, yi] represents a point a home to deliver to and an integer k denoting the number of deliveries to make, return the k closest points to the warehouse (1, 3).

Interview Feedback

Feedback about Clandestine Borogove (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem-solving ability?

3/4

What about their communication ability?

4/4

You did a really good job with this interview. You mentioned being at the point where you couldn't code in an interview and spent a lot of time working on it in between interviews, and it really showed. If you performed like you did here with the graph questions, I would recommend a higher during the debrief. That being said, you mentioned you struggled with graphs and really worked on them (which definitely showed), so I'm curious if I'd see the same data with other types (i.e. the k nearest neighbors question I asked at the end). That's when you really need to focus on your approach to the interview. If other interviews evaluate those areas and think you're doing well as well, then I have no doubt that you'll find your next job fast.

Great job!

Feedback about Indelible Raven (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

4/4

How good were the questions?

4/4

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

4/4

Interviewing with Kevin was exactly what I wanted today. His questions were great and feedback was awesome. Kevin gave me good tips on what I need to improve on. I am a strong believer in 'room for improvement'. Thank you, Kevin. I will certainly work on problems other than graphs and trees. Really appreciate your time today.

Interview Transcript

Clandestine Borogove: Hello.\nIndelible Raven: How's it going?\nClandestine Borogove: Hi, good morning. I'm doing well. How are you?\nIndelible Raven: I'm doing alright. Let me turn up my sound one sec. Alright, maybe that will be louder. So, just kind of curious. Can you say something real quick?\nClandestine Borogove: Yeah. Do you hear me alright?\nIndelible Raven: Yeah, that's better, cool. Anyway, Hi, I'm Kevin, I am a software engineer at [FAANG Company] and even further I'm an interviewer for [FAANG Company]. This is an anonymous platform, feel free to share as much as or as little as you want. But what I'm curious about are your goals for this interview.\nClandestine Borogove: Sure. My name is [Name]. I recently gave an interview at Microsoft. And I've given Facebook interviews in the past as well. My biggest struggling point was graphs. So they asked me two graph questions. One was a basic depth-first search and the other one was to count the number of islands in an m x n grid. And I struggled with those, I did the second question, but I didn't do the first one. So this time, I really focused on graph questions, I practiced them a lot. So I would love if you can ask me, you know, some graph questions. And I'd like to test if I've prepared well for them.\nIndelible Raven: Yeah, could you give me a second, I'll look up a different one. Because you just told me the one I usually ask.\nClandestine Borogove: Okay. I mean, I don't mind telling you and providing you an answer for the one that you typically like to ask just so because I've struggled with graphs. I've struggled with grid questions in the past, and I've seen it's a very common pattern in the interview, so I thought, you know, I need to prepare for these.\nIndelible Raven: Well it's a different one, it's a little more difficult than my typical, I usually ask a number of island problems. But hopefully I have a different one. The problem is it's been a while so I gotta make sure I remember it. Because I was asked it during Google interviews and it's really I wanted to say a fun one, but let's be honest, that one was not fun at all. Because, yeah, if you want to dive into while I look at the different one, if you want to dive into the number of island problems, if you want to see if you get feedback on that.\nClandestine Borogove: Sure. Could you do you mind giving me just a grid?\nIndelible Raven: Yeah, so do you have a coding language which you want to use?\nClandestine Borogove: Oh, yeah, I switched it to Python.\nIndelible Raven: That's not how you do this, I think it's that? Yeah. Yeah, there's a grid for you. Totally made up. But that'll work. By the way, I'll leave about five to ten minutes at the end. Maybe a little bit longer if you want to ask me any questions and then also give you some feedback.\nClandestine Borogove: Cool. Thank you. So for grid type questions. First things, let me ask you how many moves that are allowed? Typically, up, down, left, and right moves are allowed, but I just want to make sure if that case is acceptable to you?\nIndelible Raven: Yeah, I usually go with up, down, left, right.\nClandestine Borogove: Okay, cool. So what I'm going to do is in this case, typical runtime, optimized runtime would be O of N times M where N is the number of rows, M is the number of columns. So what I will do is define, or let me just give you a verbal algorithm first, what I really want to do here is loop over the number of rows and the number of columns, where the number of rows would simply be the length of the grid. And the columns would be just given by the length of grid zero. I'm calling this typical, this grid as grid. And what I want to do is define a visited set where I want to keep track if I've previously seen this cell or not. If I've seen the cell, then I don't want to loop over it again. Otherwise, I'll get into the cycle. If not, then I want to also check whether the cell is in bounds, I never want to get out of bounds. And if all of those conditions are satisfied, and I'm assuming another thing I should have asked you, I'm assuming one is land and zero is water. If that's the case, then I don't want to, I only want to count or increment my count if I have one. And, you know, ignore a cell if it has zero. Does that make sense so far Kevin?\nIndelible Raven: Yep, that works.

Images
\
Microsoft Interviewer - Unique ID generation \
Google Interviewer - Order statistic of an unsorted array \
Google Interviewer - Most frequent integer and pairs of integers sum \
Google Interviewer - Triplet Array