Technical Interview 1

Problem 1

You are given two integers n, k, and an array a of size n. Find out the frequency of k in the array a.

Solution

My first solution was to hash the frequency of the entire array in array h and then print h[k]. The time and space complexity are both O(n) in this case. The interviewer asked me to improve the space complexity.

In my next solution, I just took an integer variable count and incremented it every time k occurred while traversing the array a. This space complexity reduced to O(1) and time complexity still O(n).

He told me that if the array is sorted and now I have to reduce the time complexity as well. I could simply use lower_bound() and upper_bound() functions in C++ to find the first and last occurrence of k in array a. Now the space complexity is O(1) and time complexity is O(log(n)). He told me to write the code.

Instead of using upper_bound() and lower_bound() directly I thought it would be better to implement them. So, I wrote two binary search codes, one for lower_bound() and other for upper_bound(). He was satisfied and moved on to next question.

Problem 2

Create a binary search tree from a sorted linked.

Solution

My first solution was an obvious skewed tree. He was impressed and told that it is indeed very easy and simple solution but now he wants a height balanced tree. This the solution. He told me to write the entire code which I did somewhat correctly with his help.

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.