“When the programmer faced the problem, all toll-free phone numbers in the US had the 800 area code. Toll-free codes now include 800, 877, 888, and the list is growing. (a) How would you sort all of the toll-free numbers using only a megabyte? (b) How can you store a set of toll-free numbers to allow very rapid lookup to determine whether a given toll-free number is available or already taken?”
Both of these were fairly straightforward, unless I really missed the point here. I didn’t bother doing (b), because if you assume that lookups will be online, and that the megabyte limit doesn’t hold (it’s not obvious from the question whether it does or not), then you can simply map each area code to a bitvector of the taken 7-digit numbers in that area code. Lookups in the table are O(1), and looking up a number within an area code using the bitvector is O(1).
(a) was more tedious than difficult. I assume that the set of possible area codes are accessible from a function within the system somewhere, and I do two passes of the file for each area code. In the first pass, I select all phone numbers in the bottom range of the given area code (000-0000 to 499-9999) and track those in the bitvector, printing them when I’m done. The second pass sorts 500-0000 to 999-9999 in essentially the same way. Since only 5 million bits are used at any one time, the program requires about 630K of space for the bitvector, which is well within the limit.
Of all the things to mess up, I ran into a neato little problem when trying to read 10-digit numbers in from a file. This is one of the first times that I can remember that my old Java-fu has tripped me up. I didn’t realize that a long isn’t quite as ‘long’ as it sounds, so I was getting some nasty overflow. Specifically, long and int are exactly the same on my platform (g++/darwin). So, unsigned long will give you max 2**32 = 429 496 7296, which is less than half the possible 10-digit phone numbers.
Undaunted, I switched to long longs, only to hit the same problem when using ifstream to scan the numbers from the file, or stringstream to parse each number individually. Mysteriously, cerr and cout were all able to emit long longs to the terminal without any problem.
It didn’t take me very much reading to discover that C++ compilers in general aren’t required to support 64-bit ints, and so the library support for them has the potential to be a bit flaky. It’s possible that I was just doing something really stupid in my stream code in the C++ version, but when I switched to fscanf using the %ll format flag, things worked just fine. Exciting stuff, here. But, at least I learned something! I love acquiring esoteric knowledge…
Solution can be found here: morecodes.cc
With highlighting: morecodes.cc
Comments (0)