[Uber Onsite Interview] A version of frequency of a number in a sorted array problem in Uber on-site interview on Fri (20th Sep 2019)

In one of our pair programming sessions we had to find the frequency of a number in a sorted array. I was asked this exact problem in my Uber on-site on Fri. So the problem is: you are given a sorted array which can have repeats. You need to find how many times a given target number appears in the array in O(log(n)) time.

The approach I suggested is the same I built with my partner in pair programming. That is use a version of binary search. The idea is to use binary search first to find an instance of the target. Once we find the instance we look for the left boundary, i.e., to what length the number repeats on the left, and the right boundary of the target.

The way we developed this approach was to modify Binary Search in the following way. For left boundary search we start with the starting index (s) and the index at which we found our first instance of the target ©. Now we look to see if the middle index m = (s + c) / 2 is also the target. If it is then we recursively look for the boundary to the left of the middle m i.e., between s and m-1. If it’s not the target then we look for the left boundary to the right of the middle index i.e., between m and c-1.

Now of course before you start this search it’s prudent to check if the m-1 index is not the target in the former case if it’s not then m is the boundary and we don’t need the recursive call. And similarly in the latter case if m+1 is the target then m+1 is the left boundary and we don’t need to make the recursive call. The base case is when the end and the starting index in the function call cross each other.

Again there are some more details to be careful about but more or less this approach can find the frequency in O(log(n)) time by finding the right and the left boundaries :slight_smile:

3 Likes

Wow, glad you had solved that exact question before in a Pair Programming session :fire:!

Also, really enjoy seeing your thought process in the way you went out making the modifications to the binary search. Thanks for the great post @krisranden!