Technical Interview 2

My second round was conducted by a very pretty and intelligent young lady. She helped me a lot, by giving suggestions and ideas to improve my solution.

Problem 1

You are given a binary tree and two integers k and d. Print all the nodes at a distance of d from k.

Solution

My first solution was to find the distance of every node from node k using LCA and then print only those nodes whose distance is d. This is my idea. The time complexity of my solution was O(nlog(n)). She wanted it in
O(n). She helped me build all the logic and finally I was told to write the code.

Problem 2

You are given an array a which consists of only 0, 1 and 2. You have to sort the array.

Solution

My first solution was to hash the frequency of the array in one traversal and then fill 0s, followed by 1 and then 2s in second traversal. She was satisfied but wanted it in single traversal. This is the solution. I was told to write the code.

Amazon pool campus placement drive was conducted in March 2019. There were total five rounds, first round being an online coding round was held on Hackerearth followed by three technical interviews and one bar raiser cum technical round.