Amazon Interview Question
Software Engineer / DevelopersCountry: United States
// 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...
#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);
}
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);
}
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.
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..
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.
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 );
}
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]);
}
}
}
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).
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.
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);
}
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);
}
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)
#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
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.
let duplicated number be x and missing number by y
- Anonymous May 24, 2012sum 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)