Most efficient way to store thousand telephone numbers

This is a google interview question:

There are around thousand phone numbers to be stored each having 10 digits. You can assume first 5 digits of each to be same across thousand numbers. You have to perform the following operations: a. Search if a given number exists. b. Print all the number

What is the most efficient space saving way to do this ?

I answered hash table and later huffman coding but my interviewer said I was not going in right direction. Please help me here.

Could using a suffix trie help?

Ideally 1000 numbers storing takes 4 bytes per number so in all it would take 4000 bytes to store 1000 number. Quantitatively, I wish to reduce the storage to < 4000 bytes, this is what my interviewer explained to me.

Solution 1:

In what follows, I treat the numbers as integer variables (as opposed to strings):

1. Sort the numbers.
2. Split each number into the first five digits and the last five digits.
3. The first five digits are the same across numbers, so store them just once. This will require 17 bits of storage.
4. Store the final five digits of each number individually. This will require 17 bits per number.

To recap: the first 17 bits are the common prefix, the subsequent 1000 groups of 17 bits are the last five digits of each number stored in ascending order.

In total we're looking at 2128 bytes for the 1000 numbers, or 17.017 bits per 10-digit telephone number.

Search is O(log n) (binary search) and full enumeration is O(n).

Solution 2:

Here's an improvement to aix's answer. Consider using three "layers" for the data structure: the first is a constant for the first five digits (17 bits); so from here on, each phone number has only the remaining five digits left. We view these remaining five digits as 17-bit binary integers and store k of those bits using one method and 17 - k = m with a different method, determining k at the end to minimize the required space.

We first sort the phone numbers (all reduced to 5 decimal digits). Then we count how many phone numbers there are for which the binary number consisting of the first m bits is all 0, for how many phone numbers the first m bits are at most 0...01, for how many phone numbers the first m bits are at most 0...10, etcetera, up to the count of phone numbers for which the first m bits are 1...11 - this last count is 1000(decimal). There are 2^m such counts and each count is at most 1000. If we omit the last one (because we know it is 1000 anyway), we can store all of these numbers in a contiguous block of (2^m - 1) * 10 bits. (10 bits is enough for storing a number less than 1024.)

The last k bits of all (reduced) phone numbers are stored contiguously in memory; so if k is, say, 7, then the first 7 bits of this block of memory (bits 0 thru 6) correspond to the last 7 bits of the first (reduced) phone number, bits 7 thru 13 correspond to the last 7 bits of the second (reduced) phone number, etcetera. This requires 1000 * k bits for a total of 17 + (2^(17 - k) - 1) * 10 + 1000 * k, which attains its minimum 11287 for k = 10. So we can store all phone numbers in ceil(11287/8)=1411 bytes.

Additional space can be saved by observing that none of our numbers can start with e.g. 1111111(binary), because the lowest number that starts with that is 130048 and we have only five decimal digits. This allows us to shave a few entries off the first block of memory: instead of 2^m - 1 counts, we need only ceil(99999/2^k). That means the formula becomes

17 + ceil(99999/2^k) * 10 + 1000 * k

which amazingly enough attains its minimum 10997 for both k = 9 and k = 10, or ceil(10997/8) = 1375 bytes.

If we want to know whether a certain phone number is in our set, we first check if the first five binary digits match the five digits we have stored. Then we split the remaining five digits into its top m=7 bits (which is, say, the m-bit number M) and its lower k=10 bits (the number K). We now find the number a[M-1] of reduced phone numbers for which the first m digits are at most M - 1, and the number a[M] of reduced phone numbers for which the first m digits are at most M, both from the first block of bits. We now check between the a[M-1]th and a[M]th sequence of k bits in the second block of memory to see if we find K; in the worst case there are 1000 such sequences, so if we use binary search we can finish in O(log 1000) operations.

Pseudocode for printing all 1000 numbers follows, where I access the K'th k-bit entry of the first block of memory as a[K] and the M'th m-bit entry of the second block of memory as b[M] (both of these would require a few bit operations that are tedious to write out). The first five digits are in the number c.

i := 0;
for K from 0 to ceil(99999 / 2^k) do
  while i < a[K] do
    print(c * 10^5 + K * 2^k + b[i]);
    i := i + 1;
  end do;
end do;

Maybe something goes wrong with the boundary case for K = ceil(99999/2^k), but that's easy enough to fix.

Finally, from an entropy point of view, it is not possible to store a subset of 10^3 positive integers all less than 10^5 in fewer than ceil(log[2](binomial(10^5, 10^3))) = 8073. Including the 17 we need for the first 5 digits, there is still a gap of 10997 - 8090 = 2907 bits. It's an interesting challenge to see if there are better solutions where you can still access the numbers relatively efficiently!

Solution 3:

http://en.wikipedia.org/wiki/Acyclic_deterministic_finite_automaton

I once had an interview where they asked about data structures. I forgot "Array".