CareerCup

I could think of this way split the number into 3-3-4 digits so that the btree has 3 levels.
In first level you have a single node containing 000-999 valuses and the corresponding pointers(1000 keys+1000 pointers)
In second level for every one value in the node of above level you have one more node containing totally(1000 nodes each with 1000keys+1000 pointers)

And continue the same in next level too..
Can anyone think of better solution.

@someone:
but the size grows exponentially, right?

Yes but it will grow if there are those many phone numbers size cannot be more than O(n)

I meant to say that first level node doesn't contain 1000 keys + 1000 pointers from the beginning.It will get populated as and when you store in it

say you have 805-xxx-xxxx
896-xxx-xxxx
these two numbers then the top level node contains 2 keys and two pointers.
What I said was the maximum possible each node can accommodate.
Then one more optimization is you could perform binary search with in a node to check the existence of a part of the phone number.