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.

- loveCoding January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u please explain with a small example ?

- Anony February 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ann February 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- MAC March 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- voldemort00 March 02, 2012 | Flag
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.

- wdong January 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

is there n't something called overflow??

- Duh.. February 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

- 111 February 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- p February 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- coding for fun March 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous May 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ coding for fun :

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

- Anonymous May 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous May 17, 2012 | Flag
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);
}

- SpinLocked January 29, 2012 | Flag Reply
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.

- cooldaa January 30, 2012 | Flag Reply
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];

- smffap January 30, 2012 | Flag Reply
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. ?

- Mr Gupta February 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- cooldaa February 03, 2012 | Flag
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.

- hello world February 02, 2012 | Flag Reply
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;
}

- Vikram February 02, 2012 | Flag Reply
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;
	 }

- Anonymous February 02, 2012 | Flag Reply
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!

- Awesumness February 14, 2012 | Flag Reply
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);
}

- SpinLocked January 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SpinLocked February 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- cooldaa February 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- cooldaa February 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SpinLocked February 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anony February 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SpinLocked February 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this code has flaw in that it will throw ArrayIndexOutOfBounds Exception because of a[temp] += (NUM_ELEM + 1) and temp = a[i] -1 ;

- Anonymous October 31, 2012 | Flag


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