98

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.

7
  • 28
    I would answer that using a normal database you can store them as text, even thousands/millions, and lookup operations will still be very fast. I will advise against doing "clever" things since the whole system will have to be redone should they want in the future to support international numbers, or if telephone numbers that begin with a "0" start to appear, or if the government decides to change the phone number format, and so on. Oct 7, 2011 at 14:29
  • 1
    @AndreasBonini: I would probably give that answer, unless I was interviewing at a company like Google or Facebook, were out of the box solutions just do not cut it. Although postgres for example has tries, too, I would not be sure that these cut the data throughput google needs to take of.
    – LiKao
    Oct 8, 2011 at 15:32
  • 1
    @LiKao: keep in mind that the OP specifically stated "around a thousand numbers" Oct 8, 2011 at 15:48
  • @AndreasBonini: True, might have also been a test, that the interviewee knows to interpret such constraints correctly and choose the best solution according to this.
    – LiKao
    Oct 8, 2011 at 16:08
  • 4
    "efficient" in this question really needs to be defined - efficient in which ways? space, time, both?
    – matt b
    Oct 11, 2011 at 17:05

13 Answers 13

44

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

8
  • Uhm, where's the space complexity?
    – aioobe
    Oct 7, 2011 at 10:08
  • Too much time to build (O(log(n)*nk) (k is the length) for the sorting, compared to O(nk) for building a trie). Also space is far from optimal, because longer common prefixes are stored individually. Search time is also not optimal. For string data like this it is easy to forget the length of the numbers, which dominates the search. I.e. binary search is O(log(n)*k), whereas a trie only needs O(k). You can reduce theses expressions, when k is constant, but this is to show a general problem when reasoning about datastructures storing strings.
    – LiKao
    Oct 7, 2011 at 10:33
  • @LiKao: Who said anything about strings? I am dealing exclusively with integer variables so k is irrelevant.
    – NPE
    Oct 7, 2011 at 10:36
  • 1
    Ok, I misread the answer then. Still, common parts are not stored together, so the point about space efficiency remains. For 1000 of 5 digit numbers, there will be a fair amount of common prefixes, so reducing these will help a lot. Also in case of numbers we have O(log(n)) versus O(k) for strings, which is still faster.
    – LiKao
    Oct 7, 2011 at 11:42
  • 1
    @Geek: 1001 groups of 17 bits is 17017 bits or 2128 bytes (with some change).
    – NPE
    May 12, 2015 at 11:18
38

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!

5
  • 4
    The datastructure you are describing here actually only is a very efficient version of trie, that only uses as little as needed for the indexing and only two levels. In practice it would be nice to see if this can beat a trie with more levels, but I think this depends a lot on the distribution of the numbers (In real live phone numbers are not fully random, but only almost).
    – LiKao
    Oct 8, 2011 at 9:59
  • Hi Erik, since you said you'd be interested to see other alternatives, check out my solution. It solves it in 8,580 bits, which is just 490 bits off the theoretical minimum. It's a bit inefficient to look up individual numbers, but the storage is very compact.
    – Briguy37
    Oct 9, 2011 at 17:37
  • 1
    I would suppose that a sane interviewer would prefer the answer "a trie" instead of "a complex custom made database". If you want to show of your 133t hacking skills, you can add - "it would be possible to make a specific tree algorithm for this special case, if neccesary."
    – KarlP
    Oct 21, 2011 at 8:14
  • Hi, Can you please explain how 5 digits take 17 bits to be stored? Jan 11, 2016 at 4:30
  • @tushar Five digits encode a number between 00000 and 99999 inclusive. Represent that number in binary. 2^17=131072, so 17 bits suffice for that but 16 don't.
    – Erik P.
    Jan 11, 2016 at 4:35
22

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

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

2
  • 1
    +1 that's definitely the way to go. I learned this one under another name, Library tree or lexical search tree or something when I was a student (if someone remembers that old name please do tell).
    – Valmond
    Oct 7, 2011 at 16:34
  • 6
    This doesn't meet the 4000 byte requirement. For pointer storage alone, the worst case scenario is that you'd need 1 pointer for the 1-4th leaves to the next level, 10 pointers for the 5th, 100 for the 6th, and 1000 for the 7th, 8th, and 9th levels, which brings our pointer total to 3114. That gives at least 3114 distinct memory locations needed for pointers to point at, which means you'd need at least 12 bits for each pointer. 12*3114 = 37368 bits = 4671 bytes > 4000 bytes, and that doesn't even figure in how you represent the value of each leaf!
    – Briguy37
    Oct 7, 2011 at 18:48
15

I'd probably consider using some compressed version of a Trie (possibly a DAWG as suggested by @Misha).

That would automagically take advantage of the fact that they all have a common prefix.

Searching will be performed in constant time, and printing will be performed in linear time.

8
  • The question is about the most space-efficient way to store the data. Would you mind providing some estimate of how much space this method would require for the 1000 phone numbers? Thanks.
    – NPE
    Oct 7, 2011 at 11:03
  • Space for the trie is at most O(n*k) where n is the number of strings and k is the length of each string. Taking into account that you do not need 8 bit characters to represent numbers, I would suggest storing 4 hexadecimal indexes hexadeximal and one for the remaining bit. This way you need at maximum 17 bits per number. Because you will in all cases have clashes on all levels with this coding you can actually get below this. Expecting that we store 1000 numbers, we can already save a total of 250 bits for the clashes at first level. Best test the correct coding on example data.
    – LiKao
    Oct 7, 2011 at 14:37
  • @LiKao, right, and by noting that, for instance, 1000 numbers can't have more than 100 different last two digits, the trie could be collapsed significantly at the last levels.
    – aioobe
    Oct 7, 2011 at 14:55
  • @aioobe: The leaves could be collapsed at the last level because there are no children. However, the leaves at the second to last level need 2^10=1024 states (each last digit could be on or off), so it is not reducible in this case since there are only 1000 numbers. This means the number of worst-case pointers stays at 3114 (see my comment on Misha's answer) while the leaves needed goes to 5+10+100+1000+1000+10=2125, which does not change the needed 12 bytes for each pointer. Thus, this still puts a trie solution at 4671 bytes considering only pointers alone.
    – Briguy37
    Oct 7, 2011 at 19:55
  • @Briguy37, not sure I get your "each last digit could be on or off" argument. All numbers are 10 digits long, right?
    – aioobe
    Oct 7, 2011 at 20:01
15

I've heard of this problem before (but without first-5-digits-are-same assumption), and the simplest way to do it was Rice Coding:

1) Since the order does not matter we can sort them, and save just differences between consecutive values. In our case the average differences would be 100.000 / 1000 = 100

2) Encode the differences using Rice codes (base 128 or 64) or even Golomb codes (base 100).

EDIT : An estimation for Rice coding with base 128 (not because it would give best results, but because it's easier to compute):

We'll save first value as-is (32 bits).
The rest of 999 values are differences (we expect them to be small, 100 on average) will contain:

unary value value / 128 (variable number of bits + 1 bit as terminator)
binary value for value % 128 (7 bits)

We have to estimate somehow the limits (let's call it VBL) for number of variable bits:
lower limit: consider we are lucky, and no difference is larger than our base (128 in this case). this would mean give 0 additional bits.
high limit: since all differences smaller than base will be encoded in binary part of number, the maximum number we would need to encode in unary is 100000/128 = 781.25 (even less, because we don't expect most of differences to be zero).

So, the result is 32 + 999 * (1 + 7) + variable(0..782) bits = 1003 + variable(0..98) bytes.

7
  • Can you give more details on the way you are encoding and about the final size calculation. 1101 bytes or 8808 bits seems very very close to the theoretical limit of 8091 bits, so I am very surprised, that it is possible to achieve something like this in practice.
    – LiKao
    Oct 8, 2011 at 10:01
  • Would it not be 32 + 999 * (1 + 7 + variable(0..782)) bits? Each of the 999 numbers needs a representation of value / 128. Oct 12, 2011 at 13:33
  • 1
    @Kirk: no, if all of them are in the range of 5 digits. This is because we would expect that sum all these differences (remember, we encode differences between consecutive values, not between the first and Nth value) would be below 100000 (even in the worst case scenario)
    – ruslik
    Oct 12, 2011 at 14:22
  • You need 34 bits instead of 32 bits to represent the first value (9,999,999,999 > 2^32 = 4,294,967,296). Also, the maximum difference would be 00000 to 99001 since the numbers are unique, which would add 774 1's instead of 782 for base 128. Thus your range for storage of 1,000 numbers for base 128 is 8026-8800 bits or 1004-1100 bytes. 64-bit base gives better storage, with ranges from 879-1072 bytes.
    – Briguy37
    Oct 12, 2011 at 16:11
  • 1
    @raisercostin: this is what Kirk asked. In your example, by encoding once the 20k difference between the first two values, only 80k of maximum range will be possible to occure in the future. This will use up 20k/128 = 156 unary bits out of maximum 782 (that correspond to 100k)
    – ruslik
    Oct 14, 2011 at 14:20
7

This is a well-know problem from Bentley's Programming Pearls.

Solution: Strip the first five digits from the numbers as they are the same for every number. Then use bitwise-operations to represent the remaining 9999 possible value. You will only need 2^17 Bits to represent the numbers. Each Bit represents a number. If the bit is set, the number is in the telephon book.

To print all numbers, simply print all the numbers where the bit is set concatened with the prefix. To search for a given number do the necessary bit arithmetic to check for bitwise representation of the number.

You can search for a number in O(1) and the space efficiency is maximal due to the bit represenatation.

HTH Chris.

4
  • 3
    This would be a good approach for a dense set of numbers. Unfortunately, here the set is very sparse: there are only 1,000 numbers out of possible 100,000. This approach would therefore on average require 100 bits per number. See my answer for an alternative that only needs ~17 bits.
    – NPE
    Oct 7, 2011 at 10:40
  • 1
    Wouldn't the time it takes to print all numbers be proportional to 100,000 instead of 1,000?
    – aioobe
    Oct 7, 2011 at 12:47
  • Combining the two ideas you basically get the trie immediately. Using an bitvector with 100,000 entries is way overallocating and takes to much space. However O(log(n)) lookup is often too slow (depends on the numbers of queries here). So using a hierachie of bit sets for indexing you will store at maximum 17 bits per number, while still getting the O(1) lookup. This is how the trie works. Also time for printing is in O(n) for the trie, which it inherits from the sorted case.
    – LiKao
    Oct 7, 2011 at 14:28
  • This is not "the most efficient space saving way to do this". Oct 7, 2011 at 16:40
5

Fixed storage of 1073 bytes for 1,000 numbers:

The basic format of this storage method is to store the first 5 digits, a count for each group, and the offset for each number in each group.

Prefix:
Our 5-digit prefix takes up the first 17 bits.

Grouping:
Next, we need to figure out a good sized grouping for numbers. Let's try have about 1 number per group. Since we know there are about 1000 numbers to store, we divide 99,999 into about 1000 parts. If we chose the group size as 100, there would be wasted bits, so let's try a group size of 128, which can be represented with 7 bits. This gives us 782 groups to work with.

Counts:
Next, for each of the 782 groups, we need to store the count of entries in each group. A 7-bit count for each group would yield 7*782=5,474 bits, which is very inefficient because the average number represented is about 1 because of how we chose our groups.

Thus, instead we have variable sized counts with leading 1's for each number in a group followed by a 0. Thus, if we had x numbers in a group, we'd have x 1's followed by a 0 to represent the count. For example, if we had 5 numbers in a group the count would be represented by 111110. With this method, if there are 1,000 numbers we end up with 1000 1's and 782 0's for a total of 1000 + 782 = 1,782 bits for the counts.

Offset:
Last, the format of each number will just be the 7-bit offset for each group. For example, if 00000 and 00001 are the only numbers in the 0-127 group, the bits for that group would be 110 0000000 0000001. Assuming 1,000 numbers, there will be 7,000 bits for the offsets.

Thus our final count assuming 1,000 numbers is as follows:

17 (prefix) + 1,782 (counts) + 7,000 (offsets) = 8,799 bits = 1100 bytes

Now, let's check if our group-size selection by rounding up to 128 bits was the best choice for group size. Choosing x as the number of bits to represent each group, the formula for the size is:

Size in bits = 17 (prefix) + 1,000 + 99,999/2^x + x * 1,000

Minimizing this equation for integer values of x gives x=6, which yields 8,580 bits = 1,073 bytes. Thus, our ideal storage is as follows:

  • Group size: 2^6 = 64
  • Number of groups: 1,562
  • Total storage:

    1017 (prefix plus 1's) + 1563 (0's in count) + 6*1000 (offsets) = 8,580 bits = 1,073 bytes

1

Taking this as a purely theoretical problem and leaving implementation asside, the single most efficient way is to just index all possible sets of 10000 last digits in a gigantic indexing table. Assuming you have exactely 1000 numbers, you would need a little more than 8000 bits to uniquely identify the current set. There is no bigger compression possible, because then you would have two sets which are identified with the same state.

Problems with this is, that you would have to represent each of the 2^8000 sets in your program as a lut, and not even google would be remotely capable of this.

Lookup would be O(1), printing all number O(n). Insertion would be O(2^8000) which in theory is O(1), but in practice is unusable.

In an interview I would only give this answer, if I were sure, that the company is looking for someone who is able to think out of the box a lot. Otherwise this might make you look like a theorist with no real world concerns.

EDIT: Ok, here is one "implementation".

Steps to constructe the implementation:

  1. Take a constant array of size 100 000*(1000 choose 100 000) bits. Yes, I am aware of the fact that this array will need more space than atoms in the universe by several magnitudes.
  2. Seperate this large array into chunks of 100 000 each.
  3. In each chunk store a bit array for one specific combination of last five digits.

This is not the program, but a kind of meta programm, that will construct a gigantic LUT that can now be used in a programm. Constant stuff of the programm is normally not counted when calculating space efficiency, so we do not care about this array, when doing our final calculations.

Here is how to use this LUT:

  1. When someone gives you 1000 numbers, you store the first five digits seperately.
  2. Find out which of the chunks of your array matches this set.
  3. Store the number of the set in a single 8074 bit number (call this c).

This means for storage we only need 8091 bits, which we have proven here to be the optimal encoding. Finding the correct chunk however takes O(100 000*(100 000 choose 1000)), which according to math rules is O(1), but in practice will always take longer than the time of the universe.

Lookup is simple though:

  1. strip of first five digits (remaining number will be called n').
  2. test if they match
  3. Calculate i=c*100000+n'
  4. Check if the bit at i in the LUT is set to one

Printing all numbers is simple also (and takes O(100000)=O(1) actually, because you always have to check all bits of the current chunk, so I miscalculated this above).

I would not call this a "implementation", because of the blatant disregard of the limitations (size of the universe and time this universe has lived or this earth will exist). However in theory this is the optimal solution. For smaller problems, this actually can be done, and sometimes will be done. For example sorting networks are a example for this way of coding, and can be used as a final step in recursive sorting algorithms, to get a big speedup.

2
  • 1
    What is the most efficient space saving way to do this ?
    – Sven
    Oct 7, 2011 at 15:44
  • 1
    When doing calculations of run time space, this can easily be proven to be the most efficient space saving way, because you enumerate any possible state of the system with one number only. There cannot be any smaller encoding for this problem. The trick for this answer is, that the programm size is almost never considered, when doing the calculations (try to find any answer that takes this into account, and you will see what I mean). So for any problem which has a size bound, you can alway enumerate all states, to get the most space saving way to handle it.
    – LiKao
    Oct 8, 2011 at 9:28
1

This is equivalent to storing one thousand non-negative integers each less than 100,000. We can use something like arithmetic encoding to do this.

Ultimately, the numbers will be stored in a sorted list. I note that the expected difference between adjacent numbers in the list is 100,000/1000 = 100, which can be represented in 7 bits. There will also be many cases where more than 7 bits are necessary. A simple way to represent these less common cases is to adopt the utf-8 scheme where one byte represents a 7-bit integer unless the first bit is set, in which case the next byte is read to produce a 14-bit integer, unless its first bit is set, in which case the next byte is read to represent a 21-bit integer.

So at least half of the differences between consecutive integers may be represented with one byte, and almost all the rest require two bytes. A few numbers, separated by bigger differences than 16,384, will require three bytes, but there cannot be more than 61 of these. The average storage then will be about 12 bits per number, or a bit less, or at most 1500 bytes.

The downside to this approach is that checking the existence of a number is now O(n). However, no time complexity requirement was specified.

After writing, I noticed ruslik already suggested the difference method above, the only difference is the encoding scheme. Mine is likely simpler but less efficient.

1

Just to ask quickly any reason that we would not want to change the numbers into a base 36. It may not save as much space but it would for sure save time on the search since u will be looking at a lot less then 10digts. Or I would split them into files depending on each group. so i would name a file (111)-222.txt and then i would only store numbers that fit in to that group in there and then have them seearchable in numeric order this way i can always chack to see if the file exits. before i run a biger search. or to be correct i would run to binary searchs one for the file to see if it exits. and another bonary search on the contents of the file

0

Why not keep it simple? Use an array of structs.

So we can save the first 5 digits as a constant, so forget those for now.

65535 is the most that can be stored in a 16-bit number, and the max number we can have is 99999, which fits withing the 17th bit number with a max of 131071.

Using 32-bit data types is a wast because we only need 1 bit of that extra 16-bits...therefore, we can define a structure that has a boolean (or character) and a 16-bit number..

Assuming C/C++

typedef struct _number {

    uint16_t number;
    bool overflow;
}Number;

This struct only takes up 3-bytes, and we need an array of 1000, so 3000 bytes total. We have reduced the total space by 25%!

As far as storing the numbers, we can do simple bitwise math

overflow = (number5digits & 0x10000) >> 4;
number = number5digits & 0x1111;

And the inverse

//Something like this should work
number5digits = number | (overflow << 4);

To print all of them, we can use a simple loop over the array. Retrieving a specific number happens in constant time of course, since it is an array.

for(int i=0;i<1000;i++) cout << const5digits << number5digits << endl;

To search for a number, we would want a sorted array. So when the numbers are saved, sort the array (I would choose a merge sort personally, O(nlogn)). Now to search, I would go a merge sort approach. Split the array, and see which one our number falls between. Then call the function on only that array. Recursively do this until you have a match and return the index, otherwise, it does not exist and print an error code. This search would be quite quick, and worst case is still better than O(nlogn) since it will absolutely execute in less time than the merge sort (only recursing 1 side of the split each time, instead of both sides :)), which is O(nlogn).

0

My solution: best case 7.025 bits/number, worst case 14.193 bits/number, rough average 8.551 bits/number. Stream-encoded, no random access.

Even before reading ruslik’s answer, I immediately thought of encoding the difference between each number, since it will be small and should be relatively consistent, but the solution must also be able to accommodate the worst case scenario. We have a space of 100000 numbers that contain only 1000 numbers. In a perfectly uniform phone book, each number would be greater than the previous number by 100:

55555-12345
55555-12445
55555-12545

If that was the case, it would require zero storage to encode the differences between numbers, since it’s a known constant. Unfortunately, numbers may vary from the ideal steps of 100. I would encode the difference from the ideal increment of 100, so that if two adjacent numbers differ by 103, I would encode the number 3 and if two adjacent numbers differ by 92, I would encode -8. I call the delta from an ideal increment of 100 the “variance”.

The variance can range from -99 (i.e. two consecutive numbers) to 99000 (the entire phonebook consists of numbers 00000…00999 and an additional furthest-away number 99999), which is a range of 99100 possible values.

I’d aim to allocate a minimal storage to encode the most common differences and expand the storage if I encounter bigger differences (like ProtoBuf’s varint). I’ll use chunks of seven bits, six for storage and an additional flag bit at the end to indicate that this variance is stored with an additional chunk after the current one, up to a maximum of three chunks (which will provide a maximum of 3 * 6 = 18 bits of storage, which are 262144 possible value, more than the number of possible variances (99100). Each additional chunk that follows a raised flag has bits of a higher significance, so the first chunk always has bits 0-5, the optional second chunks has bits 6-11, and the optional third chunk has bits 12-17.

A single chunk provides six bits of storage which can accommodate 64 values. I’d like to map the 64 smallest variances to fit in that single chunk (i.e. variances of -32 to +31) so I’ll use ProtoBuf ZigZag encoding, up to the variances of -99 to +98 (since there’s no need for a negative variance beyond -99), at which point I’ll switch to regular encoding, offset by 98:  

 Variance  |  Encoded Value
-----------+----------------
    0      |       0
   -1      |       1
    1      |       2
   -2      |       3
    2      |       4
   -3      |       5
    3      |       6
   ...     |      ...
  -31      |      61
   31      |      62
  -32      |      63
-----------|--------------- 6 bits
   32      |      64
  -33      |      65
   33      |      66
   ...     |      ...
  -98      |      195
   98      |      196
  -99      |      197
-----------|--------------- End of ZigZag
   100     |      198
   101     |      199
   ...     |      ...
  3996     |     4094
  3997     |     4095
-----------|--------------- 12 bits
  3998     |     4096
  3999     |     4097
   ...     |      ...
 262045    |    262143
-----------|--------------- 18 bits

Some examples of how variances would be encoded as bits, including the flag to indicate an additional chunk:

 Variance  |  Encoded Bits
-----------+----------------
     0     |  000000 0
     5     |  001010 0
    -8     |  001111 0
   -32     |  111111 0
    32     |  000000 1  000001 0
   -99     |  000101 1  000011 0
   177     |  010011 1  000100 0
 14444     |  001110 1  100011 1  000011 0

So the first three numbers of a sample phone book would be encoded as a stream of bits as follows:

BIN 000101001011001000100110010000011001   000110 1     010110 1 00001 0
PH#           55555-12345                 55555-12448     55555-12491
POS                1                           2               3

Best case scenario, the phone book is somewhat uniformly distributed and there are no two phone numbers that have a variance greater than 32, so it would use 7 bits per number plus 32 bits for the starting number for a total of 32 + 7*999 = 7025 bits.
A mixed scenario, where 800 phone numbers' variance fits within one chunk (800 * 7 = 5600), 180 numbers fit in two chunks each (180 * 2 * 7 = 2520) and 19 numbers fit in three chunks each (20 * 3 * 7 = 399), plus the initial 32 bits, totals 8551 bits.
Worst case scenario, 25 numbers fit in three chunks (25 * 3 * 7 = 525 bits) and the remaining 974 numbers fit in two chunks (974 * 2 * 7 = 13636 bits), plus 32 bits for the first number for a grand total of 14193 bits.

   Amount of encoded numbers   |
 1-chunk | 2-chunks | 3-chunks | Total bits
---------+----------+----------+------------
   999   |    0     |    0     |   7025
   800   |   180    |    19    |   8551
    0    |   974    |    25    |  14193

I can see four additional optimizations that can be performed to further reduce the space required:

  1. The third chunk doesn’t need the full seven bits, it can be just five bits and without a flag bit.
  2. There can be an initial pass of the numbers to calculate the best sizes for each chunk. Maybe for a certain phonebook, it would be optimal to have the first chunk have 5+1 bits, the second 7+1 and the third 5+1. That would further reduce the size to a minimum of 6*999 + 32 = 6026 bits, plus two sets of three bits to store the sizes of chunks 1 and 2 (chunk 3’s size is the remainder of the required 16 bits) for a total of 6032 bits!
  3. The same initial pass can calculate a better expected increment than the default 100. Maybe there's a phone book that starts from 55555-50000, and so it has half the number range so the expected increment should be 50. Or maybe there's a non-linear distribution (standard deviation perhaps) and some other optimal expected increment can be used. This would reduce the typical variance and might allow an even smaller first chunk to be used.
  4. Further analysis can be done in the first pass to allow the phone book to be partitioned, with each partition having its own expected increment and chunk size optimizations. This would allow for a smaller first chunk size for certain highly uniform parts of the phone book (reducing the number of bits consumed) and larger chunks sizes for non-uniform parts (reducing the number of bits wasted on continuation flags).
0

The real question is one of storing five-digit phone numbers.

The trick is that you'd need 17 bits to store the range of numbers from 0..99,999. But storing 17-bits on conventional 8-byte word boundaries is a hassle. That's why they are asking if you can do in less than 4k by not using 32-bit integers.

Question: are all number combinations possible?

Because of the nature of the telephone system, there may be fewer than 65k possible combinations. I will assume that yes because we are talking about the latter five positions in the phone number, as opposed to the area code or exchange prefixes.

Question: will this list be static or will it need to support updates?

If it is static, then when it comes time to populate the database, count the number of digits < 50,000 and the number of digits >= 50,000. Allocate two arrays of uint16 of appropriate length: one for the integers below 50,000 and one for the higher set. When storing integers in the higher array, subtract 50,000 and when reading integers from that array, add 50,000. Now you've stored your 1,000 integers in 2,000 8-byte words.

Building the phonebook will require two input traversals, but lookups should happen in half the time, on average, than they would with a single array. If lookup time were very important you could use more arrays for smaller ranges but I think at these sizes your performance bound would be pulling the arrays from memory and 2k will probably stash into CPU cache if not register space on anything you'd be using these days.

If it is dynamic, allocate one array of 1000 or so uint16, and add the numbers in sorted order. Set the first byte to 50,001, and set the second byte to an appropriate null value, like NULL or 65,000. When you store the numbers, store them in sorted order. If a number is below 50,001 then store it before the 50,001 marker. If a number is 50,001 or greater, store it after the 50,001 marker, but subtract 50,000 from the stored value.

Your array will look something like:

00001 = 00001
12345 = 12345
50001 = reserved
00001 = 50001
12345 = 62345
65000 = end-of-list

So, when you look up a number in the phonebook, you'll traverse the array and if you've hit the 50,001 value you start adding 50,000 to your array values.

This makes inserts very expensive, but lookups are easy, and you're not going to spend much more than 2k on storage.

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