Pergunta de entrevista da empresa Google

Design a web search engine that searches web locations for anagrams of a given string.

Resposta da entrevista

Sigiloso

20 de mai. de 2010

Some books suggests tries as data structure for search engines to store inverted indexes. The trie store the words and at the end of the word there is a list of documents which contain that word. If I would do a search engine for anagrams, when I index the document I would not store the words as they are, but in lexicographic order (the word "bamboo" will be "abbmoo"). When performing a search I will not look for the query but for its lexicographic order version.

2