CareerCup

binary search like tree in dictionary order

A hash table since search is fastest O(1)

radix tree. O(1) time.

Why do you need store and search a number, all you need is whether a number exists or not, why don't we simply set a bit for a number, you can later check whether that bit is set or not.. It will be O(1), save lot of space.. :-)

The proper response is to ask for more information about the input and search patterns.

What is the ratio of numbers to searches? How big is the data set going to get?

If we assume we will get more input numbers then searches (we are online, so the data keeps coming), and that we can't throw latency out the window (again, online) for maximum data sets smaller then memory, a balanced tree might be best. We get consistent insertions. A red-black tree is usually used when insertions > searches. While O(1) for a hash map sounds great, if they numbers keep coming we will keep hitting the rehash limit, which will give you big latency spikes for insertion O(N) vs O(logN) worst case insertion.

If we expect to surpass memory then a B/B+-tree starts to be more appropriate. Or a B/B+-tree on hash(input) if we want to spread out the load at the cost of breaking locality/sortedness.