## Amazon Interview Question

Country: United States

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

We know that the numbers present in the array are in the range 0 to n-1.
We traverse the array from left to right and for each element ,a[i], we increment the value at the index a[i] by n. In case the value at any index is more than (n-1) then we know that the index's value has been incremented because that index is the value we have already encountered while traversing the array. To know the exact value at that index we take mod of n and get the original value. Again considering that value say v as the index, we increment the value at the index v by n.
After we are done traversing once, we again traverse the array from left to right and find out which index's value has been incremented maximum times. We can do that by dividing the value by n. We can restore the original value of the array by taking mod of n for each element.

#include <iostream>
using namespace std;

int getMaxRepeatedNum(int *a,int m,int n)
{
int i,k,max=0,p=0;
for(i=0;i<m;i++)
{
k=a[i]%n;
a[k]+=n;
}
/* for(i=0;i<m;i++) cout<<a[i]<<"\t";
cout<<endl;*/
for(i=0;i<m;i++)
{
k=a[i]/n;
a[i]=a[i]%n;
if(k>max)
{
max=k;
p=i;
}
}
/* for(i=0;i<m;i++) cout<<a[i]<<"\t";
cout<<endl;*/
return p;
}

int main() {
int a[]={3,1,6,3,2,0,4,4,3,1,3,0,2,5,6};
int m=sizeof(a)/sizeof(a),n=7;
cout<<"Most repeated number is: "<<getMaxRepeatedNum(a,m,n);
return 0;
}

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

nice solution !

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

clever solution!

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

{1, 5, 5, 10}; would break your code though, since you arr [ arr[i]%range ] + range, when you do 5%10, it returns index 5, which is out of bounds.

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

Sort the numbers using Radix Sort, since the numbers are between some range, O(n) t.c. . Then go for linear search for the required answer.

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

You shouldn't use Radix Sort , because it uses secondary buffer. It's better to use QuickSort, if we are talking about least memory usage.

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

Doesn't radix sort have a worst case complexity of O(n) (for bucket allocation)?

I'd recommend something like quicksort (average case time complexity O(n logn), space complexity O(1)) and then a linear search & counting.

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

Cool solution. We have to be concerned about the overflow though (the value of an element can be incremented by n^2). Nice one anyways.

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

There are not enough info in the question, like can the array hold negative numbers and can we modify the array? If we can modify the array, should we reconstruct it at the end? I assume the answer to these questions is yes yes no.

The solution resembles applying a permutation to an array with minor differences. Since there are no negative numbers in the array, we can use negative numbers to mark cells as visited. Lets call the array A. The algorithm would be:

0. ind := 0
1. starting from ind, find the leftmost index i such that A[i] >= 0. ind := i (terminate if ind >= A.length)
2. a := A[i]
3. A[i] := -infinity (-infinity means we haven't seen i in the array so far)
4. while A[a] >= 0
5. temp := A[a]; A[a] = -1; a :=temp
6. /*here A[a] should be negative*/
7. if A[a] = -infinity then A[a] = -1 else A[a] := A[a] -1
8. go to step 1

At the end just scan through the array and find the minimum value in the array that is not - infinity.

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

``````int majority(int *a, int n)
{
int i, count;

if(n == 0)
return -1;

if(n == 1)
return a;

for(i = 0, count = 0; i < n; i += 2)
if(a[i] == a[i+1])
a[count++] = a[i];

if(n%2 && a == a[n-1])
a[count++] = a;

return majority(a, count);
}``````

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

I have no clue how to get the running time for this, appears between O(n) and O(nlgn)

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

Well, since we know the range of the inputs, we could bucket sort the array in O(n) and scan the resulted list in O(n).

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

nvm. doesn't satisfy the memory requirement.

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

``````/* 1. Sort the array using Quick sort. O(nlogn) */
/* 2. scan the array using 2 pointers to complete in O(n) */

checkfreq(int a[], int n)
{
int ffreq =0,freq =1, num = -1, *fptr =a, *sptr=a+1;
for(int i=1; i< n; i++,sptr++)
{
if(*fptr == *sptr)
{
++freq;

}else
{
if(freq > ffreq)
{
freq = ffreq;
num = *fptr;
}
fptr = sptr;
freq = 1;
}
}

printf(" Max repeating Number : %d with frequency : %d \n", num, ffreq);
}``````

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

Quick Sort for O(nlogn) + scanning the array O(n). memory reqirements O(1)

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

``````public class MaxRepeating {
int[] mIntArray;
int mMax;
}

public int getMaxRepeatingNumberIndex() {
for(int i=0; i<mMax;i++){
int indexToIncrement = mIntArray[i] % mMax;
mIntArray[indexToIncrement] += mMax;
}
int iMaxNumberOfIncrementAtIndex = 0;
int indexIncrementedMost = -1;
for(int i=0; i<mMax; i++){
int iNumberofIncrement = mIntArray[i]/mMax;
System.out.println("iNumberofIncrement: " + iNumberofIncrement);
mIntArray[i] =  mIntArray[i]%mMax;
if( iMaxNumberOfIncrementAtIndex < iNumberofIncrement){
iMaxNumberOfIncrementAtIndex = iNumberofIncrement;
indexIncrementedMost = i;
}
}

return mIntArray[indexIncrementedMost];
}

}``````

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

Why don't we sort the array and use the HashMap which contains only one value.

Example: 1,3,2,4,2,6,7,4,5,4
After Sorting: 1,2,2,3,4,4,4,5,6,7

Now, iterate over this array, maintain a count variable for each repeated number. For example: for number 2, count: 2. For 4, we get count 3, since this is greater than getCount(2), we simply delete that number from the hashmap and insert this new value.

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

Since there is no time limitation as such ... why not just perform a heap sort and keep counting the top of maxHeap ... O(1) space would be used by two variables ... one which keeps the previous max and the other one that keeps the current max.

In this case, you also get the O(nlog(n)) time complexity

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

``````public static int findMostRepeatingNumber(int[] arr){
int k = arr.length;
for(int num : arr){
arr[num%k] +=k;
}
int max = 0;

for(int i =0; i<k; i++){
if(arr[i]>arr[max]){
max = i;
}
}
return max;
}``````

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

``````public int maxRepeatingNo(int[]arr )
{
int[] noLookup = new int[Integer.Max_Value];
int maxno = 0;
int maxTime =0;
for(int i =0 ;i<arr.length;i++)
{
int a =arr[i];
noLookup[a]++;
if(noLookup[a] > maxTime)
{
maxTime = noLookup[a];
maxno  = a;
}
}
}``````

Time Complexity O(n)
SpaceComplexityO(1)

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.