You are given a file which contains all possible numbers on a 32-bit architecture. 4 numbers are missing from that file. Find the 4 missing numbers

Question

This is an interview question that I've run across a few times, and I'm really not sure how to solve it given that four numbers are missing. I'm familiar with algorithms for finding one or two numbers are missing, but I don't see a way to generalize either of them to four.

Answer 1

Whether it's for an interview or actual work, your first priority needs to be a working solution that makes sense to you. That usually means you should offer the first solution you can think of that is simple and easy for you to explain.

For me, that means sort the numbers and scan for gaps. But, I work on business systems and web apps. I don't fiddle with bits, and I don't want my team to!

If you're interviewing for a low-level, closer-to-the-metal job, "sorting" will probably be met with blank stares. They want you to be comfortable thinkings about bits and so forth. Your first answer there should be, "Oh, I'd use a Bitmap." (Or bit array, or bit set.)

And then, either way -- even if you give "wrong" solution, if your interviewer (or boss!) presses for it, you can suggest some improvements or alternatives, focusing on the manager's specific area of concern.

• Severely limited RAM? Less than 512MB?
  Sort it in place, on disk. You can use a mostly-arbitrary amount of RAM to optimize and/or buffer sorted blocks.
• Limited time?
  Use that RAM! Sorting is already O(n*log(n)). (Or O(n) for a integer-bucket sort!)
• Maintainability?
  What could be easier than sorting?!
• Doesn't demonstrate knowledge of bit flags/fields? (BitSet/BitMap/BitArray)
  Well OK ... go ahead and use a BitArray to flag the "found numbers." And then scan for 0's.
• Predictable "real-time" complexity?
  Use the bitmap solution. It's a single pass over the file and another pass over the BitArray/BitSet (to find the 0's). That's O(n), I think!

Or whatever.

Address the concerns you actually have. Just solve the problem first, using naive solutions if necessary. Don't waste everybody's time addressing concerns that don't exist yet.

Answer 2

Since it's a file, I'm assuming you are allowed to make multiple passes. First create an array of 256 counters, iterate over the file and for each number increment the counter indexed as the number's first byte. When you're done, most of the counters should be at 2^24, but 1 up to 4 counters should have lower values. Each of these indices represents a first byte of one of the missing numbers(if there are less than 4 it's because multiple missing numbers share the same first byte).

For each of these indices, create another array of 256 counters, and make a second pass on the file. This time, if the first byte is one of the values from before, increment a counter in it's array based on the second byte. When you are done, look again for the counters lower than 2^16, and you'll have the second byte of the missing numbers, each matched to it's first byte.

Do it again for the third byte(notice that you need a maximum of 4 arrays in each pass, even though each byte can be followed by up to 4 different bytes) and for the fourth byte, and you have found all the missing numbers.

Time complexity - O(n * log n)
Space complexity - constant!

Edit:

Actually, I considered the n=2^32 to be the parameter, but the number of missing numbers k=4 is also a parameter. Assuming k<<n this means the space complexity is O(k).

Update:

Just for fun(and because I'm currently trying to learn Rust) I implemented it in Rust: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f. I elected to have a textual representation, since on-one is going to run it with ~2^32 numbers...

Answer 3

If this were Java, you could use a BitSet. Well, two of them, because they can't quite hold all 32 bit numbers. Skeletal code, perhaps buggy:

BitSet bitsetForPositives = new Bitset(2^31);  // obviously not 2^31 but you get the idea
BitSet bitsetForNegatives = new Bitset(2^31);

for (int value: valuesTheyPassInSomehow) {
  if ((value & 0x80000000) == 0)
     bitsetForPositives.set(value );
  else
     bitsetForNegatives.set(value & ~0x80000000);
}

Then use BitSet.nextClearBit() to find who is missing.

Note added much later:

Note that with this algorithm, it is fairly easy to run the time consuming part in parallel. Say the original file has been split into four roughly equal parts. Allocate 4 pairs of BitSets (2GB, still manageable).

1. Have four threads, in parallel, each process one file into their own pair of BitSets.
2. When complete, go back to a single thread, or the Bitsets (trivial time), then call nextClearBit four times (also fairly trivial time).

I'd expect I/O to still be the rate limiting step, but if magically all the numbers were in memory you could really speed things up.

Answer 4

This question can be solved using an array of bits (true/false). This should be the most efficient structure to hold the answers for all the numbers using the index of the array to hold whether that particular number was found.

C#

var bArray = new BitArray(Int32.MaxValue);

//Assume the file has 1 number per line
using (StreamReader sr = File.OpenText(fileName))
{
        string s = String.Empty;
        while ((s = sr.ReadLine()) != null)
        {
            var n = int32.Parse(s);
            bArray[n] = true;
        }
}

Then just iterate through the array and for those values who are still false they are not in the file.

You could break the file into smaller chunks but I was able allocate a full int32 max size array (2147483647) on my 16.0 GB laptop running Windows 7 (64 bit).

Even if I wasn't running 64 bit I could allocate smaller bit arrays. I would pre-process the file creating a set of smaller files each with a range of [0-64000][64001-128000], etc. numbers in it that would be suitable for the available environmental resources. Go through the big file and write the each number to it's corresponding set file. Then process each smaller file. It would take a little longer because of the pre-processing step, but this would get around resource limitations if there was limited resources.

Answer 5

As this is an interview question, I'd show the interviewer some understanding about the constraints. Then, what does "all possible numbers" mean? Is it really 0 ... 2<(32-1) as everyone guesses? Usual 32-bit-architectures can work with many more than just 32 bit numbers. It's just a matter of representation, obviously.

Has it to be solved on a 32-bit-system, or is that rather a part of the restriction on numbers? For example, a typical 32-bit system will not be able to load the file into RAM at once. I'd also mention that a 32-bit-system will often not be able to have a file containing all the numbers due to file size limitation. Well, unless it has some clever encoding, like "All numbers except those four", in which case the problem is solved trivially.

But if you really want to understand the question as "Given a file with all numbers from 0 ... 2^(32-1) except a few, give me a missing ones" (and this is a big if!), then there are many ways to solve it.

Trivial but non-feasable: For each possible number, scan the file and see if it's in there.

With 512 MB of RAM and single pass through file: mark every number (= set bit at that index) read from the file, and afterwards pass the RAM once and see the missing ones.

Answer 6

One approach that is easy to remember and easy to articulate in an interview would be to use the fact that if you look at all the numbers in N bits, each bit will be set in exactly half of those values and not set in the other half.

If you iterate over all the values in the file and keep 32 counts of the values at the end, you will end up with 32 values that are exactly (2^32/2) or slightly less than that value. The difference that maximum (2^32/2) and the total gives you the total bits set in each position of the missing values.

Once you have that, you can determine all the possible sets of 4 values that could give those totals. Given that, you can then go through the values in the file again checking for any values that are part of those combinations. When you find one, combinations containing that value are eliminated as possibilities. Once you have only one possible combination remaining, you have you answer.

For example using a nibble, you have the following values:

1010
0110
1111
0111
1101
1001
0100
0101
0001
1011
1100
1110

The total bits set in each position is:

7867

Subtracting those from 8 (4^2/2) we get:

1021

Which means there are these following possible sets of 4 values:

1000
0000
0011
0010

1010
0001
0010
0000

(forgive me if I've missed any, I'm just doing this by sight)

And then looking at the original numbers again, we find 1010 right away meaning the first set was the answer.

Answer 7

Assuming that the file is sorted by increasing numbers:

Insure that it indeeds contains (2³²-4) numbers.
Now if the file were complete (or if the 4 missing numbers were the last 4 ones), reading any word in the file at position N would return matching value N.

Use a dichotomy search on positions [0..2³²-4-1) to search to find the first non-expected number X1.
Once found that first missing number, do a dichtotomy search again on positions [X1 .. (2³²-4-1)] to find the second missing, X2: This time, reading a word at position N should return matching value N-1 if there were no more missing numbers (since you passed one missing number).
Iterate likewise for the two remaining numbers. On the third iteration, reading word at position N should return N-2, and on the fourth, it should return N-3.

Caveat: I have not tested this. But I think it should work. :)

Now in real life, I agree with other answers: the first questions would be about the environment. Do we have RAM avail (how much), is the file on a direct access storage device, is this a one-shot operation (no optimization required) or a critical one (each cycle count), do we have an external sort utility available, etc.
Then find a compromise acceptable for the context. This at least shows that you start analyzing the problem before looking for an algorithm.

Answer 8

As with all standard questions the solution is to google them before the interview.

This question and variations have a very definite 'correct' answer involving XORing all the numbers. Its supposed to show you understand indexes in databases or something. So zero points for any 'might work but not what it says on the paper' answer im afriad.

On the plus side there is a finite set of these questions a few hours revision will make you look like a genius. Just remember to pretend you are working it out in your head.

Edit. Ahh it seems for 4 there is a different approach than XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

Edit. Downvoters : This is a published textbook O(n) solution to the exact problem stated in the OP.