Data Structure for Efficient Search

Problem Statement

Given one million 10 digit unique integers, design an efficient data structure which has lowest time complexity for searches. You are given ample amount of space and the time for building the data structure and populating it is not judged.

The only criteria is to offer efficient searches.

Thought Process for Efficient Search

The numbers are 10 digit unique integers and we need a data structure which can offer search in near constant time. The problem is similar to finding if a word exists in a dictionary. Its just that the Strings are replaced by the 10 digit numbers.

The dictionary problem can be solved using a Trie datastructure and it offers efficient search of words.

One efficient option is to store them in a 10-ary tree resembling the Trie data structure where each digit of a number is stored in a node, and if we can successfully travel from root to leaf spotting each digit of our number in the Trie, it is considered a successful search else it is considered a failure.

The maximum height of this tree would be 10 because all the numbers are 10 digit numbers, and the capacity of the tree would be 10 billion i.e. 1010.  But we only have one million numbers which means the tree is very much sparse and it is only filled up to 0.01%.

Searching any number in the Trie would take a maximum of 10 comparisons. Which is constant time operation O(1) compared to the input size, one million.

Efficient Search

For the sake of brevity, I present here a Trie which represents 4 digit numbers only. The following numbers are stored in the Trie

 5491, 5492, 5400, 5402, 5357, 6931, 6032, 6026

To trace a number we need to walk from the root to a leaf, at each level we make one comparison, hence, in this tree we make 4 comparisons to search any number. The diagram shows a search for 5400.

Source Code

Here is the node structure and the Trie data structure.

Conclusion

Most of the problems can be easily solved if we can understand the requirement clearly. Here, it seems that the requirement was just to have efficient searches. No matter how big the data structure was and how much time it took to build it.

Also, it is important that we cross think, Tries mostly are used to store words from a dictionary, but of course we can use it for this purpose as well.

For more fun filled questions! Stay connected and Stay subscribed.