Given the standard North American phone number format: (Area Code) Exchange – Subscriber, the set of possible numbers is about 6 billion. However, efficiently breaking down the nodes into the sections listed above would yield less than 12000 distinct nodes that can be arranged in groupings to get all the possible numbers.
This seems like a problem already solved.
Would it done via a graph or tree?
Best Answer
A comment you placed on the question:
So it sounds like you intend to store all current valid phone numbers, in the range of (000) 000-0000 through (999) 999-9999. So the set of possible numbers is 10,000,000,000, or, 10 billion.
This number can immediately be reduced to less than 8 billion, since the first digit in an area code cannot be a 0 or 1, area code cannot end in "11", and 555 numbers are reserved, as well as a few other rules.
Since only a maximum of 8 billion are available, and you mention storing 5-6 billion, I propose the much more space-efficient storage of the 2-3 billion unused numbers.
To generate a list of valid numbers, you would then numerically loop through all combinations, and skip numbers in the list of invalid numbers. Or, simply check to see that a number is not in the store invalid numbers, to know if it is valid.
A Trie tree or a Radix tree are most likely going to be the most space efficient while still having fast lookup/insert/remove speeds.