Python Interview with an Amazon engineer

Watch someone solve the circular queue 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

Circular queue

Interview question

1) Sum of nodes where grandparent is even in a tree. 2) Split list. 3) Build a circular queue.

Interview Feedback

Feedback about Warp Lemming (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

3/4

He is a great thinker and explainer. - Explains solution with easy words and visually - I just suggest to do more practice

Feedback about Orthogonal Typhoon (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

2/4

How good were the questions?

2/4

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

3/4

N/A

Interview Transcript

Orthogonal Typhoon: Okay, what's your preferred programming language? Python great. So, what type of questions to me ask to you?

Warp Lemming: Data structures and algorithms.

Orthogonal Typhoon: So, start from easy one a or start from medium level?

Warp Lemming: From medium or hard.

Orthogonal Typhoon: Okay, let's start. Yeah. We have a tree, a binary tree. And we want to find node sums, which their grandparents are even. So let me explain. You have binary tree. Let's say it's 6 3 8 for example. Okay, great. You have let's say 1 2 3 for example, and here we have say the right node of one is four, then nine, eight, one, two. Okay. Okay. And here are the right is six, five. So, we need the sum of all nodes, sub nodes let's say, with their grandparents value is even. So, here one, two and three, five as a grandparent is six grandparent is the parent of parent okay. And they have these grandparents is six and six is even. So, we need to sum up all these elements. So as they are and the other ones, which let's see eight is also even and it is, yes and one two and five and we have the sum. So create for yourself your test cases, your design the method for this one, okay.

Warp Lemming: In level, there's possible sub values that grandparent is even another sub level grandparent is not even. So we cannot do it that DFS. Okay. So for each value, I will move forward which grandparent. Okay. And it's been good. So for six, there's no grandparent and no parent. For eight, there is no grandparent, there is a parent, which is great. For five, grandparent six, and the parents, we know here that five has a grandparent that's even. So we have to add it to the sum. Right let's say that we have a global variable that will save the total sum. So, we can do a traversal with these variables for each node to check if the grant parent is even. Then we will add myself to the sum. Otherwise, I will just continue. Great, okay, it was all good. So, what we can do in order traversal. How does it sound?

Orthogonal Typhoon: Sounds great. So we can move to look at the code if you want.

Warp Lemming: Yeah, so I need I kind of assumed that they have a tree class or I should write the tree class.

Orthogonal Typhoon: Yeah, you could assume that it's already exists.

Warp Lemming: I will assume that we have a global value for the sum. So I have another function. This would take down... Oh, no. So I'm here if the node is none, I can return. So I don't have a parent so I will not have a grandparent, right? So I just... Well, here I'm setting myself as a parent for my child. And I would pass from my parent the info about the grandparent. Okay. Now, check if I don't have a parent, so I will not have a grandparent. So if my grandparent is even, I will add my value to the global sum. Let me check this. So as we know... Then I'll go to the left.

Orthogonal Typhoon: Okay if you want, you can create some test cases, run it.

Warp Lemming: I can run it, okay. So the tree doesn't matter. I don't know the height of the thing. I think this is working.

Orthogonal Typhoon: Great. Could you please tell me about the time complexity and memory complexity?

Warp Lemming: Yeah. So, the time complexity is O(n) since we are going in before a DFS traversal, which is post order traversal. This is O(n) time. The space will be O(h), regarding to the recursive calls and h is the height of the tree. So, if the tree is skewed. This will be O(n).

Orthogonal Typhoon: Thank you. Let's move to another question. Yeah, sure. You want me? Clear here clear? This one? Yeah. Okay, we have some word one. And we have word two. We are only permitted to add a character, remove a character, or replace.

Warp Lemming: Edit distance. I know this question.

Orthogonal Typhoon: Yeah, exactly. So, find the minimum change we could do to convert word one word two.

Warp Lemming: I already know this question.

Orthogonal Typhoon: Okay, so you want to change question? Yeah?

Warp Lemming: If you can, but yeah, I already know this. This is dynamic programming. I will use top down approach to add or remove or replace, this will be O(nm).

Orthogonal Typhoon: Yeah, okay. Okay. Let's move on to the next question. We have a linked list, a singly linked here, so we have node one, we have node two, node 3 4 5. Let's say we need to buy... I think that maybe, you know this question also, but it's very interesting question. So we should change the positions. So we should move the last node after the first node l5, then keep the other nodes l2, then move the next last one, l4, then I keep l3. So we are changing. We are moving the last one to the current next. Yeah.

Warp Lemming: We have two pointers, something like this. We take P1 then we will be one go to the right. Then we take P2, then P2 will go to the left. Something like that. Yeah, forget about the left but if it's already so it's something like that. They will take the one that will go to the right. And they will take a P2 to L1 and go to the left. Then they are in each other. Right.

Orthogonal Typhoon: So yeah, okay. Our node, is this node, maybe. Yeah. And it has value. And yeah, without breath.

Warp Lemming: Right. Okay, yeah. So the first solution that I can think about is we don't have a prev pointer, we can reverse the list. While we have different nodes, so we can take alternatively, like from the fence than from the second list, the first. It's just nicer. So I think they have something like this and first of all... Then I'm taking the P2 which is fine, take a P1 which is in his MC. Go here I can see that they are the same way because yeah when they when they are they will meet right... I can break one of this. If they were even, I think they will not reach each other. So, we can see that and come and go one will go we know. Yeah. So, they will meet. So, yeah what was it not me I can take a jump right. So that the time and space is O(n). So, they are going on the branch, we are reversing the list, setting another list and then traversing it.

Orthogonal Typhoon: You will, so you will copy the current list then reverse, then traverse both of them. Yes. Yeah. Yeah. So, maybe there is some better way.

Warp Lemming: Yeah. According to time we can do better right because we will need to traverse all the length. So, the time will be at this stage maybe right maybe we can do better.

Orthogonal Typhoon: Say you could you can change the input list. So you can do it in place. And in place and in place input is not calculated as extra memory.

Warp Lemming: Yeah. So let's see. If we can cut the array the list into two halves... Okay. We have reversed this like to have been one. That's right. So I can say I have two halved. I will reverse with our second list. And then I'll reverse the alternatively, as the first approach. Right, so I just need to reverse of about half of that. So it's even just, this will work that thing that we see about us so far. Okay. So I need to think... Yeah. So the third, the second algorithm is to take the first half of the list, and the second half reverse second half. Okay. It's already complete. Great. Great. Yeah. This will be a O(1) space.

Orthogonal Typhoon: Yeah, exactly. If you want, you can write code, but if you don't, we can move to another question. I think this will not be challenging, because I know the algorithm of finding the middle with the slow and fast pointer. And then the reverse list, it is easy.

Warp Lemming: Okay, you know, do you want a tree or not tree?

Orthogonal Typhoon: I do like, I do like. I'm if you if you have dynamic programming or graphs, so the better because...

Warp Lemming: Today I was faced with a good algorithm, it was really challenging for me. Let me ask you, maybe you didn't face this equation. So designing circular queue. A circular queue is a data structure which the operations are performed based on first in first out principle and last position is connected back to the first position. Is something that means buffer ring. So we have let's let me copy the exact class maybe, so clear. We have an enqueue method. It it's for adding. Yes, exactly. So the other is front, is just returning the element from the front. rear is there from the rear of the queue. So if queue is empty, return minus one. So is this is circular and for enqueue and dequeue, we are, as you see, returning a boolean. So if we can insert element to the queue, we are returning true. Otherwise return false so we can we can insert the queue and also for abort if we can't dequeue from queue, we are returning false, will be canceled.

Orthogonal Typhoon: The k is the capacity of the queue?

Warp Lemming: Yeah, k is a capacity and maximum capacity. And for example, we could to say these operations... Let me copy the test cases for example. And the results are here. Yeah, well, it could be something complicated, but you can just ask...

Orthogonal Typhoon: No, but I think we can use linked lists, we have space, we can add. And when we dequeue, we were removed from the back end. So, I can now I can use linked lists. And there is another double ended queue in Python. If you know, the double ended queue, which was being.

Warp Lemming: You used priority queue instead linked list.

Orthogonal Typhoon: Ah, using an array, right? You want to use an array. It's more performant. Okay.

Warp Lemming: Yeah, so if it's a list, it's very easy, right? But you can add to the end, you will have array of size k capacity, you will add to the end if you have capacity, if you don't have you will remove from the end, you will return false. Otherwise, the dequeue are removed from the head.

Orthogonal Typhoon: But you can continue using the linked list. I'm sorry, you can continue. That's okay for our interview. But yeah, with that...

Warp Lemming: Okay. So, if we want to implement array, so let's say that we have, okay... so enqueue... So, and the numbers are positive or negative an integer. But we can assume that it's positive integers?

Orthogonal Typhoon: Let's say they're all positive.

Warp Lemming: Yeah. Yeah, I can work with minus one. So here, if I want to enqueue, I can see that there's no minus one here. So I will close because I'm done. When I dequeue, I will choose the one on one it'll move up. Yeah. So whatever the head of the same position that is full and into when also the same. So yeah, when we are the same as the minus one, so I have empty, we are the same, I'm not minus one right. So, I have one here. So that the thing and the head will be here right. So let's say that this is a tail, this is a head. And it is full it is the full condition. When it is removed, this is the tail will be moving and are removed. The tail will also move this they will also be moving with model for sure. Yeah, the other thing, this is the last one. And so what do you think, how does it sound?

Orthogonal Typhoon: Sounds great. But think about that... For example, if you put at... So, enqueue and dequeue all the elements... You enqueued all the elements. So then you dequeued all of them. How do you understand that the queue is empty?

Warp Lemming: I said when tail and the head are the same position and they are pointing to minus one, okay. So, if they are pointing to minus one, when I add the head will move right. And will point to the next one. Yeah, the tail will stay right. Yeah. That is connected to the dequeue operation.

Orthogonal Typhoon: Okay, okay. Great. Right. So, let's work with that right.

Warp Lemming: Yeah, yeah. So, okay, let's implement them. Well, I will I can't read. Otherwise, I will add. I don't want to go over such variations.

Orthogonal Typhoon: Let me ask you a question. So if queue is full, so you're returning false. Yeah. What if we return let's say our circular queue's responsibility is that if the queue is full, we can write from the beginning, so it's circular. Just adding to the first node.

Warp Lemming: Yeah, we will add a special node, we can add like here this is circular, right? But when we dequeue, I remove the one, this will become minus one, the same will move, and then I will add. Right okay, okay. Right. So, the this is the perfect example here enqueue. Yeah, you know, examples number one right. I can move anything there. Okay. I will put the plan in my response to the fifth one. So let me jump into it. All right. So they are the same position okay... But they are the same position and they have -1. So they are the same position and doesn't have -1. So that is full situation. Now, either front and rear. So if I don't have values each one of them what I can do... but I should pretend minus one... can I return minus one? Yeah? And the rear, I will return and it'll be minus one right? So if I have a zero, so the tail is minus one was returned. Yeah. What do you think?

Orthogonal Typhoon: It seems okay. Let's check leetcode. Let's see this one. Cool. So in line 15 there is an error. This assignment is index out of range.

Warp Lemming: Maybe this is it?

Orthogonal Typhoon: The error is one line before that line. So it...

Warp Lemming: Yeah, I know. But, but the head will be moving here. So if the k is zero maybe this is another case. But I'm wondering if this is the error.

Orthogonal Typhoon: Okay, it seems okay. Let me write all the spaces... Okay you have an error. So, let me send to you. So, let's say you have this input, I think you will understand this one.Your output is this one, but the expected answer is this one.

Warp Lemming: Yeah. So this one is within that... I have to explain that. So, you mean yeah one of them was there because it was circular. So, I thought that was one of the problems. Yeah, I am pointing to the last. So, or maybe

Orthogonal Typhoon: So, problem what's the problem. So, we have circular queue with size six. When we are enqueue six. Yeah, yeah. in queue six it show it returns true. It means we are successful. And we are want to get rear. So, we added only one element so, rear should be the current.

Warp Lemming: Yeah, so, I removed the minus one, now it should work.

Orthogonal Typhoon: Oh yeah. So I thought that will change. But now, our first test case is failing. The other one works fine. If you want, I can send you the actual and expected.

Warp Lemming: I can see I can when it's full. When it's full, then I need to return true. What do you think overall?

Orthogonal Typhoon: Overall is great. So actually, I took a lot of time to figure out this problem, actually, but you are near to the success. It's great. How are you preparing for interviewing, only leetcode?

Warp Lemming: I have practiced on interview pad. I'm doing a lot of the peer rounds. And now it's the first time interviewing.io. I use Cracking the Coding Interview book and LeetCode.

Orthogonal Typhoon: So you're good. You did great. It's great. Actually, my first interview in interviewing.io, I only did first one and take a second one was medium, which wasn't a hard question. But I don't know why I can't solve the problem. Maybe I stuck with something. And actually, when you're stuck in something, you're stuck. So you can't it can't break as well. So the goal is to think about all his case, and write once rather than write and changing because fixing issues is hard.

Warp Lemming: Yeah, takes more time.

Orthogonal Typhoon: Yeah. So I can send you this question link if you want to try it then. Okay, I'm writing here. Yeah. Oh, yeah. Thank you very much. It was great. It was interesting. So goodbye.

Warp Lemming: Thank you.

Orthogonal Typhoon: You've been so good luck with your interview. Bye.

Warp Lemming: Bye bye.