23

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.

1

8 Answers 8

20

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.

18
  • I am not so sure about feasibility of sorting 4 billion numbers with a naive approach, let alone on disk. Have never tried it, though.
    – Eiko
    Oct 17, 2016 at 17:40
  • 1
    @Eiko Well ... and again, the main point is ... don't over-complicate things. The first step is to just solve the problem, any way you can think to solve it, even if it's naive. I can't even stress the level of frustration your future employer will have if you're spending time iterating to make sure you have with "the right" solution when the business just needs a solution. Prove that you can do both! Prove that you can solve problems quickly, and then identify potential problems worth refactoring and/or optimizing for as needed.
    – svidgen
    Oct 17, 2016 at 18:53
  • 1
    @Ewan "Because you've had the question come up on at interview" is not the same as, "There's one specific answer every manager is looking for." ... I certainly wouldn't care what solution you gave me, as long as you demonstrated an ability to solve the problem and not get caught up solving problems I never gave you!
    – svidgen
    Oct 17, 2016 at 21:57
  • 1
    You're missing the point. This question and its variations occur in books of programming puzzles and interview questions. It's not been made up by the person asking the question. the 32bit stuff is supposed to make it impossible to do by keeping track of the numbers or sorting. Its just computers have got faster/bigger since it was written.
    – Ewan
    Oct 17, 2016 at 22:04
  • 1
    @Ewan: you're still assuming that your instance of the question has the same constraints as the OPs. The OP didn't say his algorithm has to run on a 32 bit machine, he didn't even say it has to run on a computer at all, a conceptual algorithm could be suitable. He also doesn't state what "all possible numbers" means, as arbitrary sized integer math is possible on even 8-bit microcontrollers. Quite a lot of assumptions you're making to be giving absolute statements. Oct 17, 2016 at 22:07
19

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...

17
  • Holding all the numbers in memory (for multiple passes) requires 4 bytes * 2^32 memory, which is pushing things. So more likely you'll do all the I/O four times. But the other memory used is extremely small, so great job there.
    – user949300
    Oct 17, 2016 at 4:05
  • 1
    @user949300 I'm assuming this solution reads the file piece by piece rather than loading the whole thing into memory at once Oct 17, 2016 at 5:52
  • "most of the counters should be at 2^24, but 1 up to 4 counters should have lower values" - wrong: can be 0, with all missing values sharing the first byte (also second and third is possible). Next: how many array do you create in the second pass? 256, 1 to 4 times 256, 256 times 256? And then in the third and forth pass? Oct 17, 2016 at 7:37
  • 3
    @BernhardHiller The file contains all possible numbers in the 32-bit space, save for 4 distinct numbers. As such, all of the first bytes will occur, only 1 to 4 of them will have fewer hits. Oct 17, 2016 at 9:59
  • @LasseV.Karlsen thanks, now I understand the algorithm. Oct 17, 2016 at 14:00
6

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.

12
  • 3
    @Idan Ayre. This solution requires little code, so less chance of coding errors. I'm pretty this is time O(n). Nor does it assume/require multiple passes through a huge file, so it uses less space than an algorithm requiring multiple passes. Please elaborate what you mean by "Oh dear".
    – user949300
    Oct 17, 2016 at 3:59
  • 2
    Doesn't handle Integer.MIN_VALUE correctly. You could mask out the sign bit instead of negating to fix it. Oct 17, 2016 at 11:46
  • 1
    This naive approach needs 2^32 bits = 4 Gib = 512 MiB for the bitsets, which is a modest amount of RAM, even on a 32-bit system. Oct 17, 2016 at 11:47
  • If the language of choice has no built in bitsets, emulating them by using a byte array. For example in C#: bool GetBit(byte[] byteArray, uint index) { var byteIndex = index >> 3; var bitInByte = index & 7; return (byteArray[byteIndex] >> bitInByte) & 1 != 0; } Oct 17, 2016 at 11:52
  • 1
    @JoulinRouge (and JacquesB) So, we agree that this is linear in time, uses modest (1/2 Gig) RAM, and only takes one pass of I/O. Works for me.
    – user949300
    Oct 20, 2016 at 17:29
5

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.

2
  • This doesn't appear to handle negative numbers. (Or unsigned ints with the highest bit set if thats the input.) The memory for the bitset should not be a problem even on most 32 bit systems.
    – user949300
    Oct 17, 2016 at 20:11
  • @user949300 - Correct. I didn't notice any large memory consumption when the array was initialized with all false values. One would need a secondary BitArray for the negative numbers. Maybe bArrayNegative = new BitArrary(Int32.MaxValue). When the number was read it could be checked for positive or negative and then put into the appropriate Bit Array. Thanks for the comments.
    – Jon Raynor
    Oct 17, 2016 at 20:24
2

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.

2
  • 1
    Some good questions, but whether the 32 bit system is representing ints, floats, or huzziwigs, it still can only represent 2^32 values in 32 bits. If the question is "oh yeah, we allow 128 bit ultra-longs", then the 32 bit architecture "constraint" in the question is deliberately misleading. Still, a great question to ask the interviewer, because many specs are misleading or poorly written. Your actual solution is a BitSet like mine.
    – user949300
    Oct 17, 2016 at 16:50
  • @user949300 Yes - and it's impossible to know what the interviewer is looking for. If the last person they hired was a "stack hacking before thinking" guy, your answer should be different than if it was a "has absolutely no idea about architecture" or "playing the optimisation game" guy. :) I've worked with large bitsets before (though not in Java), so they come into my mind naturally. And can be adopted for lower memory as well if needed (bucketing). The bitsets also solve the "sorting problem" in the comments above in linear time with 512 MB of RAM.
    – Eiko
    Oct 17, 2016 at 16:59
0

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.

4
  • but you have to find 4 numbers, not one
    – freedev
    Oct 19, 2016 at 13:41
  • @freedev You are correct. That's what it does. A set of four numbers is four numbers... in a set.
    – JimmyJames
    Oct 19, 2016 at 13:52
  • Interesting, but you gloss over determine all the possible sets of 4 values that could give those totals. I really think this is an important part of the solution which is missing from your answer. It can also affect time and space complexity. Oct 21, 2016 at 15:58
  • @AllonGuralnek You are right on. I spent a little time working through this and I had vastly underestimated how many sets of 4 numbers would add up to the same number in the worst case. I think this is a salvageable idea but it's a good bit more complicated than I've laid out here. I will update with details later. I appreciate the feedback.
    – JimmyJames
    Oct 22, 2016 at 0:39
0

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.

-2

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.

15
  • 1
    Notably, this linked book is all about stream processing. In particular, stream processing within constraints. That said, I certainly would believe that this is the origin of the question the OP has seen, since it is otherwise pretty trivial. More notably, you haven't actually answered the question. You'll have +1 from me if you can convincingly posit this as the "original" or "intended" question and explain the solution ... but, this doesn't answer anything as-is.
    – svidgen
    Oct 18, 2016 at 4:13
  • 1
    This answer (in an interview) just shows that you read the book. Nothing about your skills or thought processes. And how do you "google all standard questions" before an interview? Is there some finite list of "all questions ever asked at an interview" that I missed?
    – user949300
    Oct 18, 2016 at 5:18
  • 1
    @ewan it also underscores the difficulty of hiring a good candidate! If the "good" ones are simply well prepared for the interview questions... It becomes difficult to hire someone who can actually solve my business problems?
    – svidgen
    Oct 18, 2016 at 11:51
  • 1
    @ewan To be clear, I was making fun of my incorrect punctuation. ... In any case, bear in mind, I also have received a fair number of job offers in my day, even being pretty darn ignorant of the standard questions and answers like this. And now, as a hiring manager, I can promise you I don't want recited answers... Though, I do understand some managers will have different needs.
    – svidgen
    Oct 18, 2016 at 13:26
  • 1
    @Ewan I should also clarify one more thing, if my tone wasn't received as intended: You should revise your answer to actually assert that the problem in the linked-to book is the "intended question." And then answer the question! ... You undoubtedly would have my +1, and plenty others, and the satisfaction of helping the OP for doing so.
    – svidgen
    Oct 18, 2016 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.