You may find my Round 1 interview experience here.

Status: 4th year ECE student at Tier 2 college
Position: SDE1 at Amazon
Round : 2
Location: India
Date: March 2022
Opportunity type: On Campus

Round 2: 2nd Technical Interview

1. Introduction

2. 10-15 min discussion on internships, projects. What was my role during the internship specifically? Technologies used in projects, why one over the other?

3. Coding problems (3):

a) Given a target node and an integer k, return a list of all the values of nodes that at distance k.

Example:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explaination: You can find 7 and 4 via going down the descendants of TreeNode* 5 and can find 1 via the parent of 5;
Illustration:
5->2->7
5->2->4
5->3->1

Approach:
First create the parent pointers using a hashmap, then use a bfs traversal starting with target node in the queue and a distance 0. Then, add the 3-directional siblings of queue's front to the queue and incremented the distance by 1 at every iteration of queue. We break out of the bfs when either queue is empty or diatance == k. Finally, all the elements left in the queue are our required elements.

Summary:
Solved the question, it took half an hour to give the approach and code. Also, made a small mistake in the code which I was able to resolve with interviewer's guidance.

Problem Link: https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

b) Given a list of numbers representing length of ropes. Connect the ropes with minimum cost, if cost to connect two ropes is equal to the sum of their lengths.

Example:

Input: [1, 2, 3, 6, 8]
Output: 41
Explaination: Cost of all the joins : 3 + 6 + 12 + 20 = 41
Illustration:
1 + 2 = 3
3 + 3 = 6
6 + 6 = 12
12 + 8 = 20

Approach:
Create a priority queue (min heap) and all the elements in it. Add the two smallest ropes from the priority queue, add their sum to the cost as well as insert their summation back into the priority queue. Finally when there is only one lement in the priority queue, return the accumulated cost.

Summary:
Gave the exact approach within the first 30 seconds of the question. The interviewer seemed to like my fast response but then again gave me another question.

c) Given an integer 1 <= n <= 10^5 and integer 'm'. The task is to tell the max step we can reach starting from 1, if at every step 'x', our 'm' reduces by pow(x, 2). And we can not move ahead if m becomes 0.

Example:

Input: n = 10^5, m = 10
Output: 3
Explaination: m at every step: 
1 : 10 - 1 = 9 -> move ahead
2 : 9 - 4 = 5 -> move ahead
3 : 5 - 9 = -4 -> return;

Approach:

Gave a linear approach but the interviewer wasn't happy with the O(n) time complexity and asled me optimize it. With the help of a couple of hints, I came with a binary search solution which reduced the time complexity to O(log(n)). After which, I managed to further optimize it to a O(log(sqrt(m)) solution.

Summary:

The interview seemed to satisfied with the last version of code that I wrote, so all's well that ends well.

Synopsis:

Solved all the given problems, though took some extra time. The interviewer did gave me a few hints here and there and I was able to understand and utilise them. So, overall, it turned out to be yet another pleasant interview.

Edit: Got an email for the next round, will update after the interview. Happy Coding! :)

P.s. It took a lot of time and effort to write this post, so if you found this to be useful in any way. Kindly upvote. Thanks!