Implement a Phone Directory

The problem, simply

You get a list of contacts and a query string that a user types one letter at a time. After each letter, show all contacts that start with the letters typed so far, in ABC order and without repeats. If no contact matches, show 0.

Below, N is the number of contacts, L is the longest contact, Q is the length of the query, and S is the number of letters in the contacts you show.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each prefix, look at every contact and keep the ones that start with it.

1. Put the contacts in a TreeSet. That removes repeats and keeps ABC order.
2. For each length 1 to Q, take the prefix of the query.
3. Collect every contact that starts with the prefix. If none, add 0.

import java.util.*;

class Solution {
    public static List<List<String>> displayContacts(String[] contacts, String query) {
        TreeSet<String> book = new TreeSet<>(Arrays.asList(contacts));   // sorted, no repeats
        List<List<String>> out = new ArrayList<>();
        for (int len = 1; len <= query.length(); len++) {
            String prefix = query.substring(0, len);
            List<String> hits = new ArrayList<>();
            for (String c : book) {
                if (c.startsWith(prefix)) hits.add(c);
            }
            if (hits.isEmpty()) hits.add("0");
            out.add(hits);
        }
        return out;
    }
}

How long it takes: Q prefixes, each checking N contacts for up to L letters, O(Q * N * L), plus the sort. Extra room: the sorted copy, O(N * L).

Way 2: the clever way

Put every contact in a trie. Each new letter is one step down from where you already are. Everything below that node is a match, so collect it with a depth first walk that tries children in ABC order.

1. Insert all contacts into a trie.
2. Keep a finger cur at the root. For each typed letter, move cur down that letter's branch.
3. If the branch is missing, this prefix and every longer one get 0.
4. Otherwise walk everything below cur. Each word end you meet is a suggestion, already in ABC order.

import java.util.*;

class Solution {
    private static class Node {
        Node[] next = new Node[26];
        boolean end;
    }

    public static List<List<String>> displayContacts(String[] contacts, String query) {
        Node root = new Node();
        for (String c : contacts) {                     // build the trie
            Node cur = root;
            for (char ch : c.toCharArray()) {
                int k = ch - 'a';
                if (cur.next[k] == null) cur.next[k] = new Node();
                cur = cur.next[k];
            }
            cur.end = true;                             // repeats land on the same node
        }

        List<List<String>> out = new ArrayList<>();
        Node cur = root;
        StringBuilder prefix = new StringBuilder();
        for (char ch : query.toCharArray()) {
            prefix.append(ch);
            cur = (cur == null) ? null : cur.next[ch - 'a'];   // one step from where we are
            List<String> hits = new ArrayList<>();
            if (cur != null) collect(cur, prefix, hits);
            if (hits.isEmpty()) hits.add("0");
            out.add(hits);
        }
        return out;
    }

    // depth first walk in ABC order: every word end below node is a match
    private static void collect(Node node, StringBuilder word, List<String> hits) {
        if (node.end) hits.add(word.toString());
        for (int k = 0; k < 26; k++) {
            if (node.next[k] != null) {
                word.append((char) ('a' + k));
                collect(node.next[k], word, hits);
                word.deleteCharAt(word.length() - 1);
            }
        }
    }
}

How long it takes: building the trie is O(N * L). Each prefix costs one step plus a walk over the part of the trie below it, which is about the size of what we print, so O(N * L + Q * S) in all. Extra room: the trie, O(26 * N * L).

Watch out for

• Repeated contacts. With a list they show up twice. In a trie they end at the same node, so they appear once.
• The 0 for no match. Many versions want the string 0, not an empty list. Read the problem.
• Children in a HashMap lose ABC order. Use an array of 26, or a TreeMap, if the order matters.

What interviewers ask next

• Show only the top 3 suggestions, like a search box? Store the best 3 words in every node while inserting. Then each keystroke is one step and a copy, no walk at all.
• Rank by how often a name is picked? Keep a count at each word end, and keep the top k per node in a small heap.
• Huge directories that do not fit in memory? Use a compressed trie, or a sorted file plus binary search for the range of words with the prefix.
• Can sorting alone do it? Yes. Sort once, then for each prefix binary search for the first and last word that start with it. Each prefix costs O(L log N) plus the output.

Remember this

Grown-up words: the drawer cabinet is a trie, the drawer you have open is the current node, reading every card inside is a depth first traversal of its subtree, and the whole feature is autocomplete.