Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
awesome logic!!!!
Try to put the number you encounter into its proper position in the sorted list.
A no X should be at index x-1, you indicate that you encountered X already by making the number at X -ve. Next time when you encounter X, you have already made the value at index x-1 -ve so its a repeat and that is the number.
Can you please be little more clear, how are we using constant time . An example would be more than helpful
take the sum of the numbers and take the product of the numbers (or sum of square). Then the repeating number can be solved out.
if overflows is a concern, I propose the following soln:
1. calculate the sum of nos and subtract it from N*(N+1)/2
2. calculate the sum of squares and subtract it from
N*(N+1)*(2N+1)/6.
this gives us two equations of the form:
a - b = X
a^2-b^2 = Y
from which the missing no can be easily found, the code is below:
int a[] = {2,1,3,4,8,6,7,8,9,10};
int N = 10;
int sum = 0, sum_sq = 0;
for(int i = 0; i < N; i++) {
sum += a[i];
sum_sq += a[i]*a[i];
}
int true_sum = N*(N+1)/2,
true_sum_sq = N*(N+1)*(2*N+1)/6;
int X = true_sum - sum,
Y = true_sum_sq - sum_sq;
int missing = (Y / X + X) / 2;
I don't think the above works ..i might have made a mistake with math.. but can u confirm it with calculation of above example.
Code works very fine....great!!
But it finds the MISSING NUMBER not the REPEATING NUMBER
One way is to create a hash map of all the numbers from 1 to 100, which will record the count of each number. If any count of any number is incremented twice, we get the repeating number.
void findRepeatedEle(int a[], int len) {
int hash[len], i;
for(i = 0; i < len; i++)
hash[i] = 0;
for(i = 0; i < len; i++) {
if(hash[a[i]]) {
printf("The repeated element is %d\n", a[i]);
break;
}
hash[a[i]]++;
}
}
The other way is to create a binary search tree. When a node in the tree matches the value of the next element being inserted, we get the repeating element.
Interviewer asked me .. In case we do not have space , how we will be able to find that number efficiently. ?
A funky sort algorithm that spits out any duplicates and runs in O(n):
Start by swapping out an element (arr[x]) with -1.
Take that number (temp) and swap it into its sorted location(arr[temp-1]).
Repeat while we don't get -1 back and don't find a collision (temp == arr[temp-1]).
If we find a cycle, -1 will be back in temp.
If we find a collision, the duplicate number will be in temp. Print it!
At this point you can break but I keep the funky sort going just for fun.
Enjoy!
Java
// int arr[] = { 6,10,1,4,5,8,7,9,2,8 };
int arr[] = { 9, 1, 8, 2, 7, 3, 6, 4, 5, 5 };
// int arr[] = {9,1,8,2,7,3,6,4,5,5,6,4,4,4,4,4,4};
int temp;
int aux;
int count = 0; // For Fun
for (int x = 0; x < arr.length; x++) {
temp = arr[x];
arr[x] = -1;
while ((temp != -1) && (temp != arr[temp - 1])) {
aux = arr[temp - 1];
arr[temp - 1] = temp;
temp = aux;
count++; // For Fun
}
if (temp != -1)
System.out.println("Duplicate: " + temp);
}
System.out.println("Time: " + count); // For Fun
// For fun. Spits out the array as 1,2,3,...,n,-1,-1,...,-1 (a -1 for
// each duplicate)
System.out.print("Final array:");
for (int x : arr) {
System.out.print(" " + x);
}
Edited for whitespace!
for(i=0; i< NUM_ELEM; i++)
{
temp = a[i];
if(a[temp] / (NUM_ELEM+1) > 0)
{
// if you just want to find the repeating element
cout<< "the repeating element is"<<temp;
break;
}
a[temp] += (NUM_ELEM + 1);
}
any reason for down grading it.. first of all did you have the sense of under standing it? btw.. the " sum the numbers" solution has the problem of overflow..
Small mistake in the code.. but all i wanted to convey was the essence of the solution. try this!!
for(int i=0; i< NUM_ELEM; i++){
temp = a[i] -1 ;
if(a[temp] / (NUM_ELEM+1) > 0)
{
// if you just want to find the repeating element
printf( "the repeating element is %d", temp + 1);
break;
}
a[temp] += (NUM_ELEM + 1);
}
it requires some brain to understand.. execute with a[100] = {1, to 99} and see if it works..
we are treating the array it self as a bit vector and increasing the value at an index by a costant, to count the number of times that index is repeating..
We can do it in O(n) and constant space
- loveCoding January 30, 20121. for every element calculate index = Math.abs(a[i]) -1
2. check the value at index
a. if it is +ve, multiply by -1 i,.e make it -ve.
a. if it is -ve return (index+1) i.e. the value thats repeated.