Counting the number of occurrence of numbers in the array[reviewed]

Problem 

Given an array of ages(integers) sorted lowest to highest, output the number of occurrence for each age.

  For instance:

  [8,8,8,9,9,11,15,16,16,16]

  8: 3

  9: 2

  11: 1

  15: 1

  16: 3

  Running time should be $\le O(N)$

This question is one of Facebook interview question. To be honest upfront, I don't think the running time of ideal solution can be $\le$ O(N). It is still, by asymptotically speaking, O(N).

1. Brute-force approach

Simplest way to solve this problem will be to scan the numbers from left to right and count the occurrence of numbers. I would not bother writing the code for this approach since it is quite straightforward.

Running time of this algorithm is linear, O( N ), where N is the number of ages in the list.

2. Binary Search approach

If we are looking for the faster algorithm, we might be talking about $O(\log {n})$ or O(1).
Given the size of the input and output we need to produce, O(1) is out of question. Then, we need to find the algorithm can run in O(log N).

Given the fact, the input is sorted, we might be able to use binary search, by modifying the logic as below:

1) check if numbers between the start and end are the same. If so, write the occurrence, $end-start+1$ in the output array.
2) If start and end is not the same. Perform the followings:
2-1) slice the input in half
2-2) increase the occurrence count of the number in half by 1.
2-3) search the left-half, with start and half -1 range
2-3) search the right-half, with start and half -1 range
3) Continue back to step 1).

This algorithm isn't actually remove the searching space by half each time, thereby disqualifying to be O( log N) algorithm.

However, it can reduce the search if the given range is filled with the same numbers.

Overall running time of this algorithm, due to the worst case scenario, $$O(N)$$
Here is the complete code in C++



Practice statistics:

Could not come up with the algorithm because even the binary search one still run in O(N).
Later wrote the algorithm using binary search.


UPDATE(2019-09-26): solved the problem again. I knew I could use binary search but could not come up with the complete algorithm within 10 mins.

After reviewing the algorithm, it took 10 mins (with one typo in test code) to write the complete code.

After solving this problem, I now think that I could improve my original solution for "counting the occurrent of a specific number", problem. Previous answer for that question was to search both space and count one number at a time.

New way will be count entire range between start and end. This will avoid counting individual matching values.

Here is a solution in python.


Practice statistics

10:00: could not come up with a correct algorithm
10:00: to write the complete code (with one typo in the test code)