I applied to ITA in 2008ish and was require to complete one of these, something very similar to instant search. Needless to say I failed because the question isn't about your ability to program, it is just if you know what a suffix-tree is.

These are fun puzzles but terrible interview questions.