Epic Systems Interview Question
even if you use just one bit per number you dont have enough bits (so using a 10mb memory as an array of 1 bit cells containing a 1 if its array index is part of the list wont work)
I don't know if I get the question correctly, but I guess one iteration over all the numbers is a must. So, either find the max or min of the 4 billion numbers. The max + 1 or min - 1 is the number that doesn't exist in the file. O(n)
Good idea, then, we can use
fgetpos to record the position of the last reading,
and then use fsetpos to go the position of last reading.
We keep an variable for max or min
Therefore, we can go one iteration with 10MB
If the max = MAX_INT and min = MIN_INT then max+1 and min-1 would cause integer(unsigned long long or whatever) overflow.
we need to store the [range] of available numbers. lets start with [min,max] inclusive.
now on iterating, we ll split the range if we come across a number in existing ranges.
for example, if we get 10, then our ranges become {[min,9]; [11,max]}.
algorithm:
1. init ranges to {[min,max]}
2. for each number k
3. if k is in any of the ranges, split the range
4. if k is the only number that can be in a range (say [k,k]) then delete the range from the list of ranges.
after iterating, pick a number from the list of ranges.
time O(n)
worst case space O((2^16)/2)
assuming 2 bytes per int, ints are not sorted and diff between consecutive ints >= 2
takes 32mb for storing range values.
best case space O(4)
ints are sorted and diff between consecutive ints is <= 1
takes 8 bytes for storing range values.
All you need is 2 int variables. Store 0 in one of the variable. Read the 1st integer from the file into the 2nd variable. Get the greatest out of the two. Get the next integer from file and compare to the greatest which you already have. Repeat till you have the greatest number. Add 1 to it and that is the number which is not in the file.
NOTE: int in any language has constraints to what is the greatest number it can hold or else there will be overflow.
4 billion integers sum......???
- conquersky September 21, 2009