CareerCup

There are many ways to solve it, depends on how large is the phone book.
Assuming it is not more than N= 10,000 entries ( I mean, seriously ? ) and none of the entries are more than m= 30 character long on the average - we can have an exact (mN) algorithm.
====
1. split input words into characters
2. generate a regex like ^(c.*)+$
3. Match this regex against all entries --> matches are the result.
Example:
J => ^J.*$
JD => ^J.*D.*$
====

Another way of doing it ( slightly optimally ) is imagining a prefix tree structure.
There, the problem is find all where ( same from previous ) in xpath language :
====
1. split input words into characters
2. generate an xpath like //c/*/c/*/
3. Find all that matches that.
====

They are equivalent approaches, however, once you reach a sub-tree, the second approach drastically reduces the no of nodes one needs to look for, it is much better than [1].

However, for an interview and practicality perspective:

/* search words */
_words_ = [ "John", "JohnDavis", "Ted", "JackMay"  ]
// the mumbo jumbo 
def search( word ){
  // we have a bug here, what about $.o is a regex?
  // we need to escape that, but...well... 
  regex = "^" + str(word.value, '') as { str($.o) + ".*" } + "$" 
  println(regex)
  select ( _words_ ) where { $.o =~ regex }
}
// now take for a spin 
println( search( 'J' ) )
println( search( 'JD' ) )

The result is not so bad:

➜  zoomba99 git:(master) ✗ zmb tmp.zm
^J.*$
[ John,JohnDavis,JackMay ]
^J.*D.*$
[ JohnDavis ]
➜  zoomba99 git:(master) ✗