Google | Phone Screen | Reject | India

Problem: Given a sorted array you need to find the k closest element to m (given m and k).
My Approach: Get the index of the element which is closest to m through binary search, once we get the index use two pointer and check left and right respectively for k elements

TC: logn + k

He asked to code on the above, once done we dry run for certain test cases and was ok with the solution. During discussion I told him anyway we need to traverse k as we are looking for k elements.

Then he gave me a follow up.

Follow up: What if we need to find the kth closest element.
As not much time was left he asked me to just give the approach for the same. I told him we will just do binary search with some changes we will look in the range of (k) elements (end-start) and check for end and start index accordingly for k closest to m.

I was positive that I will be able to clear this round. But got a rejection mail. Just wanted you guys to help me out if there exists some other approach that I might be missing. Also lately I am getting rejected in a lot of opportunities (where I may be lacking behind).

1 thought on “Google | Phone Screen | Reject | India”

  1. anotherAcoount

    For follow up, assume some number – x, now find the sum of total # of numbers in m-x and m+x, if it is more than k, reduce x, else increase x, i.e. use binary search for the same. optimal x is the answer.

Comments are closed.