## Google Interview Question for Software Engineer / Developers

• 2

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;
int element=a;
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)));

}``````

Comment hidden because of low score. Click to expand.
-1

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@srikantaggarwal- it returns 1

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
-1

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.

Comment hidden because of low score. Click to expand.
0

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;

Comment hidden because of low score. Click to expand.
0

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..

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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;
}

}``````

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.

Comment hidden because of low score. Click to expand.
0

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) .

Comment hidden because of low score. Click to expand.
2

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)

Comment hidden because of low score. Click to expand.
0

What average Theta(log n)? Nonsense.

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.

Comment hidden because of low score. Click to expand.
0

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

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)?

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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 :)

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;
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);
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 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
# when i=2, j=9, it will find 2's last pos, which is a
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``````

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;
}``````

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;
int count =0;
int maxrepvalue =a;
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));

}

}

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;
}``````

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........

Comment hidden because of low score. Click to expand.
0

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

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);

}``````

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);
int num, max_repeat = 1;
int prev = a;
int rep = 1;
int i;
num = a;

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 );
}

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;
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));
cout<<maxRepeatElement<<"\n";
}``````

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``````

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
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")
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

For sorted:

``````int max_value = A, max_count = 1;
int value = A, 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

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

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;
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;
}``````

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;
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];
}

}``````

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();
}

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;
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

}``````

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));
}
}

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;``````

}

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));``````

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)``

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);
}
}``````

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;

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);

}``````

Comment hidden because of low score. Click to expand.
0

complexity is of O(n)

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;

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;

}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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. :)

Comment hidden because of low score. Click to expand.
0

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.

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;
int highest_count = count;
int retVal = i;
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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a, 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();
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a, 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();
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a, 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();
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a, 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();
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a, 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();
}

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);
}

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?

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;
}
}``````

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);
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;
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));
}``````

Comment hidden because of low score. Click to expand.
0

//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;``````

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;
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;
LNode start = new LNode(0,arr);
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));

}

}``````

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);
}

}

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;
}``````

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;
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;
}

}``````

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++)
{
}
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);

}
}

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.

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;
int count=1;
int pre=array;
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;
}``````

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;
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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Test

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;
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;

}``````

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;
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;
}
}
}``````

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.

### 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.