title: Search a string as you type the character
body: <p>I have contacts stored in my mobile. Lets say my contacts are</p>
  
  <pre><code>Ram
  
  Hello
  
  Hi
  
  Feat
  
  Eat
  
  At
  </code></pre>
  
  <p>When I type letter <code>'A'</code> I should get all the matching contacts say <code>"Ram, Feat, Eat, At"</code>.</p>
  
  <p>Now I type one more letter <code>T</code>. Now my total string is <code>"AT"</code> now my program should reuse the results of previous search for <code>"A"</code>. Now it should return me <code>"Feat, Eat, At"</code></p>
  
  <p>Design and develop a program for this.</p>
  
  <p>This is interview question at Samsung mobile development</p>
  
  <p>I tried solving with <code>Trie data structures</code>. Could not get good solution for reusing already searched string results. I also tried solution with dictionary data structure, solution has same disadvantage as <code>Trie</code>.</p>
  
  <p>question is how do I search the contacts for each letter typed reusing the search results of earlier searched string? What data structure and algorithm should be used for efficiently solving the problem.</p>
  
  <p>I am not asking for program. So programming language is immaterial for me.</p>
  
  <p>State machine appears to be good solution. Does anyone have suggestion?</p>
  
  <p>Solution should be fast enough for million contacts.</p>