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
I do not like the answer.
Firstly you need to know what is the sum of the first 100 integers. Besides:
the last line should be: ans = currentTotal – 5050;
the function parameter should be int *myArray
the loop condition is wrong and should be i < 100
Moreover this way faster:
int findMissing(int *myArray)
{
int ans;
int value = ~ 5F; // ~ 95
for(int i = 0; i < 100; i++)
{
if (myArray[i] & value && //check if > 96 or < 0
(myArray[i] < 0 || myArray[i] > 100)) { // comes here 4 times max
ans = myArray[i];
break;
}
}
return ans;
}
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)
