Autocomplete

The goal for this one was to write a system for automatically completing a given input. It's an easy problem to explain, but a little tricky to tease out the interesting parts.

For the first session most groups just built simple pattern matchers or key/value pair objects, but by the second session there were groups working on building tries and another using the Levenshtein distance metric to compute the closest match.

A fun problem, but because the interesting parts are more technical and harder to motivate it's probably best for experienced groups.

write up

autocompleter:

• generate a prefix list up front
• store as a trie instead
• use a red-black tree trie
• or an AVL tree
• make it adaptable to new vocabulary
• make it usable