Amazon Interview Question
Country: India
By "Window search", did you take the meaning to be the search feature that searches your files on Windows? I'm somehow skeptical that something like that would use map reduce.
Assuming you are saying "window search" to be say the Windows Search feature of Windows7.
The best would be to use suffix tree (or trie) to implement such a functionality.
Initially, index all the files in the suffix tree with the leaf node value being the location of the file on the disk.
When the user searches, list all the files with the prefixes as entered by the user.
If you wanted to list based on prefixes, you pretty much need a prefix tree. A hash table won't really work. Another possibility is just a sorted array, of course, if the files are re-indexed relatively infrequently. I'd probably opt for a prefix tree.
I think the whole stucture is based on map reduce. Hash table is the very basic concept of it.
- ric February 20, 2012