Card 03/ 07
Choosing Example: Checking Usernames While They Are Typed
A sign-up form says, letter by letter, whether a name is taken and lists the taken names that start the same way.
A sign-up form that checks a username as it is typed needs a different structure from one that also lists the taken names starting with the letters already typed, and listing the operations shows where the line falls. This card covers the form's operations, their cost in a hash set, a trie and a sorted array, and how one added operation changes the choice.
The site holds two million usernames. On every keystroke the form says whether the name typed is taken; once a name is free, the person signs up and the name is added. Then the designers add a list under the box: the taken names that begin with what has been typed, so that someone typing "ada" sees "ada", "adam" and "ada_k" and picks something else.
In the table, k is the length of the name typed, m the number of names the list shows, and n the number of usernames. A trie is a tree with one node per letter, in which every name starting with the same letters shares the same path from the root.
| Operation | How often | Hash set | Trie | Sorted array |
|---|---|---|---|---|
| Is this name taken? | Every keystroke | O(k) on average, to hash the name | O(k) | O(k log n), halving the array |
| Add a new name | Every sign-up | O(k) on average | O(k) | O(n), shifting the names after it |
| List the taken names that start with what is typed | Every keystroke | O(n × k), checking every name | O(k + m) | O(k log n + m) |
Before the list, the form asks two things, both about whole names, and order never matters. That is a hash set: a lookup and an add, each O(k) on average.
The list changes the question. A prefix is not a key a hash set can find, so every keystroke would compare all two million names with the letters typed. The trie walks k nodes down the path for those letters and reads off the m names below it, however many names the site holds. A sorted array finds the same names, since they sit side by side, but each sign-up shifts on average a million entries to make room.
The steps stay the same from one program to the next, and the answer follows the operations. A question about numbers in order would have chosen an ordered tree, and a question about text by prefix chooses a trie.
← → move through sections and cards