if records are in millions, then we have to store in database, but I don't know what optimization we'll perform on queries.
dunno much about database optimisation
@TheLittleNaruto we can store numbers in binary tree nodes as well. That's log n search time. But millions of records won't be store in RAM, where tree's memory will reside
then files are last resort. We'll store numbers in files. Lets say all the numbers starting with 99 will be stored in one file. That'll provide sharding to our number dataset, which'll be in files. Now these files can be stored on disk as well.
next is searching, so searching for file is fairly easy. We can just have another dataset, which store all the addresses to files. So, we'll see what the number starts with, then get the address of that file in O(1). We'll open the file, here, all the numbers will be stored in sorted manner, where we can do binary search and find the name.
how about this @TheLittleNaruto
Total search complexity, log n Time complexity for insertion, log n. Same with deletion as well
and we can keep making files until system runs out of storage space, so its really upto how much money the interviewer has :P
I just designed an optimised and sharded database for you man. You can scale it vertically, as well as horizontally. You can even have multiple databases saving files, and then you can have even more storage space.
sometimes, if you listen carefully, you can hear my genius at work :P