It's an interview question:
There are 1 billion cell-phone numbers which has 11 digits, they are stored randomly in a file, for example 12345678910, the first digit gotta be 1. Go through these numbers to see whether there is one with duplicate, just see if duplicate exists, if duplicate found, return True, or return False. Only 10 MB memory allowed.
Here is my solution:
Hash all these numbers into 1000 files using hash(num)%1000
, then the duplicates should fall into the same file.
After the hashing, I got 1000 small files, each of which contains 1 million
numbers at most
, right? I'm not sure about this, I simply do it 1 billion / 1000 = 1 million
.
Then for each file, build a hash table to store each number and a flag
representing its occurrence.
I guess, it will take 5 B
to represent the number, 4 B
for the lower 8 digits
and 1 B
for the upper 3 digits
; and actually 1 bit
will suffice the flag
, because I just need to find out whether duplicate exists, only how many times. But how can I apply the 1 bit
flag to each number? I'm stumbled, so I choose bool
to be the flag, 1 B
is taken.
So finally, each number in the hash table will take 5B<for number> + 1B<for flag> + 4B<for the next-pointer> = 10B
, then each file will take 10M
for the hash table.
That's my stupid solution, Please give me a better one.
Thanks.
FOLLOW UP:
If there are
no duplicates
in these 1 billion phone numbers, given one phone number, how to find out the given oneis or is not in
these 1 billion numbers? Use as few memory as possible.
I came up with 2 solutions,
The phone number can be represented using 5B as I said above, scan through the file, read one number a time, and xor the given number with the one read from the file
, if the result is 0
, then the given one is in the file, it'll take O(n)
time, right?
Partition
these numbers into 2 small files
according to the leading bit
, which means, those numbers with a leading 1-bit
go to a file, leading 0-bit
go to another file, meanwhile count how many numbers in each file, if the given number fall into the 1-bit file and the 1-bit file's count
is not full
, then again partition
the 1-bit file according to the secondary leading-bit
, and check the given number recursively; if the 1-bit file is full
, then the given number gotta be in the file, it'll take O(logn)
time, right?
Absolutely. There are two ways to do this depending on your needs. If both devices already have their own phone number and data plan then you can access your primary number from either phone any time through the DIGITS app.
Fastest solution (also in terms of programmer overhead :)
# Generate some 'phones'
yes 1 | perl -wne 'chomp; ++$a; print $_."$a\n";' > phones.txt
# Split phones.txt in 10MB chunks
split -C 10000000 phones.txt
# Sort each 10MB chunk with 10MB of memory
for i in x??; do sort -S 10M $i > $i.srt; echo -ne "$i.srt\0" >> merge.txt; done
# Merge the shorted chunks with 10MB of memory
sort -S 10M --files0-from=merge.txt -m > sorted.txt
# See if there is any duplicates
test -z $(uniq -d merge.txt)
Check that the memory usage constraint is met with pmap $(pidof sort) for example:
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With