Google Interview Question for Software Engineer / Developers


Country: Israel
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 7 vote

A solution with O(n) time complexity and O(1) space complexity.
Logic:1) maintain 4 variables called count and element element,max count,max element.Initialise count to 1 and maximum element to 1st element of array.
2) while traversing if the element is same as maximum count then increment count by one.
3)Else decrement count.If count reaches zero then assign maximum element to the element at which count became zero and reinitialise the variables

#include<stdio.h>
#include<stdlib.h>
int findMaximumRepeatingElement(int *a,int n)
{
  int count=1,maxcount=1,maxelement=a[0];
  int element=a[0];
  int i=1;
 while(i<n)
 {
   if(a[i]==element)
   {
    count++;
   if(count>maxcount)
  {
      maxcount=count;
      maxelement=a[i];


   }


   }
   else
   {
       
      element=a[i];
      count=1;
     
   }
 i++;
 

 }
    return maxelement;
}

int main()
{

  int a[]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,3,3,3,3,3,4,4,4,4,4,4,4,5};
 printf("%d",findMaximumRepeatingElement(a,sizeof(a)/sizeof(int)));

}

- arunkumar267 December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 5 votes

This method is valid only when the max element occurs ore than n/2 times..

- srikantaggarwal December 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@srikantaggarwwal No it will work for all cases.You can check

- arunkumar267 December 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Try for 1,1,2,3,,4,5

- srikantaggarwal December 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@srikantaggarwal- it returns 1

- arunkumar267 December 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is actually the majority voting algorithm. it usually works only if an element appears more than n/2 times. In this case it works for the other ones as well because the array is sorted. In O(n) it is a little bit or over-complication. You could just go through the array and compare it to the previous element.

- Anonymous January 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 votes

Its not majority voting algorithm. In Moore's algo you decrease the counter if the currently checked element is different then the candidate till the counter is equal 0.
So the part:

else
   {
       
      element=a[i];
      count=1;
     
   }

should be change as follows for Moore's algo:

else
   {
       
      element=a[i];
      count--;
     
   }

In arunkumar267's solution he simply starts counting from the beginning when he finds new value and its perfectly fine.

- thelineofcode January 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This algorithm can be optimized (which was interviewer's second part of the question) by performing the following check as the first step in the while loop:

if(maxCount >= (numArr.length - i))
return maxCount;

- Nishant Kelkar January 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For 1 1 2 3 4 5
After each element scan :
a. scan 1. count = 2, maximum element = 1
b. scan 1. count = 3 maximum element = 1
c. scan 2. count = 1, maximum element = 1
d. scan 3. count = 0, maximum element = 3
e. scan 5, count = 0, maximum element = 4..

- srikantaggarwal January 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem statement says the array is already sorted, so you don't need to bother with all this decrementing counter stuff. Just count instances of last letter, if the counter exceeds max, update max and max letter. O(n)

- foo May 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think its not correct
test case
1 2 2 1 1
o/p is 2
it should be 1

- jindal.manishkumar1 June 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

use map,key is array item and frequency is value.
and sort it according to value

- jindal.manishkumar1 June 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@jindal.manishkumar1
The question states the array is sorted. Now please check your test case:
1 2 2 1 1

- Anonymous February 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

Below is the java code solution
The first method time complexity is: Θ(n)
The second method average time complexity is: Θ(logn)
:

/**
 * 
 * @author Alex (xiaofan)
 * 
 */
public class RepetitionsNumber {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 1, 2, 2, 3, 3, 3, 4 };

		RepetitionsNumber repetitionsNumber =new RepetitionsNumber();

		int maxRepNumber=repetitionsNumber
                              .getBiggestRepetitionsNumber(a);
		System.out.println(maxRepNumber);

		maxRepNumber = repetitionsNumber
				.getBiggestRepetitionsNumberMoreEfficient(a);
		System.out.println(maxRepNumber);

	}

	/**
	 * Time Complexity Θ(n)
	 * 
	 * @param a
	 * @return
	 */
	public int getBiggestRepetitionsNumber(int[] a) {

		int maxRepNumber = 1;
		int currentRepNumber = 1;

		for (int i = a.length - 1; i > 0; i--) {
			int j = i - 1;
			if (a[i] == a[j]) {
				currentRepNumber++;
			} else {
				maxRepNumber = maxRepNumber > currentRepNumber 
					? maxRepNumber: currentRepNumber;
				
				currentRepNumber = 1;
			}
		}

		return maxRepNumber;
	}

	/**
	 * Improve one with devide and conquer .
	 * 
	 * Average Time Complexity Θ(logn) Worst Case Θ(n)
	 * 
	 * @param a
	 * @return
	 */
	public int getBiggestRepetitionsNumberMoreEfficient(int[] a) {
		return binaryRepNumber(0, a.length - 1, a);
	}

	private int binaryRepNumber(int startIndex, int endIndex,int[] a) {

		if (startIndex == endIndex) {
			return 1;
		}

		int midIndex = (startIndex + endIndex) / 2;
		int midRepNumber = 1;
		int leftMidInex = startIndex;
		int rightMidIndex = endIndex;

		for (int i = midIndex; i > startIndex; i--) {
			int j = i - 1;
			if (a[i] == a[j]) {
				midRepNumber++;
			} else {
				leftMidInex = j;
				break;
			}
		}

		for (int i = midIndex; i < endIndex; i++) {
			int j = i + 1;
			if (a[i] == a[j]) {
				midRepNumber++;
			} else {
				rightMidIndex = j;
				break;
			}
		}

		int leftRepNumber=binaryRepNumber(startIndex,leftMidInex, a);
		int rightRepNumber=binaryRepNumber(rightMidIndex,endIndex, a);

		int maxRepunumber = leftRepNumber > rightRepNumber 
				? leftRepNumber: rightRepNumber;
		
		maxRepunumber = maxRepunumber > midRepNumber 
				? maxRepunumber: midRepNumber;

		return maxRepunumber;
	}

}

- xiaofan December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

binaryRepNumber - That's more or less what the interviewer was looking for. He noted that you could further refine the solution by using binary search instead of the for loops.
He also noted that the complexity is not O(log n), this is what I thought as well. The complexity is apparently O (n / k ), where k is the length of the longest sequence.

- GeorgyBoy December 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(log n) is much faster than O(n/k) if the array length is bigger and k is small.
For example: n=1000, k=10 , O(logn)=10 , but O(n/k)=100.
For the length of n=1000, only the K bigger than 100, O(n/k) better than O(logn).

So no one can make sure O(n/k) is faster than O(log n) .

- xiaofan December 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

can you guys please help me in understanding how this solution is O(log n)? As far as I see it is still O(n) because eventhough you are splitting the array in the mid, you are still making the comparisons in both the sub arrays.
in binary search, once the array is split, we know if the element lies in one of the sub arrays easily (based on if the element is bigger than or smaller than the mid element)

- sukheshmg December 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What average Theta(log n)? Nonsense.

- Anonymous December 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think current implementation of binaryRepNumber has O(n) time complexity. In order to reduce it to O(n / k) it is needed to maintain the biggest length of the longest repetition. If length is greater or equal to the length of current interval then do nothing in the current recursion call.
This approach allows to reduce comparisons on leaves of recursion tree.

- Anonymous January 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could someone please explain why the worst case is O(n/k)?

- Anonymous January 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think it would be O(n/k) only if the number with occurence k is in the middle. Otherwise, in the worst case you could have all elements distinct and have the largest one with occurence k and it would still be O(n). Can someone give an idea why it would be O(n/k)?

- Anonymous January 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your first method will not work for this sequence: (imho)

0 1 3 4 1 1 3 4 2

It will return a 2. Whereas the ans is 3 (there are 3 1s in the array)

- boku January 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My solution is O(n^2). which is compare element with every other element.
But that doesn't use the fact that array is sorted

- boku January 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry my bad didnt see that the arr is sorted. 1st soln works

- boku January 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think it's O(n) for the second method. you have to go to the left and right subarray anyways.

- meow January 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

The 'divide and conquer' solution is absolutely NOT O(logn). It still requires checking every element in the array.

To improve on the linear run time, I believe you need to do this optimization: after checking the number of repititions for the middle number, you check if you can eliminate the left or right side (by virtue of their total lengths being less than the number of repitions in the middle). In the case where you're can't eliminate left or right, do either left or right first, whichever is larger (you can choose either if they're the same length). Then you check if you can eliminate the other side from contention before doing the other side.

A few examples:
1 1 2 2 2 2 3 3 4 => here you would counts the 2's. Then instead of recursively checking the number of repetitions one the left hand and right hand side, you can determine that neither can be greater than 4 (because length of left hand side = 2 and length or right hand side = 2).

11111234567 => here you count the one 2 in the middle. Then, arbitrarily, you choose to do the left hand side next. You see it has 5 reps. You can't beat that on the right hand side (it has 5 numbers total), so assuming you can return either number if multiple numbers have the same max #of repitions, you are done.

- Rob January 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

One more improvement to binary search method above can be to check on the top of the method

if (arr[startIndex] == arr[endIndex]) {
	return endIndex - startIndex + 1;
}

This is especially helpful for arrays like 13,13,13,13,13,52,53,53,53,53,53

Nice binary search approach by the way.

- Asif Garhi August 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

not only the second algorithm is not log n, it may actually end up being O(n log n) (for example for arrays with only 1 number). Nice try though, but overengineered :)

- mbriskar May 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

This solution is based on the idea of skipping forward by a length equal to the most number of repeats seen so far.

public class MostRepeatingInSortedArray {
	public int mostRepeating(int a[]) {

		// the index of current element
		int current = 0;

		int most_repeated = a[0];
		int max_repeats = 1;

		// just to see how many times the basic operation is done
		int complexity = 0;

		/* always increment by the max repeats seen so far */
		while (current + max_repeats < a.length) {
			/* same element again */
			if (a[current + max_repeats] == a[current]) {
				complexity++;
				current += max_repeats;
				max_repeats += max_repeats;
				most_repeated = a[current];
				while (a[current] == a[current + 1]) {
					complexity++;
					current += 1;
					max_repeats++;
				}
				complexity++;
				current++;
			} else {
				/* different element dound */
				complexity++;

				/* move the current index */
				current += max_repeats;

				/* backtrack */
				int rep = 1;
				while (a[current] == a[current - rep]) {
					complexity++;
					rep++;
				}
				complexity++;

				/* check elements ahead of you */
				int rep2 = 1;
				while (a[current] == a[current + rep2]) {
					complexity++;
					rep2++;
					if (current + rep2 == a.length) {
						break;
					}
				}
				complexity++;
				int total_rep = rep + rep2 - 1;
				if (total_rep > max_repeats) {
					max_repeats = total_rep;
					most_repeated = a[current];
				}
				current += rep2;
			}
		}

		System.out.println("complexity: " + complexity);
		System.out.println("elements: " + a.length);

		return most_repeated;

	}

	public static void main(String[] args) {
		MostRepeatingInSortedArray test = new MostRepeatingInSortedArray();
		int[] input = new int[] { 1, 1, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5,
				5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 9, 9, 9, 9, 10, 11, 12, 12,
				12, 13, 13, 13, 13, 13, 13, 13, 22, 23, 24, 32, 33, 35, 36, 55,
				55, 55, 55, 55, 56, 56, 57, 58, 59, 59, 59, 60, 65, 65, 65, 65,
				65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66,
				66, 67, 67, 68, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
				70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
				70, 70, 71, 72, 72, 72, 72, 72, 72, 72, 72, 72, 80, 80, 85, 86 };
		int out = test.mostRepeating(input);
		System.out.println("most repeated: " + out);
	}
}

- sukheshmg January 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

int findRepetition(int[] array){
 int ans = -1, count = 0, prevMax=0; prevNumber = Integer.MAX;
  for(int i= 0; i< array.length; i++){
	if(prevNumber == array[i]){
		count++;
	    }
	else{
		if(count >= prevMax){
			ans = prevNumber;
			prevMax = count;
			}
	prevNumber = array[i];
	count = 1;
	}
  }
	return ans;
}

- Roxanne December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Biggest {

public static void main(String args[])
{
int [] a ={1,2,2,3,3,3,3,5,6,6,6,6,6,6,6,7,8,8,8};

int prevnum =a[0];
int count =0;
int maxrepvalue =a[0];
int maxrepcount =0;
for (int i =0;i<a.length-2;i++)
{

prevnum = a[i];
if(prevnum ==a[i+1])
count ++;
else
{
if(count >maxrepcount)
{
maxrepvalue=prevnum;
maxrepcount =count;
}

count=0;
}


}
System.out.println(maxrepvalue +">>" +(maxrepcount+1));


}

}

- Anonymous December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just start to count when coming across a different number, the code is easy:

int findRepeatMost(int arr[], int n, int& mostItem)
{
    int mostTimes = 0, i, j;

    for(i = 0; i < n; i = j){
        for(j = i+1; j < n; ++j){
            if(arr[j] != arr[i]) break;
        }
        if(mostTimes < j-i){
            mostItem = arr[i];
            mostTimes = j-i;
        }
    }

    return mostTimes;
}

- uuuouou December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Refer to skip list, always try to skip K numbers to avoid unnecessary scan, if encounter a different number, then backward........

- Dong December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

great idea!.. i am thinking of few modifications to your approach

1. have a max_repeats initialize to 1
2. keep going till you see different element a2 (incrementing max_repeats)
2. when you see an element different than the current one (a2), skip by max_repeats
3. a. If the number at new location is same as a2, a2 is our new candidate, keep going sequentially
3. b. If the number at new location is different than a2, (is a3) then using 2 pointers scan backwards and forward for a3s
3. b.i if this gets more a3s then make a3 new candidate

4. repeat with new max_repeats as your skip factor

- Vivek December 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void main(){

  int i,j;
  int arr[] = {1,2,2,2,4,4,4,48,48,48,48,48,48,48,48};
  int length = 14;
  int index,count=1,findex,fcount=-1;
  for(i=0;i<length-1;){
     count = 1;
     while(arr[i]==arr[i+1]){
	count++;
	index=i;
	i++;
     }
     if(arr[i]!=arr[i+1])
	i++;

     if(fcount<count){
	fcount = count;
	findex = index;
     }
  }
  printf("\nLargest Frequency number :: %d",arr[findex]);
  printf("\nFrequency :: %d",fcount);
 
}

- Coder December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

int main()
{
int a[] = {1,1,1,1,1,1,1, 2, 2, 2, 3 ,4, 5, 5 , 5 ,5 ,5 };
int n = sizeof(a)/sizeof(a[0]);
int num, max_repeat = 1;
int prev = a[0];
int rep = 1;
int i;
num = a[0];

for (i=0; i < n; i++)
{
if (a[i] == prev)
{
rep++;
}
else
{
if (rep > max_repeat)
{
num = prev;
max_repeat = rep;
}
rep = 1;
}
prev = a[i];
}

if (rep > max_repeat)
{
num = prev;
max_repeat = rep;
}

printf ("Number with max repeatations = %d \n", num );
}

- Sandeep December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>

using namespace std;

int evalMaxRepeatElem(int *array, int num_Elem){
	int maxcount = 1;
	int i = 0, count = 0;
	int repeatElem = array[0];
	while( i<num_Elem ){
		while(array[i] == array[++i])
			count++;
		if(count > maxcount)
			repeatElem = array[i-1];
		}
	return repeatElem;
}

int main(){
	int array[] = {1,1,1,1,2,3,3,3,5,5,5,5,5,5,7,7,7,7,7,7,7,7,7,7,7,8,9,9};
	int maxRepeatElement;
	
	maxRepeatElement = evalMaxRepeatElem(array, sizeof(array)/sizeof(array[0]));
	cout<<maxRepeatElement<<"\n";
}

- Sunny December 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a short Implementation in Python

count = 0

def MaximumRepeatingInteger(arrayofnumber):
    global count
    dict_of_counts = {}
    for integer in arrayofnumber:
        if dict_of_counts.has_key(str(integer)):
            count +=1
            dict_of_counts[str(integer)]=count
        else:
            count = 1
            dict_of_counts[str(integer)]=count
        
    return max(dict_of_counts.values())

number = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5]
print MaximumRepeatingInteger(number)  : 14

number=[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5]
print MaximumRepeatingInteger(number)  : 21

- gravityrahul January 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Go

package main

import "fmt"

func main() {
  b:= []int{1,1,2,2,2,3,3,4,5,7,15,15,15,15,15,17}
  max_count := 1
  count := 1
  max_value := b[0]
  for i:=1; i < len(b) ; i++ {
    // We increment the count if the same value
    if b[i-1] == b[i] {
      count = count + 1
    }
    if b[i] != b[i-1] {
      count = 1
    }
    if count > max_count {
      max_count = count
      max_value = b[i]
    }
  }
  fmt.Println("Total value:", max_value, "appears",max_count,"times")
}

- Elie January 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For sorted:

int max_value = A[0], max_count = 1;
int value = A[0], count = 1;
for(int i=1; i<N; ++i)
    if(A[i] == A[i-1]) 
    {
        ++count ;
        if(max_count <count )
        {
            max_value  = value ; 
            max_count  = count ;
        }
    }
    else
    {
        value  = A[i];
        count = 1;
    }

Time: O(N)
Space: O(1)

For unsorted:

Data structure: treap (tree+heap)

http://en.wikipedia.org/wiki/Treap   
http://e-maxx.ru/algo/treap

sorted tree by value + max-head by count
root will be the answer

Time: O(N Log(N))
Space: O(N)

- Darida January 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) complexity with no additional space

/*
  Given a sorted array of integers, write a function that will return the number with the biggest number of repetitions.

  (Asked to refine the solution to be more efficient)
*/

#include <iostream>
#include <vector>

static int max_rep(const std::vector<int>& vec) {
	int big_cnt = 0;
	int saved_int;
	int cnt;

	saved_int = vec[0];
	cnt = 1;
	big_cnt = 1;
	
	for(int i = 1; i < vec.size(); i++) {
		if(saved_int == vec[i]) {
			++cnt;
			continue;
		}

		// Different
		if(cnt > big_cnt) {
			big_cnt = cnt;
		}

		saved_int = vec[i];
		cnt = 1;
	}

	if(cnt > big_cnt)
		big_cnt = cnt;

	return big_cnt;
}

int main() {
	std::vector<int> vec{1, 1, 1, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5};
	std::cout << max_rep(vec) << std::endl;
	return 0;
}

- Felipe Cerqueira January 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void LargeRepetations(int[] arr)
        {
            int len = arr.Length;
            int mostFreq = arr[0];
            int largeFre=1;
            int currentFre = 1;
            
            for (int i = 1; i < len; i++)
            {
                if (arr[i-1]!=arr[i])
                {
                    currentFre = 1;
                }
                else
                {
                    currentFre++;
                }
                if (largeFre < currentFre)
                {
                    largeFre = currentFre;
                    mostFreq = arr[i];
                }
                
            }

- Alemayehu Woldegeorgis January 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
void main(){
int a[] = {2,7,9,7,5,7,0,9,4,3,5,7};
int i,j,max=0,number,k;
for(i=0;i<12;i++){
number=1;
for(j=i+1;j<12;j++){
if(a[j]==a[i])
number++;
}
if(number>max){
k=a[i];
max=number;
}
}
printf("MAximum occurence of a number is: %d and the number is %d", max,k);
getch();
}

- RK January 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		int[] intArray= { 1, 1, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5,
				5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 9, 9, 9, 9, 10, 11, 12, 12,
				12, 13, 13, 13, 13, 13, 13, 13, 22, 23, 24, 32, 33, 35, 36, 55,
				55, 55, 55, 55, 56, 56, 57, 58, 59, 59, 59, 60, 65, 65, 65, 65,
				65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66,
				66, 67, 67, 68, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
				70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
				70, 70, 71, 72, 72, 72, 72, 72, 72, 72, 72, 72, 80, 80, 85, 86 };
		int count=0;
		int pricount=0;
		int currentNo=intArray[0];
		int maxInt=0;
		int i=0;
		for(int no:intArray){
			if(no==currentNo){
				count++;	
			}else{
				if((count>pricount)){
				   pricount=count;
				   maxInt=currentNo;
				}			
				count=1;
				currentNo=no;
			}
				i++;
			}
		if((i==intArray.length)){
			if(count>pricount){
				 pricount=count;
				 maxInt=currentNo;
			}
			    	 System.out.println("Maxi int :"+maxInt +" and count : " +pricount);
			     
			}
		// TODO Auto-generated method stub

	}

- Ram January 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What should be the complexity for the following, as this seems like the easiest approach to me:
HashMap<Integer, Integer> test = new HashMap<>();
Integer[] array = {1,2,3,1,1,3,2,2,2,2};
int maxKey =0;
int maxValue=0;
int newCounter =0;
for (Integer check: array)
{
if (!test.containsKey(check))
{
test.put(check, 1);
System.out.println("FIRST key:"+check+" counter:"+1);
}
else
{
newCounter=test.get(check)+1;
test.put(check, newCounter);
if (newCounter>maxValue)
{
maxValue=newCounter;
maxKey=check;
}
System.out.println("key:"+check+" counter:"+test.get(check));
}
}

- standon January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int maxCount(int a[]){
	int maxCount = 0;
	int count = 0;
	for(int i = 1; i < sizeof(a); i++){
		if(a[i] == a[i-1]){
			count ++;
		}
		else{
			if(maxCount < count)
				maxCount = count;
			count = 0;
		}
	}
	return maxCount+1;

}

- qwerty January 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int maxRepetitionCount =0;
		int maxRepetitiveElement =0;
		int tmp =0;
		for(int i =0; i< a.length-1;i++) {
			if(a[i+1] == a[i]) {
				tmp++;
			}else if( tmp > 0) {
				//Repetition sequence ends
				if(tmp > maxRepetitionCount) {
					maxRepetitionCount = tmp;
					maxRepetitiveElement = a[i];
					
					if(maxRepetitiveElement > (a.length-1 -i)) {
						//Not enough elements left to overcome this value
						tmp =0;
						break;
					}
				}
				tmp =0;
			}
		}

		//if max repetiting element is the last element
		if(tmp > maxRepetitionCount) {
			maxRepetitionCount = tmp;
			maxRepetitiveElement = a[a.length -1];
		}
		
		System.out.println(maxRepetitiveElement+"  "+(++maxRepetitionCount));

- Serdar January 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python one-liner:

max([list(j) for i, j in groupby(a)], key=len)[0]

- nilkn January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This one has also o(n) as worst case (when the largest run is very small, e.g 2). however, it gets much better as runs grow. For example, a run of size 200 in an array of size 1000 would require only ~50 comparisons. A run of size 60 in the same array requires ~150.

static int
bsearch_run_boundary (int *a, int num, int start, int end, int is_begin, int *cmp)
{
    int org_end = end, org_start = start;
    int mid;
    while (start < end) {
        (*cmp)++;   // count the num of comparisons
        mid = start + ((end - start) / 2);
        if (a[mid] < num) {
            start = mid+1;
        } else if (a[mid] > num) {
            end = mid-1;
        } else if (is_begin) {
            if (mid == org_start || a[mid-1] < num) return mid;
            end = mid-1;
        } else {
            if (mid == org_end || a[mid+1] > num) return mid;
            start = mid+1;
        }
    }
    return a[start] == num ? start : -1;
}

static void
largest_run (int *a, size_t n, int *maxrun, int *cmp)
{
    int mid = n / 2;
    int midval = a[mid];
    int begin, end, run;

    // find the beginning of this run
    begin = bsearch_run_boundary(a, midval, 0, mid, 1, cmp);
    // find the end of this run
    end   = bsearch_run_boundary(a, midval, mid, n-1, 0, cmp);
    assert(begin >= 0 && end >= 0);
    run = end - begin + 1;
    printf("-> run (%d) = %d\n", midval, run);
    // is it the largest run so far?
    if (run > *maxrun) *maxrun = run;
    // check the lower range if it has potential for a larger run
    if (begin > *maxrun) {
        largest_run(a, begin-1, maxrun, cmp);
    }
    // check the higher range if it has potential for a larger run
    if (n - end - 1 > *maxrun) {
        largest_run(a + end + 1, n - end - 1, maxrun, cmp);
    }
}

- shin January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {

		int[] testArr = new int[] { 1,1, 9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9

		};

		int maxFreq = 0;
		int currentFreq = 0;
		int max = testArr[0];

		for (int i = 1; i <= testArr.length - 1; i++) {

			currentFreq++;
			
			int prev = testArr[i-1];
			int next  = testArr[i];

			if (prev != next || (i == testArr.length - 1)) {

				if (maxFreq <= currentFreq) {
					max = testArr[i-1];
					maxFreq = currentFreq;
				}

				currentFreq = 0;

			}
		}

		System.out.println("Max freq " + maxFreq + " Number " + max);

	}

- itnilesh January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

complexity is of O(n)

- itnilesh January 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

i don't think dividing with binary can help as you still need to scan whole array. Here is my take on this. it will skip k where k is max known so far. So its best will be o(n/k) and worst will be O(n)

int findMaxRepead(int[] num)
        {
            int maxCount = 0;
            if (num.GetLength(0) > 0)
            {
                int i = 1;
                int count = 1;
                int currNum = num[0];

                while (i < num.GetLength(0))
                {
                    if (num[i] == currNum)
                    {
                        if (count > maxCount)
                        {
                            maxCount = count;
                        }
                        i = i + maxCount;
                        count += maxCount;

                    }
                    else
                    {
                        count = 1;
                        currNum = num[i];
                        int j = i - 1;
                        while (j >= 0 && currNum == num[j])
                        {
                            j--;
                            count++;
                        }

                    }

                }
            }
            return maxCount;

        }

- Anonymous January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

without using binary search, you're not taking any advantage of the fact that the array is _sorted_ .

- shin January 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

not accurate, the reason i can skip k is due to the fact that array is sorted otherwise i had to scan all. Problem itself is not divide concur kind of thing its more of a scanner. In scanner kind of problems only optimization you can do is how many do you can skip. Do you have case that shows binary algo will out perform what i posted above. :)

- Anonymous January 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for skipping k elements it's enough to assume that the numbers are grouped in "runs", but you don't need the groups themselves to be in ascending order. For example, the skipping algo works for a case like [ 3, 3, 1, 1, 1, 2, 2]. Think about a case where you have a run which is bigger than n/2 . Therefore, this run has to cross the array's middle point. The binary search starts from the middle, so it finds it right away, while the skipping algo may need n/2 steps. if the run is n/4 long, then binary search finds it at the 2nd round, and so on. The advantage of "random sampling" in oppose to linear scanning is that large runs have a higher probability to be sampled than small runs. Now there are two ways of doing the binary search. The one listed above is similar to DFS (depth first). There's also a BFS approach, where all the level-2 ranges are handled before starting to handle level-3 ranges, etc. The BFS might be better, because if the largest run is located at the array end, then it would be found soon enough to suppress the exploring of smaller ranges.

- shin January 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int most_freq(const int *i, const int size)
{
	if(0 == size) return -1;
	int count = 1;
	int m;
	int prev = i[0];
	int highest_count = count;
	int retVal = i[0];
	for(m=1; m<size; ++m)
	{
		if(i[m] == prev)
		{
			count++;
			if(count > highest_count)
			{
				highest_count = count;
				retVal = i[m];
			}
		}
		else
		{
			prev = i[m];
			count = 1;
			if(i[m + highest_count -1 ] == prev)
			{
				count = highest_count;
				m+=highest_count-1;
			}
		}
	}
	return retVal;
}

- Sagar January 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a[20], n, count =0, maxrepeat=0,maxrepeatvalue;

printf("entr the size of array ");
scanf("%d", &n);
printf("enter the element");

for(i=0;i<n;i++)
{
scanf("%d",&a[i]);

}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{

if(a[i]==a[j]){

count++;}
else
{
if (count > maxrepeat)
{
maxrepeatvalue=a[i];
maxrepeat=count;
count=0;
}
}

}
}
printf("total count =%d \n maximum repeated number %d\n", maxrepeat+1, maxrepeatvalue);
getch();
}

- sony kumari January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a[20], n, count =0, maxrepeat=0,maxrepeatvalue;

printf("entr the size of array ");
scanf("%d", &n);
printf("enter the element");

for(i=0;i<n;i++)
{
scanf("%d",&a[i]);

}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{

if(a[i]==a[j]){

count++;}
else
{
if (count > maxrepeat)
{
maxrepeatvalue=a[i];
maxrepeat=count;
count=0;
}
}

}
}
printf("total count =%d \n maximum repeated number %d\n", maxrepeat+1, maxrepeatvalue);
getch();
}

- sony kumari January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a[20], n, count =0, maxrepeat=0,maxrepeatvalue;

printf("entr the size of array ");
scanf("%d", &n);
printf("enter the element");

for(i=0;i<n;i++)
{
scanf("%d",&a[i]);

}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{

if(a[i]==a[j]){

count++;}
else
{
if (count > maxrepeat)
{
maxrepeatvalue=a[i];
maxrepeat=count;
count=0;
}
}

}
}
printf("total count =%d \n maximum repeated number %d\n", maxrepeat+1, maxrepeatvalue);
getch();
}

- sony kumari January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a[20], n, count =0, maxrepeat=0,maxrepeatvalue;

printf("entr the size of array ");
scanf("%d", &n);
printf("enter the element");

for(i=0;i<n;i++)
{
scanf("%d",&a[i]);

}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{

if(a[i]==a[j]){

count++;}
else
{
if (count > maxrepeat)
{
maxrepeatvalue=a[i];
maxrepeat=count;
count=0;
}
}

}
}
printf("total count =%d \n maximum repeated number %d\n", maxrepeat+1, maxrepeatvalue);
getch();
}

- sony kumari January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a[20], n, count =0, maxrepeat=0,maxrepeatvalue;

printf("entr the size of array ");
scanf("%d", &n);
printf("enter the element");

for(i=0;i<n;i++)
{
scanf("%d",&a[i]);

}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{

if(a[i]==a[j]){

count++;}
else
{
if (count > maxrepeat)
{
maxrepeatvalue=a[i];
maxrepeat=count;
count=0;
}
}

}
}
printf("total count =%d \n maximum repeated number %d\n", maxrepeat+1, maxrepeatvalue);
getch();
}

- sony kumari January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>

int count(int[],int);
int max = 1;
int tempmax = 1;
int count(int a[],int size){

for(int i=0;i<size;i++)
{

if(a[i]==a[i+1])
max++;
else
{
printf("\n [ %d ]-> %d",a[i],max);
if(max>tempmax)
{
tempmax = max;
max = 0;
}


}
}
if(max>tempmax)
return max;
else
tempmax;

}



int main()
{
int arr[] = {1,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5};
int maxcount = count(arr,(sizeof(arr)/sizeof(int)));
printf("\n highest -> %d",maxcount);
}

- Monis Majeed February 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Cant we have Map with key as the number and value as the number of times it is in the list?

- Anonymous February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.tutorial.sorting;

public class GetMaxNumberRepeatedTest {
	
	public static void main(String[] args) {
		GetMaxNumberRepeatedTest gmrt = new GetMaxNumberRepeatedTest();
		int[] testList1 = new int[]{1};
		int[] testList2 = new int[]{1,2,3,4};
		int[] testList3 = new int[]{1,2,2,3,4,4,5,5,5,6,6,6,7};
		int[] testList4 = new int[]{1,2,2,3,3,3};
		
		System.out.println("==========================================");
		System.out.println("\t Get Number Repeated Most Times \t");
		System.out.println("==========================================");
		System.out.println("Test Case 1: Expected: -1 Actual: " + gmrt.getMaxNumberRepeated(testList1));
		System.out.println("Test Case 2: Expected: -1 Actual: " + gmrt.getMaxNumberRepeated(testList2));
		System.out.println("Test Case 3: Expected: 5 Actual: " + gmrt.getMaxNumberRepeated(testList3));
		System.out.println("Test Case 4: Expected: 3 Actual: " + gmrt.getMaxNumberRepeated(testList4));
	}
	
	public int getMaxNumberRepeated(int[] listSorted) {
		// Base Case
		if(listSorted.length < 2) {
			return -1;
		}
		int countMaxRepeated = 0;
		int itemMaxRepeated = -1;
		int countCurrentRepeated = 0;
		int itemCurrentRepeated = -1;
		
		for(int i=1; i < listSorted.length; ++ i) {
			if(listSorted[i] == listSorted[i-1]) {
				itemCurrentRepeated = listSorted[i];
				++ countCurrentRepeated;
			}
			else {
				countCurrentRepeated = 0;
			}
			if(countCurrentRepeated > countMaxRepeated) {
				countMaxRepeated = countCurrentRepeated;
				itemMaxRepeated = itemCurrentRepeated;
			}
		}

		return itemMaxRepeated;
	}
}

- Bryant March 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is klogn solution using Binary search.

int main(void) {
	
	int a[] = {1,1,1,2,2,2,3,4,4,4,4};
	int max = 0;
	int size = sizeof(a)/sizeof(a[0]);
	int maxRepetitions = numberWithRepetitions(a, 0, size, max);
	printf("%d", max);
	return 0;
}

int numberWithRepetitions( int[] a, int low, int high, int *maxNo){

	if(a.length == 0){
	return 0;
}
if( a.length == 1){
	*maxNo = a[0];
	return 1;
}

int mid = high + low/2;

if( a[low] == a[mid] && a[high] == a[mid]){
	*max = a[low];
	return high-low ;
}

int range = 0;
int leftHigh = mid;
while( a[mid] == a[leftHigh] ){
	range ++;
	leftHigh--;
}
int rightLow = mid+1;
while(a[mid] == a[rightLow]){
	range++;
	rightLow++;
}
*max = a[mid];
return (max(range,
        (max(numberWithRepetitions(a,  low, leftHigh, &maxNo),
			   numberWithRepetitions(a, rightLow, right, &maxNo));
}

- supershal March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

//correction in last part of the code

int maxleft, maxright;
int maxRepetitions
int leftMaxRepetitions = numberWithRepetitions(a,  low, leftHigh, &maxleft) ;
int rightMaxRepetitions = numberWithRepetitions(a, rightLow, right, &maxRight);
if( leftMaxRepetitions > rightMaxRepetitions ){
	maxRepetitions = leftMaxRepetitions;
	*maxNo = maxLeft;
}else{
	maxRepetitions = rightMaxRepetitions;
	*maxNo = maxRight;
}
if( range > maxRepetitions){
	maxRepetitions = range;
	*maxNo = a[mid];
}
return maxRepetitions;

- supershal March 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Build a list for representing non-uniform segments using recursion. Each element contains a value and an index. The Space O(n/k), Time O(n/k) where k is the average number of repeats.

public class GetValueWithMaxRepeats {
	private static final boolean DEBUG = false;


	public static int getNumberWithMaxRepeats(int [] arr) { // input is a sorted array
		int n = arr.length;
		if( n  < 1) throw new IllegalArgumentException("Empty input array");

		int curCount = 1, curValue = arr[0];
		int maxCount = Integer.MIN_VALUE, maxValue = curValue;

		for(int i = 1; i < n; i++){
			if(curValue ==arr[i]){
				curCount++;
			} else {
				if(curCount > maxCount) {
					maxCount = curCount;
					maxValue = curValue;
				}
				curCount = 1;
				curValue = arr[i];
			}
		}
		if(curCount > maxCount) {
			maxCount = curCount;
			maxValue = curValue;
		}
		return maxValue;

	}

	
	private static class LNode {
		LNode next;
		int index;
		int value;
		
		LNode (int idx, int val) { index = idx; value = val; }
		@Override
		public String toString() {
			return "<"+value+" @ "+ index+">";
		}
		
	}
	
	public static int getNumberWithMaxRepeats_eff(int [] arr) { // input is a sorted array
		int n = arr.length;
		if( n  < 1) throw new IllegalArgumentException("Empty input array");
		if( n == 1) return arr[0];
		LNode start = new LNode(0,arr[0]);
		LNode end  = new LNode(n-1, arr[n-1]);
		start.next = end;
		createList(arr, start, end);

		if(DEBUG) {
			System.out.println("The list is: ");
			printList(start);
		}
		
		int curCount = 1;
		int maxCount = Integer.MIN_VALUE, maxValue  = start.value;

		LNode prevNode = start;
		LNode cur = start.next;
		while(cur!=null){
			if(cur.value != prevNode.value){
				if(curCount > maxCount) {
					maxCount = curCount;
					maxValue = prevNode.value;
				}

				curCount = 1;	
			} else {
				curCount+=cur.index - prevNode.index;	

			}

			prevNode = cur;
			cur=cur.next;
		}
		if(curCount > maxCount) {
			maxCount = curCount;
			maxValue = prevNode.value;
		}
		
		return maxValue;
		
		
		
		
	}


	private static void printList(LNode start) {
		LNode cur = start;
		while(cur != null) {
			System.out.print(cur+"->");
			cur = cur.next;
		}
		System.out.println("||");
	}

	
	private static void createList(int[] arr, LNode start, LNode end) {
		if(DEBUG) System.out.println("Start="+ start+", end="+end);
		if(start.value == end.value || start.index + 1 == end.index) return;
		int midIdx = (start.index + end.index)/2;
		LNode mid = new LNode(midIdx, arr[midIdx]);
		start.next = mid;
		mid.next = end;
		createList(arr,start,mid);
		createList(arr,mid,end);
	}


	public static void main(String[] args) {
		int [] arr = { 1,1,1,1,1,1,1,1,1,1, 2,2,2,2,2,2,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,6,6,7,8,8,8,8,8,8,8,8 };
		System.out.println(getNumberWithMaxRepeats(arr));
		System.out.println(getNumberWithMaxRepeats_eff(arr));
		
		
	}
	
	
}

- konst May 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaxRepetations {

public static void main(String[] args) {
int a[]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,3,3,3,3,3,4,4,4,4,4,4,4,5};
maxRep(a);
}
public static void maxRep(int[] a){
int maxcount =1;
int count =1;
for(int i=0;i<a.length;i++){
if(i!=a.length-1){
if(a[i]==a[i+1]){
count++;
}else{
if(count>maxcount){
maxcount = count;
count = 0;
}else{
count =0;
}
}
}
}
System.out.println("Max Count "+maxcount);
}

}

- Krishna June 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Ruby,

Using binary search to find the last positions of each kind of elements, and calculate count.
Using a heap to store all kinds of element and find the max.

Complexity: O(klogn), k is the number of kinds of elements.
In the example, [1,1,2,2,2,2,3,3,3], k will be 3

I'm using array in Ruby to mimic heap.

# [1,1,2,2,2,2,3,3,3]
# heap = [{:num=>2, :count=>4}, {:num=>3, :count=>3}, {:num=>1, :count=>2}]
def find_majority( a )
  i = 0
  heap = []
  while i < a.size
    last_i = i
    i = bsearch(a, i, a.size-1)
    heap << { num: a[i], count: (i-last_i+1).to_i }
    heap.sort!{|x,y| y[:count] <=> x[:count] }
    i += 1
  end
  heap.first
end

# [1,1,2,2,2,2,3,3,3]
# when i=0, j=9, it will find 1's last pos, which is a[1]
# when i=2, j=9, it will find 2's last pos, which is a[5]
def bsearch(a, i, j)
  return i if i==j
  mid = ((i+j)/2).to_i
  return mid if a[i]==a[mid] && a[mid] != a[mid+1]
  return a[mid] > a[i] ? bsearch(a, i, mid-1) : bsearch(a,mid+1,j)
end

- jonoson August 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is an algorithm whose best case is O(logN), worse case is O(N)

public static int findBiggestRepetitions(int[] arr){
		int p = 1,c =0;
		for(int i = 0; i<arr.length;i++){
			while(i+p<arr.length && arr[i] == arr[i+p])
				p *=2;
			if(p!=1){
				if(p>2){
					int t = p/4;
					p = p-t;
					while(t>0){
						t = t/2;
						if(arr[i] == arr[i+p])
							p +=t;
						else
							p-=t;
					}
				}
				if(p>c)
					c=p;
				i=i+p-1;
				p=1;
			}
		}
		return c;
	}

- Anonymous November 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int[] tab = new int[]{1,1,1,1,3,3,4,4,4,4,8,8,9,9,9,9,9,9,9};
		System.out.println(getBiggestRepetition(tab, tab.length));
	}
	

	public static int getBiggestRepetition(int[] array, int n)
	{
		int elm1, elm2, occ1, occ2;
	
		if(n==0) return -99999;
		
		elm1 = array[0];
		occ1 = 1; 
		int i = 1 ;
		while((i<n)&&(array[i]==elm1))
		{
			occ1++;
			i++;
		}
		
		if(i==n) return elm1;
		else
		{
			elm2 = array[i];
			occ2 = 0;
			for(; i<n ; i++)
			{
				if(array[i]==elm2)
					occ2++;
				else
				{
					if(occ1<occ2)
					{	
						occ1 = occ2;
						elm1 = elm2;
					}
					elm2 = array[i];
					occ2 = 1;
				}
			}
		}
			
		if(occ1<occ2)	
			return elm2;
		
		return elm1;
	}


}

- Slaheddine January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class App
{
public static void main( String[] args )
{
ArrayList<Integer> randomList = new ArrayList<Integer>();
Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();


for(int j =1; j<=10;j++)
{
randomList.add((int) ((Math.random()*10))+1);
}
int maxCount= 1;
int maxElement=randomList.indexOf(0);
for (Integer num : randomList)
{
int count=0;
if(!countMap.containsKey(num))
{
countMap.put(num, 1);
}
else
{
count = countMap.get(num)+1;
countMap.put(num,count);
}
if(count>= maxCount)
{
maxElement = num;
maxCount = count;
}

}
for ( Integer key : countMap.keySet() ) {

System.out.println( key+" "+ countMap.get(key));
}
/*for (Integer listNumber : randomList) {
System.out.println(listNumber);
}*/
System.out.println(maxElement);

}
}

- evs February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A different solution with O(n) time and O(1) space:
sum the numbers in the array and calc the average. if the average is smaller than the middle element, continue recursively to the left side of the array. else, continue recursively to the right side.

- JustMaybe April 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time O(1) space, I think this question is so simple, just go forward and keep track of max seen element

int findMostRepeatedNumber(vector<int>& array) {
	int max_count=1;
	int max_value=array[0];
	int count=1;
	int pre=array[0];
	for(int i=1; i<array.size(); ++i) {
		if(array[i]==pre) {
			count++;
		}else{
			count=1;
			pre=array[i];
		}
		if(count>max_count){
			max_count=count;
			max_value=pre;
		}
	}
	return max_value;
}

- jigili August 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since its said that the array is already sorted,

int findMaxRepeat(int a[], int cnt){
  int maxEle = 0;
  int maxCount = 0;
  int curEle = 0;
  int count = 0;
  int i;
  
  curEle = a[0];
  maxCount = 0;
  for(i=0;i<cnt;i++){
    if(a[i] ==  curEle){
      count++;
      if(maxCount<count){
         maxCount = count;
         maxEle = a[i];
      }
    }
    else{
      curEle = a[i];
      count = 1;
    }
  }
  return maxEle;
}

- kng December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Test

- cabaf January 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;

int find(int a[],int n){
      for(int i=0;i<n;i++){
       a[a[i]]+=n;
}
int res=0;
int maxi=a[0];
for(int i=1;i<n;i++){
    if(maxi>a[i]){
         maxi=a[i];
         res=i;
    }
}
return res;
}


int main(){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
cout<<find(a,n)<<endl;


}

- Amit Bhardwaj August 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

**
 * Given a sorted array of integers,
 * write a function that will return the number with the biggest number of repetitions.
 */
public class RepeatCounter {

    private final Stack<TabKeeper> tabKeepers = new Stack<>();
    private int[] numArrs = new int[]{2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 9, 9, 9, 9, 9};
    private int numArrsLength = numArrs.length;

    private int currentValue = numArrs[0];
    private int currentCounter = 0;


    public String getMaxOccurrence() {
        for (int index = 0; index < numArrsLength; index++) {
            if (currentValue == numArrs[index]) {
                currentCounter++;
                if (index == numArrsLength - 1)
                    saveCount(index);
            } else {
                saveCount(index);
            }
        }

        TabKeeper tabKeeper = tabKeepers.pop();
        return "The number " + tabKeeper.number + " occurs " + tabKeeper.numberMaxOccurrence + " times";
    }

    private void saveCount(int index) {
        if (tabKeepers.isEmpty()) {
            tabKeepers.push(new TabKeeper(currentValue, currentCounter));
            moveToNext(index);
        } else {
            if (tabKeepers.peek().numberMaxOccurrence < currentCounter) {
                tabKeepers.pop();
                tabKeepers.push(new TabKeeper(currentValue, currentCounter));
            }
            moveToNext(index);
        }
    }

    private void moveToNext(int index) {
        currentValue = numArrs[index];
        currentCounter = 0;
        currentCounter++;
    }

    public class TabKeeper {
        private int number;
        private int numberMaxOccurrence;

        public TabKeeper(int number, int numberMaxOccurrence) {
            this.number = number;
            this.numberMaxOccurrence = numberMaxOccurrence;
        }
    }
}

- Java code using Stack December 08, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More