Amazon Interview Question for Software Engineer / Developers


Country: United States




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

let duplicated number be x and missing number by y
sum the elements to n numbers sum =(n)(n+1)/2-x+y
since we know sum and n we get x-y
similarly sum the sqare of elements we get sq_sum=(n)(n+1)(2n+1)/6-x2+y2
from this we get x2-y2
we can get x and y from this
complexity o(n)

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

Cool...I just forgot that there was even other formula for this...Mathematics rocks :0

- Stupid Developer May 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It has overflow problem.

- Akash Jain May 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Use Counting sort to find out duplicated and missing number in O(n) time

- Anonymous May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

// suppose we have int[] a = 1,2,3,4,5,5,7, yes I know it should be unsorted, just for demo purposes. corresponding         1,2,3,4,5,6,7

1. find missing XOR dup
2. find the rightmost setbit.
3. seperate a into two portation aLeft and aRight
seperate natural number list into bLeft and bRight
4. XOR all element in aLeft and bLeft 
    XOR all element in aRight and bRight you will find two numbers
5. identify which one is the missing one and which one is the dup one BY Comparing the length of the list


void func(int n, int [] a)
{
int missingXORdup  = 0;
for( int i = 0; i < n + 1; i++ )
{
 missingXORdup ^= a[i];
 missingXORdup ^= i;
}  //missingXORdup  = 5^6

List<int> aLeft  = new List<int>();
List<int> aRight  = new List<int>();
List<int> bLeft  = new List<int>();
List<int> bRight  = new List<int>();

int lowestSetBits = missingXORdup & ~( missingXORdup  - 1 ) // get the lowest set bit. use it to seperate array into two partition.

for( int i = 0; i < n + 1; i++ )
{
 if( lowestSetBits & a[i] > 0 )
      aLeft.add(a[i]);
 else
      aRight.add(a[i]);
 if( lowestSetBits & i > 0 )
      bLeft.add(i);
 else
      bRight.add(i);
} 
int ret1 = 0;
foreach( int i in aLeft )
    ret1 ^= i;
foreach( int i in bLeft )
    ret1 ^= i;
int ret2 = 0;
foreach( int i in aRight )
    ret2 ^= i;
foreach( int i in bRight )
    ret2 ^= i;
// now the missing one and the dup one are stored in ret 1 and ret 2. Now we need to decide which one is the missing one and which one is the dup one.
if (aLeft.count() > bLeft.count())
    Console.Writeline(" The dup one is {0} and the missing one is {1}", ret1,ret2);
else
    Console.Writeline(" The dup one is {0} and the missing one is {1}", ret2,ret1);
}

Gotta go...

- AmazonFailedXiYesterday May 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>

using namespace std;
int main()
{
int n,sum=0,squ=0;
cin>>n;
int a[n],b[n],k;
for(int i=0;i<n;i++)
{
cin>>k;
a[i]=k;
}
for(int i=0;i<n;i++)
{
b[i]=i+1;
}
for(int i=0;i<n;i++)
{
sum+=(a[i]-b[i]);
squ+=(a[i]*a[i]-b[i]*b[i]);
}
squ/=sum;
cout<<"duplicated number "<<(squ+sum)/2<<" and missing number "<<(squ-sum)/2<<endl;
return(0);
}

- Vineet Setia May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If I am understanding the meaning of an unsorted list of N natural numbers correctly
i.e. if N is 6 a possible list could be 2 3 1 5 6 4

and for the purposes of this question it could be 2 3 1 5 5 4

Couldn't we just run through the list populating a hash where the key is the number and the value is the occurrences of that number. Then we loop through the entire list a second time checking the numbers from the hash if the value is greater than 1 it is a duplicate if the value is not in the hash it is the missing number...

public void printOddities( int [] arr){
   HashMap<Integer, Integer> nums = new HashMap <Integer, Integer>();
   int miss, dup;
   miss = dup = 0;
   for(int i = 0; i < arr.length; i++){
      if( !nums.get(arr[i])){ nums.put(arr[i], 1); }
      else { nums.put(arr[i], nums.get(arr[i])+1 ); }
   }
   for( i = 1; i <= arr.length && (miss=0 || dup=0); i++){
      if( !nums.get(i) ){ miss = i; }
      else if ( nums.get(i) > 1){ dup = i; }
   }
   System.out.print("Missing num: "+miss+"\Duplicate num: "+dup);
}

- Anonymous May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Make an array of n elements. Lets say it is 'a'.
Initialize the array with zero.
now traverse the given array. Lets say it is 'b'.
Now do a[b[i]]++;
After complete traversing check each element of array 'a'.
The element which remains zer is the missing element and the one which has value two will be the duplicated one.

- maverick May 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

counting sort takes extra space....here one O(1) solution


1+2+..+n=n*(n+1)/2;

here one number is missing and 1 is duplicated.

So say, sum=total sum of array elements
and
mul=multiplication of array elements.

now,

if a=missing no and b=duplicated no,

| sum-n*(n+1)/2 | = |a-b|

and

mul/(n!) = b/a;

from this two equation, we can solve a and b..

- arwin May 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont see that your solution is of O(1). Rather it is O(n). The sum and mul here is the actual sum and mul of the elements in the input array and to calculate that you need to traverse the array element by element and this is of proportional to the number of elements in the array.

- Vikas Nalwar May 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ya i meant O(1) space.. not time

- arwin May 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

traverse array and make make that index value -ve means make a[a[i]] -ve. if it is already -ve then repeated . then travese it again whichever value would be +ve then that index is d number which is missing . o(n)time and o(1) space.

- time May 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take a Big Integer, traverse all the numbers and set the corresponding bit. If the bit is already set it means the number is repeated and one of the bit would be zero the number missing.

- Ramindar May 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's the solution which uses XOR...
O(n) Time, O(1) space.

static void PrintDupAndMissing(int[] array)
        {
            int xOR = 0;

            // XOR the elements in the array
            // with the sequence of Natural Numbers ( 1..N )
            for ( int i = 0; i < array.Length; i++ )
            {
                xOR ^= (array[i] ^ (i + 1));
            }
            // xOR = Dup ^ Missing

            int bit = xOR & ~(xOR - 1);
            int n1 = 0, n2 = 0;

            // Walk the array elements and the natural numbers again.
            // We XOR the Numbers together that share a bit with one the #'s in Dup^Missing
            //
            for (int i = 0; i < array.Length; i++)
            {
                if ( ((i+1) & bit) != 0 )
                {
                    n1 = (i+1) ^ n1;
                }
                if ((array[i] & bit) != 0)
                {
                    n1 = n1 ^ array[i];
                }
            }
            // One of the numbers has been computed, XOR it with Dup^Missing, to get the other.
            n2 = xOR ^ n1;

            Console.WriteLine("{0} {1}.", n1, n2 );
        }

- MessyHack May 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain the logic behind
int bit = xOR & ~(xOR - 1) ?

- Akash Jain May 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findDupAndMissing(int [] array,int n){

int [] tmp=new int [n];

for (int i=0;i<array.length;++i){
tmp[array[i]]++;
}

for (int i=0;i<tmp.length;++i){
if (tmp[i]==0){
System.out.println("missing: "+tmp[i]);
}else if (tmp[i]>1){
System.out.println("duplicated: "+tmp[i]);
}
}

}

- Anonymous May 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The size of array is N and it has been said that the array contains first n natural numbers. You know the size of array. Now start traversing the array, as you encounter a value, go to that position in the array and flip the number to negative. This takes O(1) per element and doing it for n elements would take O(n). if the value in a given position is negative already, this can happen only in case of duplication, store that position in a variable (this is the number that is repeating). Once this preprocessing is done, traverse the array again and there would be only one position that would have positive value. That position is the number that is missing. At the max you traverse the array twice or thrice and hence runtime complexity is O(n) and space complexity is O(1).

- newbie May 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since array is given with natural numbers. O(n) solution

1. Find duplicate number

int dupIndex = -1;
for(int i=0i<a.length;i++){
int val = Math.abs(a[i]);
if(a[val]<0){//duplicate index found
dupIndex = i;
break;
}
a[val] = -a[val];
}
a[dupIndex] is the repeating element.

2. Difference (((n*(n+1))/2) - get sum of all array numbers)+a[dupIndex] is the missing element.

- Praveen Kumar Ch May 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Its the easiest of the lots..

private static void Proceess2()
        {
            int[] arr = { 1, 1, 3, 4, 5, 6, 7, 8, 9, 10 };
            int duplicate = -1, missing = -1;
            int sum = 0;
            for (int i = 0; i < 10; i++) {
                if (duplicate==-1&&arr[i] != i+1) {
                    duplicate = arr[i];
                }
                sum += arr[i];
                
            }
            missing = 55 -sum+ duplicate;

            Console.WriteLine("Duplicate: " + duplicate + " Missing:" + missing);
        }

- Arjun May 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is written that the arry is not sorted

- yogi May 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for faster result better to use bit array instead of set

int test19()
{
  size_t nArrray[] = {2,10,4,3,6,5,7,1,3,8,0};

  const size_t n = _countof(nArrray);

  set<int> lstTest;

  int sum = 0, doubling = 0;

  for( size_t i = 0; i < n; i++ )
  {
      if( lstTest.find( nArrray[i] ) != lstTest.end() )
      {
         doubling = nArrray[i];

         cout << "duplicated number is " << doubling;
      }
      else
      {
         lstTest.insert( nArrray[i] );
      }
      sum += nArrray[i];
  }
  int missed = ( n * ( n - 1 ) / 2 ) - (sum - doubling);

  cout << " and missing number is " << missed << endl;

  return(0);
}

- LBaralgeen May 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int [] array={1,2,4,5,6,7,8,5,9};
int result=0;
int sum=0;
for(int i=0;i<array.length;i++)
{
result^=array[i];
sum += array[i];
}
System.out.println(result); //duplicate number
System.out.println(45-sum+result); // n(n+1)/2 - (sum ) + (duplicate number)

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

//correction
int result=array[0];
int sum=0;
for(int i=1;i<array.length;i++)
{

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

#include <iostream>
using namespace std;

int main(){
const int N = 10;
int input[N] = { 2 , 10 , 4 , 3 , 6 , 5 , 7 , 1 , 3 , 8 };
int ori_sum = N * ( N + 1 ) / 2;
int ori_sqr = N * ( N + 1 ) * ( 2 * N + 1 ) / 6;
for (int i = 0; i<N; i++){
cout << input[i] << endl;
}
int sum = 0;
int sqr = 0;
for (int i = 0; i <N; i++){
int cur = input[i];
sum = sum + cur;
sqr = sqr + cur * cur;
}
int s = ori_sum - sum;
int r = ori_sqr - sqr;
int dup = ( r - ( s * s) ) / (2 * s );
int miss = s + dup;
cout << "duplicate number : " << dup << endl;
cout << "missing number : " << miss << endl;
}
//out put
// duplicate number : 3
// missing number : 9

- Nan May 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int dupNo=sum=0;
for(int i=0;i<arr.length;i++)
{
if(!set.add(arr[i]))
dupNo=arr[i];
sum+=arr[i];

} // now finding missing element is simple
//n(n+1)/2- sum+dupNo

- Bharath gowda May 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it can be done in o(n)...
since 1 to N elements are present except one, and they are unordered,
just order it keeping sum as follow

int sum=0;
int duplicateNumber=0;
for(int i=0; i<array.size(); i++{
    sum +=array[i];
    if(a[a[i]] == a[i]){
          duplicateNumber=a[i];
     }
    else {
    swap(a[a[i]] , a[i]); 
   }
}

// sum of all numbers from 1 to N
int originalSum = ((array.size()*(array.size()+1)) /2)

sum = sum - duplicateNumber;

int ommittedNumber = originalSum - sum;

This is O(n) time and O(1) space algo.

- nix May 31, 2012 | Flag Reply


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