Find occurrences of a number in sorted array (allow duplicates).

Question

PixelPerfect3 · Accepted Answer

Use binary search to find the number (O(logN)). Once that is done you can search around that index. Though that could become O(N).

Better answer: run binary search again twice once you have found the number the first time. For the upper half and the lower half - so total run time is O(logN)

Anonymous · Answer

With the last algorithm, how does it ever return anything but 0?  If main calls with start := 0 and end :=  length - 1? The only case where you get past the base case is if the array is length 1... since (start < end) = (0 <  length -1) from the input... and returns 0...

Anonymous · Answer

Also, I think there is a good shot at a stack overflow with this method.  I would add an extra variable and solve the problem tail recursively.

Anonymous · Answer

Try this. 

int findLeftEdge( int A[], int num, int val ){
	int mid = num/2;
	
	if( num == 1 ){
		return 0;
	}else{
		if( A[mid] == val && A[mid-1] != val ){
			return mid;
		}else if( A[mid] == val || A[mid] > val ){
			return findLeftEdge( A, mid, val );
		}else if( A[mid]  val ){
			return findRightEdge( A, mid, val );
		}
	}
}

int countOccurrenceSortedArray( int A[], int num, int val ){
	int left = findLeftEdge( A, num, val );
	int right = findRightEdge( A, num, val );
	
	return right-left+1;
	
	
}

int main() {
	// your code goes here
	int A[] = { 1, 5, 10, 10, 12, 19, 19, 19, 20, 20};
	int ans = countOccurrenceSortedArray( A, sizeof(A)/sizeof(int), 20 );
	cout << ans << endl;
	return 0;
}

Anonymous · Answer

O(logN) required

someguy · Answer

JAVA Code : // For Sorted and UnSorted Array in O(N) time Complexity.

import java.util.HashMap;

public class FindOccurrences {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int unsortedArray[] = {4,6,7,8,4,5,6,8,3,2,4,5,7,8,9,3,4,6,7,8};
		System.out.println(findOccurrencesUnsorted(unsortedArray,8));
		
		int sortedArray[] = {1,2,2,3,3,3,4,4,4,4,5,5,5,5,5};
		System.out.println(findOccurrencesSorted(sortedArray,5));
	}

	
	private static int findOccurrencesUnsorted(int[] array, int number) 
	{
		HashMap map = new HashMap();
		for(int i=0;i

Interview Candidate · Answer

O(logN) is possible for sorted arrays, the key here is to firstly check beginning and end to determine next binary-search steps, I attached my code below, and I think this is O(logN) in worst case.

//inputs are the sorted array, k is the number looking for
//start and end are two index values, main method calls with (start=0) and (end=length-1)
int GetOccurance(int[] inputs, int k, int start, int end)
{
	if(startk) return 0;
	if(inputs[start]==k&&inputs[end]==k) return end-start+1;
	int mid = (start+end)/2;
	if(input[mid]k)
		return GetOccurance(inputs, k, start, mid-1);
	else 
		return GetOccurance(inputs, k, start, mid-1)+1+GetOccurance(inputs, k, mid+1, end);
}

someguy · Answer

I think it is not possible in O(logN) because anyway traversing the complete array is needed to access all the numbers. Worst Case scenario would be the last number repeating itself 5 times. For example : {1,2,2,3,3,3,4,4,4,4,5,5,5,5,5} and if you are asked to find out the occurrences of number '5' then you have to traverse the complete array once which means the complexity should be O(N).

Google

Google Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches