algorithm - Search a string as you type the character -

i have contacts stored in mobile. lets contacts are

ram  hello  hi  feat  eat  @ 

when type letter 'a' should matching contacts "ram, feat, eat, at".

now type 1 more letter t. total string "at" program should reuse results of previous search "a". should return me "feat, eat, at"

design , develop program this.

this interview question @ samsung mobile development

i tried solving trie data structures. not solution reusing searched string results. tried solution dictionary data structure, solution has same disadvantage trie.

question how search contacts each letter typed reusing search results of earlier searched string? data structure , algorithm should used efficiently solving problem.

i not asking program. programming language immaterial me.

state machine appears solution. have suggestion?

solution should fast enough million contacts.

it kind of depends on how many items you're searching. if it's relatively small list, can string.contains check on everything. when user types "a", search entire list:

for each contact in contacts     if contact.name.contains("a")         add contact results 

then user types "t", , sequentially search previous returned results:

for each contact in results     if contact.name.contains("at")         add contact new search results 

things more interesting if list of contacts huge, number of contacts you'd have in phone (a thousand lot!), going work well.

if interviewer said, "use results previous search new search," suspect answer looking for. take longer create new suffix tree sequentially search previous result set.

you optimize little bit storing position of substring along contact have next time around check see if next character expected, doing complicates algorithm bit (you have treat first search special case, , have explicitly check string lengths, etc.), , unlikely provide benefit after first few characters because size of list searched pretty small. pure sequential search contains check going plenty fast. users wouldn't notice few microseconds you'd save optimization.

update after edit question

if want million contacts, sequential search might not best way go @ start. although i'd still give try. "fast enough million contacts" raises question of "fast enough" means. how long take search 1 million contacts existence of single letter? how long user willing wait? remember have show 1 page of contacts before user takes action. , can before user presses second key. if have background thread doing search while foreground thread handles input , writing first page of matched strings display.

anyway, speed initial search creating bigram index. is, each bigram (sequence of 2 characters), build list of names contain bigram. you'll want create list of strings each single character. so, given list of names, you'd have:

r - ram - ram, feat, eat, m - ram h - hello, hi ... ra - ram - ram ... @ - feat, eat, @ ... etc. 

i think idea.

that bigram index gets stored in dictionary or hash map. there 325 possible bigrams in english language, , of course 26 letters, @ dictionary going have 351 entries.

so have instant lookup of 1- , 2-character names. how you?

an analysis of project gutenberg text shows common bigram in english language occurs 3.8% of time. realize names won't share distribution, that's pretty rough number. after first 2 characters typed, you'll working less 5% of total names in list. 5 percent of million 50,000. 50,000 names, can start using sequential search algorithm described originally.

the cost of new structure isn't bad, although it's expensive enough i'd try simple sequential search first, anyway. going cost 2 million references names, in worst case. reduce million references if build 2-level trie rather dictionary. take slightly longer lookup , display one-character search results, not enough noticeable user.

this structure easy update. add name, go through string , make entries appropriate characters , bigrams. remove name, go through name extracting bigrams, , remove name appropriate lists in bigram index.