Microsoft Interview Question
Country: -
Adding numbers is probably fastest if only 1 number is missing.
Worse ways:
Sort 2 stacks then walk them.
Hash the numbers in the smaller stack then walk the other one checking hash. (If same number is in there twice you mark it in hash table as number 2 then while walking you substract 1 each time you find that number. When you don't find it in hash, that is the number.
#include "stdio.h"
int main()
{
int stack1[]={10,12,13,14};
int stack2[]={12,10,14};
int size1= sizeof(stack1)/sizeof(stack1[0]);
int size2= sizeof(stack2)/sizeof(stack2[0]);
int missednumb=0;
int i=0;
if (size2<size1)
{
while(i<size2)
{
missednumb^=stack1[i]^stack2[i];
i++;
}
}
else
{
while(i<size1)
{
missednumb^=stack1[i]^stack2[i];
i++;
}
}
if (size2<size1)
{
missednumb^=stack1[i];
}
if (size1<size2)
{
missednumb^=stack2[i];
}
printf("\n The Missed number is %d",missednumb);
return 0;
}
for both stack s1,s2
pop elements of s1 first
-maintain a separate negativesum and a positivesum(sum of negative & positive no.s respectively);
-lets say they r ns1 & ps1
similarly for s2
find ns2,ps2
now
if(ns1==ns2) { if(ps2>ps1) missingno=ps2-ps1;
else missingno=ps1-ps2;
}
else if(ps1==ps2) { if(ns2>ns1) missingno=ns2-ns1;
else missingno=ns1-ns2;
}
the missing number = xor all numbers from both stacks
- Anonymous October 02, 2011