A Microsoft Interview: Attempt #2
So I had another initial interview with a Microsoft developer this evening - this time over the Phone instead of in person.
The problem I was given to solve:
You are given an array of size N, filled with the consecutive integers from 0 to N-1. One of the integers is missing from this array. Write a function to find it and return it.
Example Array: A[] = {0,1,2,3,4,5,6,8,9,10}
My first solution was to traverse the array, and asser that each index was only 1 greater then its previous index. The ideal solution is to simply check that the value at the current index in the array, equals the index. So in the above example, A[0] = 0, and A[1] = 1, and so on.
Once you find an index that does not match the value - then the current index has identified the missing integer.
// find the missing int in an array of consecutive ints
int findMissingInt(A[]) {
for (int x = 0; x < 10; x++) {
if (a[x] != x) {
return x;
}
}
}
While this solution works - it is a little slow if you have a ton of elements (like 1000). O(n) to be exact. Every single element needs to be visited to find our missing integer.
So Mr.A (the interviewer) asked for a better solution - one that is fast then O(n).
Below is the final solution. Which unfortunately I feel took me too long to realize - after 30 minutes on the phone I was already well flustered and starting to draw blanks on the simple aspects of life.
int findMissingInt(A[]) {
int low, high, mid;
low = 0;
high = 10;
while (high > low) {
mid = low+()(high-low)/2);
if (a[mid] != mid) {
// missing integer is on the left side of the list
high = mid;
} else {
// missing integer is on the right side of the list
low = mid;
}
}
// once high is < low, we have found our missing integer, it will be the high bound.
return high;
}
Hey,
I think you can solve the problem using the sum of all numbers. Sum of Numbers must equal to (N*(N+1)/2), the missing number “x” will make the sum of the array less than that value by x.
However, this solution fails if the missing number is ZERO !
Best of luck :)
a.
20 Feb 08 at 4:25 am
That’s exactly the sort of crap I would have hung up on. Good for you for sticking with it.
Randy Aldrich
20 Feb 08 at 10:56 am
The main problem I see, this won’t work for all arrays. Why not take a[0] and a[N] for low and high respectively.
PSSTTT Where is the goat food recipe!?
Rob
20 Feb 08 at 12:22 pm
Sorry about the goat food Im working on it. There’s been to much snow lately!
Carol
20 Feb 08 at 12:31 pm
The solution of adding all elements in the array and comparing to (N*(N+1)/2) is very interesting, but if you’re going to traverse the entire array in order to add the values, it’s not as efficient as just comparing them and breaking out when the incorrect value is found.
Only in the worst case of the last number being incorrect will they be equal in speed.
Jason Laver
20 Feb 08 at 1:05 pm
For the missing number - is there just a missing element from the array ie. {0,1,3,4} or is there a bad number ie. {0,1,0,3,4}.
In the second situation the Nick’s final binary search wouldn’t work since it relies on there being a reduced number of elements in the array.
However in the first situation Nick’s algorithm (runs O log(n))would beat out A’s and Jason’s (O(n)). There isn’t too much differnce between the 2 O(n) algorithms. It’s true that Jason’s will break out sooner when you find the value, however there is slightly less processing that needs to be done per cycle with the (N*(N+1)/2) solution so it would probably end up being a draw in the end.
Well good job with the interview Nick! Important thing is you got the solution. Hopefully I will be seeing you out her for the second round of interviews soon!
Brandon Wilson
20 Feb 08 at 1:40 pm
Best case scenario Nick’s original solution is faster. average and worst case scenario the adding solution is faster. Adding instructions are much cheaper than comparisons.
I fail to see how the adding solution cannot account for 0.
expected-actual=missing
if 0 is missing then expected-actual will be 0. This doesn’t account for the case that NOTHING is missing, but that’s not part of the problem description since it includes the following:
“One of the integers is missing from this array.”
What the adding solution doesn’t account for is order. It doesn’t care. The actual values could be completely reversed and it would still return the ‘missing’ number. This doesn’t match the problem description which is:
“You are given an array of size N, filled with the consecutive integers from 0 to N-1.”
In fact, this displays a defect in the actual problem description itself. Is the function’s job to find the missing number or the first out of sequence number?
If the answer is to find the missing number then the adding solution is easily the best. If the answer is to find the first out of sequence number then adding wouldn’t even work.
Randy Aldrich
20 Feb 08 at 3:00 pm