I was asked about this question in the past at Visa, was wondering if anyone has a good solution without using DB and trie\n\nAll users have first name and last name and phone number in the phone book. User starts searching for a name using chars in middle of the fname or last name. The results should have all the contacts which contain this search string. \n\nexample: \n\nSam Arnold \nScott Zimmer\n\nuser searches:  immer\nit should bring \'Scott Zimmer\' \n\nI answered that trie can be used, but, it is hard to do it with this kind of requirements and without using DB. What kind of DS should be used?

I was asked about this question in the past at Visa, was wondering if anyone has a good solution without using DB and trie\n\nAll users have first name and last