Thursday, February 16, 2012

Design The Algorithm for AutoComplete Feature of Google

Autocomplete is a program function that enables inputting the text (in editors, command line shells, browsers etc.) completing the text by its inputted part. Vasya is busy working on a new browser called 'BERowser'. He happens to be working on the autocomplete function in the address line at this very moment. A list consisting of n last visited by the user pages and the inputted part s are known. Your task is to complete s to make it an address of one of the pages from the list. You have to find the lexicographically smallest address having a prefix s


Input text- 
next

select output from 
nextelement       ---- Answer
nextpermutation






1 comment :

Anonymous said...

tries vud do....bt space complexity is high...
if the words in dictionary are limited den suffix array and trees cud be used.....
howevr i i'm unable to code the implementation of suffix array...vud b oblidged if u help out