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)

Comments

Post a Comment

Popular posts from this blog

Planting flowers with no adjacent flower plots

Image
Problem Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die. Given a flowerbed (represented as an array containing booleans), return if a given number of new flowers can be planted in it without violating the no-adjacent-flowers rule  Sample inputs  Input: 1,0,0,0,0,0,1,0,0  3 => true  4 => false  Input: 1,0,0,1,0,0,1,0,0  1 => true  2 => false  input: 0  1 => true  2 => false  public boolean canPlaceFlowers(List flowerbed, int numberToPlace) {  // Implementation here  }
Read more
  Given an array of  intervals  where  intervals[i] = [start i , end i ] , merge all overlapping intervals, and return  an array of the non-overlapping intervals that cover all the intervals in the input . Example 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. Example 2: Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.   Constraints: 1 <= intervals.length <= 10 4 intervals[i].length == 2 0 <= start i <= end i <= 10 4
Read more

Find the maximum number of bomb that can be detonated

  Problem You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb. The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range. You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range.  These bombs will further detonate the bombs that lie in their ranges. Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb. Input: bombs = [[2,1,3],[6,1,4]] Output: 2 Explanation: The above figure shows the positions and ranges of the 2 bombs. If we detonate the left bomb, the right bomb will not be affected. But if we detonate the right bomb, both bombs will be detonated. So...
Read more