Find an integer not in list of 4 billion using 4 mb. But 4 MB is not enough

Question

Given a list of 4 billion integers, find an integer not in the list using 4MB of memory. (interview was in Java)

My solution is to use a BitSet.

However according to my calculations there aren't enough bits in 4 MB of memory! = c

4 Megabytes = 4096 KB # multiply by 8

4096 KB =~ 4,096,000 Bytes # multiply by 1000

4,096,000 Bytes =~ 33,500,000 bits # multiply by 8

So 33,500,000 bits is two orders of magnitude less than a billion. Let a lone the 4 billion.

Or is it part of the question to work with this limitation?

Most likely it is very much a part of the challenge with the question, otherwise I doubt the memory limit would have been even mentioned in the question. — Joachim Isaksson, Mar 27 '14 at 21:04
What does "given a list of 4 billion integers" mean? How is it given to you? In a file? In a database? Carved in stone tablets? — Dawood ibn Kareem, Mar 27 '14 at 21:05

score 4 · Accepted Answer · answered Mar 27 '14 at 21:14

There's nothing in the question stating you can only make one pass of the data.

So, assuming it's not a mistake, you could still use a bit set but do it in groups. For the first pass, check only the numbers from zero to thirty million (roughly). Second pass, check from thirty to sixty million. And so on.

That would still allow you to find a missing number within the constraints of the question.

score 0 · Answer 2 · answered Mar 27 '14 at 21:18

0

You wanted a bloom filter.

Unlike a standard hash table, a Bloom filter of a fixed size can represent a set with an arbitrary large number of elements; adding an element never fails due to the data structure "filling up." However, the false positive rate increases steadily as elements are added until all bits in the filter are set to 1, at which point all queries yield a positive result.

Some additional reading

answered Mar 27 '14 at 21:18

Woot4Moo

23,987
16
94
151

The Bloom filter can answer the question of whether a particular number is present in the set, but it does not allow you to iterate over the set. Combined with a small but non-zero false positive ratio, it means you won't always be able to correctly identify the number not present in the set. – Michał Kosmulski Mar 27 '14 at 21:29
1

For the bloom filter to be useful in any way, each insertion will have to set at least 1 bit. The bloom filter will fill up long before you have read a significant fraction of the numbers. – maniek Mar 27 '14 at 21:29

score -1 · Answer 3 · answered Mar 27 '14 at 21:12

-1

iterate through the list and keep the max number. Then int notInList = max + 1

answered Mar 27 '14 at 21:12

user1411444

29
3

And if the list is {maxint}? – paxdiablo Mar 27 '14 at 21:16

Find an integer not in list of 4 billion using 4 mb. But 4 MB is not enough

3 Answers3

Linked