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

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

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

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

It has overflow problem.

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

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 )
else
if( lowestSetBits & i > 0 )
else
}
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...

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

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

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

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

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

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.

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

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

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.

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.

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

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

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

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

}

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

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.

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

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

It is written that the arry is not sorted

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

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)

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

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

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

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++)
{
dupNo=arr[i];
sum+=arr[i];

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

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.

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.