I was invited to Amazon, Delhi office after clearing online test at hackerearth. We were made to sit for about 20 minutes after which interviews started. When i entered the cabin, two interviewers were present there. They seemed to be very friendly. First of all, they introduced themselves. Then i introduced myself. Then they presented me first problem that was based on trees. The problem goes as follows:

Given a prefect binary tree, print middle nodes of it without knowing the height of the tree.

Sample Input:

			1 
		  /    \
	    2       3
	  /   \    /  \
	 4     5  6    7
	

Sample Ouput
2 3

Sample Input

		   1
		  /  \
		 2    3
		 

Sample Output
2 3

I told them an approach including fast and slow pointer and pre-order traversal both. Then they asked me to write code.

Second problem was based on array i.e.

Given an array of large numbers and a number K, give an algorithm to search for a triplet whose sum is K. You can modify the array. You can print any triplet whose sum is K.

I could only suggest O(n^2 logn) approach. They asked to optimise it. But i couldn't. Then they asked me to solve smaller problem i.e to find duplet in an array.

I could also suggest O(nlogn) approach for smaller subproblem.

Then they asked me to tell them about my challenging project which i told them.

This was the whole interview.

Unfortunately, i couldn't make into further rounds.