Tom
BAN USER- 0of 0 votes
AnswersYou have more than 3 million entries of phone numbers. You have to create a phone book just like the one we have on the new phones these days. You type the name, and the numbers that match the letters you typed shows up on your phone.
- Tom
For e.g: When you type 'K' all numbers under K appear,then you say "i"...all numbers under "Ki" appear..so on and so forth.
How will you design/architecture this type of search? Discuss data structures you would use whats the worst case for your design?| Report Duplicate | Flag | PURGE
Delve Networks Software Engineer / Developer Data Structures Ideas Object Oriented Design
You can keep a boolean array range from 0-100 (call it prime). Make all entries in the array as true.
We know that 0,1 are not prime. So prime[0] and prime[1] = false.
Now starting from 2 - cancel out all factors of 2,which means prime[4],prime[6] and so on make it as (false). Once thats done, go to the next entry in prime which is true;i.e 3.
boolean[] primeArray = new boolean[n + 1];
Arrays.fill(primeArray, true);
int range = (int)Math.sqrt(n);
primeArray[0] = false;
primeArray[1] = false;
for (int count = 2; count <= range; count++)
{
if (primeArray[count])
{
for (int countFactors = count*count; countFactors<=n; countFactors = countFactors + count)
primeArray[countFactors] = false;
}
}
This can be done using a hashtable. For each number, check if (value - array[i]) exists in the hash, if not then add array[i] in the hashtable. Keep going through the array, until you find the pair which adds up to the value given. For example: if value = 20 and array is: 2, 15, 8, 10, 18. Start from 2, (20-2)=18, Check is 18 exists in the hashtable, if no, then put(2) into the hashtable. Go to 15, then 8, then 10 and then finally when you come to 18, check (20-18) = 2 exists, it does,return 2 and 18. This can be done in O(n) with extra storage.
- Tom July 10, 2009
Will this work for FOOOPARFOO?
- Tom June 06, 2010