## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

We can do it in O(n) and constant space

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

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

can u please explain with a small example ?

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

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.

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

Can you please be little more clear, how are we using constant time . An example would be more than helpful

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

Can you please be little more clear, how are we using constant time . An example would be more than helpful

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

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.

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

is there n't something called overflow??

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

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

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

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.

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

Code works very fine....great!!
But it finds the MISSING NUMBER not the REPEATING NUMBER

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

@p : its ((y/x)+x)/2

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

@ coding for fun :

repeating number can be found by sum+missing-true_sum;

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

or ((y/x)-x)/2

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

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

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

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.

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

2 ways:
Sol 1:
1: Create a bool of size n.
2: For each entry in array, if bool_array[n[i] - 1] is true, then, that's the duplicate element.

Sol 2:
1: Sort the array.
2: for i = 1 to n - 1:
2.1: if a[i] == a[i - 1] return a[i];

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

Interviewer asked me .. In case we do not have space , how we will be able to find that number efficiently. ?

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

if the use of space is not permitted, the solution provided by wdong seems plausible.

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

Use the variation of couting sort, where
whenever you try to increment the value at index in the counting array, if its a 2 we have the element as index+1.

I like the solution posted by Manan too. But this is my idea if constant space is allowed.

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

public int find(int[] a){
int temp[]=new int[100];
for(int i:a){
if(temp[i-1]!=0){
return i;
}
else temp[i-1]=i;
}
return 0;
}

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

``````public static int find(int[] a){
int temp[]=new int[100];
for(int i:a){
if(temp[i-1]!=0){
return i;
}
else temp[i-1]=i;
}
return 0;
}``````

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

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!

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

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

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

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

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

I executed your code on my system, it does not give correct answer.

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

I executed your code on my system, it does not give correct answer.

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

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

}``````

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

this code has zero logic. what does that if condition mean there ?

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

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

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

this code has flaw in that it will throw ArrayIndexOutOfBounds Exception because of a[temp] += (NUM_ELEM + 1) and temp = a[i] -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.