Recently finished a phone interview with a Bloomberg engineer. I applied for Entry Level Software Engineer position through referral. Got a reply to schedule for a technical phone interview.

The question asked was -
Given an input of sorted array (e.g: 1 1 2 3 3 3 4 5 6 6 6 6 6 7 8 9 9 9), find how many times a number 'k' (e.g: 6) has occurred in the array.
Here the o/p will be 5 since the number 6 has occurred 5 times in the array.

I told him my approach would be to store each element in a HashMap where the number is the key and number of occurrences is it's value. Then lookup that number k in the HashMap and return it's value.
Worst case time complexity - O(n) as we add all the elements in the HashMap.

But he asked if there is a faster solution. Since, the array is already sorted, my mind went for Binary Search which would find the solution in O(logn) to find k in the list. Once k if found to be the middle element, to find the number of occurrences of k, I will have the expand from that point (mid point of the list) on left and right sides using pointers to find the first occurence of k and the last occurence of k and keep a counter variable every time I move the pointers either to left or right. And in the end, return that counter which would be the frequency.

However, the interviewer said, if the input is - 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6, the time complexity will still be O(n) since you find the middle element to be k in the first search itself and are expanding from the mid point to index 0 and arrayLength - 1.

I was unable to find a solution faster than O(n) for this example - 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6.

Am I missing something here? Because I think if every element is k, then you will HAVE TO visit each number and that would be O(n). Please let me know if there is a better solution.

Thank you !