Log in! (forgot password)
Microsoft Interview Question - Count it Out
This problem is more targeted towards people with Computer Science or similar backgrounds, it is a REAL question from an interview with Microsoft.
You have an array of 99 unique numbers from 0-100. What is the fastest (in computing) way to find the number between 0 and 100 that is not in the array?
Discussion
Ouch… the code’s wrong too!
Remember – values are not necessarily initialized to 0 like you’re assuming!
Take a look (remember, there’s supposed to be stars where the bold starts/stops – and this is just 5 numbers from 0 to 5):
int main(){
int array16 = {1,2,3,4,5};
int array26 = {0,1,2,4,5};
printf(“%d\n”,findMissing(array1));
printf(“%d\n”,findMissing(array2));
printf(“%d\n”,findMissing2(array1));
printf(“%d\n”,findMissing2(array2));
}
int findMissing(int *myArray){
int ans, currentTotal, index;
for(index = 0; index < 6; index++){
currentTotal += myArray[index];
}
ans = (5*3) – currentTotal;
return ans;
}
int findMissing2(int *myArray){
int ans, currentTotal, index;
currentTotal = 0;
for(index = 0; index < 6; index++){
currentTotal += myArray[index];
}
ans = (5*3) – currentTotal;
return ans;
}
On my system I run it and I get:
-1998321152
-2107044387
0
3
0 and 3 are correct, but the first two numbers are not – even though both functions take the same parameters and perform the same operations (correctly, aside from initializing currentTotal to 0).
I guess the question should have been 99 unique numbers from 1 to 100 (both inclusive).
it’s true..for some reason the *s for pointers and multiplication don’t format correctly..if you look, the bold text starts where the first star (pointer) should appear and ends where the multiplication of 50 by 101 should appear….
Not only is there a problem with the question, your code is wrong. Your function takes an integer when it should take an array (or at least a pointer to an array.)
Also, the sum of integers from 0…100 is 5050, not 50101.
there is a problem with this question, if you have an array of 99 unique numbers from 0-100 there is not just one number that is missing, there are two. The numbers 0-100 are 101 in size.
Difficulty
Currently: Moderate (4.44)
