Module assignment: Word index

What this assignment asks you to build

You will write a small program that acts as a word index. The index holds a set of lowercase words. A user, or a test script, sends it one command per line: add a word, remove a word, count the words that start with some letters, or ask for suggestions. The program answers each command on its own line of output, and it stops when it reads the command end.

The program is a real piece of the kind of system this module covers. A phone's typing suggestions, a search box's counts, and a personal dictionary's delete button all need the same three features: insert, count by prefix, and list by prefix. Your index will do all three with one trie. Every lesson in this module feeds into it.

This assignment is due as a single file, word_index.cpp, that compiles with g++ -std=c++17. It reads from standard input and writes to standard output. You do not need any other file, and you should not use a library that does the work for you, such as a built-in set or map of strings. The point is to build the trie yourself.

Work through the spec, then the checklist, then the rubric. The hints and the reference solution are hidden under their own headings, so you can try the work first and open them when you are stuck.

The spec

The program reads commands until it sees end or runs out of input. Each command starts with one word, and the rest of the command is given as separate tokens. Read the tokens with cin >> token, which is how the earlier lessons read input.

Here are the commands. Each one prints exactly one line, unless the command produces several lines as noted.

• add WORD adds WORD to the index. It prints added when the word is new, and duplicate when the word is already stored. It prints invalid when WORD is not valid.
• remove WORD removes WORD from the index. It prints removed when the word was stored, and missing when it was not. It prints invalid when WORD is not valid.
• count PREFIX prints the number of stored words that start with PREFIX. A prefix that is not valid prints invalid. A prefix with no matches prints 0.
• suggest PREFIX K prints up to K stored words that start with PREFIX, one per line, in alphabetical order. K must be a whole number from 1 to 10. When nothing matches, it prints none. When PREFIX is not valid, or K is outside 1 to 10, it prints invalid.
• end stops the program. Any command after end is ignored.
• Any other first word prints unknown command.

A valid word or prefix has 1 to 20 characters, and every character is a lowercase letter from a to z. The words apple and app are valid. The words Banana, hello2, a-b and an empty token are not valid.

The index stores each word once. Adding a word that is already stored does not change the count of words that start with its letters. Removing a word that was never stored does not change anything.

An example to check your program against

Here is a complete example. The input is what you type in the Input box, one command per line. The output is what the program must print, line for line.

add apple
add app
add apple
add Banana
add applet
count app
suggest app 2
remove app
count app
suggest zz 3
remove zz
end
add ignored

Expected output:

added
added
duplicate
invalid
added
3
app
apple
removed
2
none
missing

Walk through the example so you understand each line before you write code. The first two adds store apple and app, so both print added. The third add repeats apple, so it prints duplicate. Banana has an uppercase letter, so it prints invalid and is not stored. The fifth add stores applet, which prints added.

The count of app is 3, because apple, app and applet all start with app. The suggestion for app with a limit of 2 prints app and apple, the first two in alphabetical order. After remove app, the count of app drops to 2, because app is gone but apple and applet remain. The suggestion for zz finds no stored word, so it prints none. Removing zz prints missing, because it was never stored. The command end stops the program, so the last add is never read.

A second example checks the error paths.

add a
add ab
count a
suggest a 1
suggest a 11
remove ab
count a
frob
suggest q 3
end

Expected output:

added
added
2
a
invalid
removed
1
unknown command
none

This example has a limit of 11, which is outside the allowed range, so it prints invalid. The command frob is not one of the commands, so it prints unknown command. Test with both examples before you rely on your program.

Requirements checklist

Copy this list into your own notes and tick each line when your program does it. Each line is a behaviour the grader tests.

• The program compiles with g++ -std=c++17 and no errors.
• The program stores the words in a trie, not in a set, map or sorted list.
• add prints added for a new word and duplicate for a stored word.
• add and remove print invalid for a word with an uppercase letter, a digit, a symbol or more than 20 letters.
• remove prints removed for a stored word and missing otherwise.
• After remove, the word is no longer found by count or suggest, and a later add of the same word prints added.
• count returns the number of distinct stored words with the prefix, using pass counts so it does not walk the whole subtree.
• count returns 0 for a prefix with no matches, and does not crash on a missing path.
• suggest prints the words in alphabetical order, one per line, and stops at K words.
• suggest prints none when there are no matches and invalid when K is outside 1 to 10.
• Removing a word frees the nodes that no other word needs, and keeps the nodes that other words need.
• end stops the program, and an unknown command prints unknown command.
• The program never reads or writes outside its arrays, which you can check by running it with -fsanitize=address on your test inputs.

Grading rubric

Your grade depends on how many of the checklist items your program passes, and on how clean the code is. The three levels below describe what a solution at each level looks like.

A 60% solution handles the main commands on valid input. It stores words in a trie, prints added, duplicate, removed and missing correctly for simple inputs, and answers count and suggest on the first example. It may fail on invalid words, on the empty result of suggest, or on removing a word that shares letters with another word. It may have a count that goes wrong after a remove, which is the stale count bug from lesson three.

An 80% solution passes both examples and every checklist item about the commands. It validates words and limits, handles missing prefixes without crashing, and keeps the counts correct after removes. The code has clear functions for each command. A reader can tell which function does what. It may still have a weak point, such as a suggestion that walks more of the trie than it needs to, or a memory leak on remove.

A 100% solution does everything in an 80% solution and also prunes removed nodes correctly, so the trie frees the nodes no word needs. It keeps counts correct after every command, stops the suggestion search as soon as it has K words, and uses the address sanitizer without any report on a test with mixed commands. The code is short, names its functions well, and has a comment that explains the one rule that matters most: a node can go only when no word passes through it. Your write-up explains how you tested it, with at least three inputs of your own design that were not in this page.

The grader runs a set of hidden inputs. Each input is a list of commands. The output must match the expected output line for line, including the blank lines or their absence. Print each answer on its own line and end each line with a newline.

Plan your work

Build the program in layers, and test each layer before you add the next. Do not write the whole program at once.

1. Write the node struct with 26 child pointers, a word-end flag and a pass count. Lesson three shows the struct.
2. Write addWord, which returns whether the word was new. It must search first, then walk and increment the pass counts, then set the flag. Test it with the input add car, add car, count ca, and check that the output is added, duplicate, and 1.
3. Write validWord, which checks the length and the letters. Test it with add Banana and add followed by a 21-letter word.
4. Write removeWord, which decrements the pass counts along the path, clears the flag and prunes the nodes that reach zero. Test it with the car and card example from lesson three. Check the counts after each remove.
5. Write countPrefix and collect. Test suggest with limits 1, 2 and 10 on a list of at least five words that share a prefix.
6. Write the main function that reads commands, calls the right function, and prints the answer. Test the full examples.
7. Run your program with -fsanitize=address -g on your own test inputs. Fix every report before you submit.

Hints

Each hint is hidden under its own heading. Open one only when you are stuck on that step.

Stretch extension

Once your program passes the checklist, you can extend it. Add a command top K that prints the K most frequently added words, where a count increases each time a word is added successfully. Store the count on the word-end node, and use a heap to keep the best K. Describe in your write-up what the extension costs in time compared with the alphabetical suggest command, because the search can no longer stop early after K words.

Reference solution

Try the assignment before you open this. The reference solution below is one correct program. Your program may differ in structure and still be correct. It passes both examples in this page. Read it for the design choices, not to copy it.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
struct Node {
    Node* next[26] = {};
    bool isEnd = false;
    int pass = 0;  // number of stored words that pass through this node
};
 
Node* root = new Node();
 
bool validWord(const string& w) {
    if (w.empty() || w.size() > 20) return false;
    for (char c : w) {
        if (c < 'a' || c > 'z') return false;
    }
    return true;
}
 
Node* findNode(const string& p) {
    Node* cur = root;
    for (char c : p) {
        cur = cur->next[c - 'a'];
        if (!cur) return nullptr;
    }
    return cur;
}
 
bool contains(const string& w) {
    Node* n = findNode(w);
    return n && n->isEnd;
}
 
bool addWord(const string& w) {
    if (contains(w)) return false;
    Node* cur = root;
    for (char c : w) {
        int i = c - 'a';
        if (!cur->next[i]) cur->next[i] = new Node();
        cur = cur->next[i];
        cur->pass++;
    }
    cur->isEnd = true;
    return true;
}
 
bool removeWord(const string& w) {
    if (!contains(w)) return false;
    vector<Node*> parents;
    Node* cur = root;
    for (char c : w) {
        parents.push_back(cur);
        cur = cur->next[c - 'a'];
        cur->pass--;
    }
    cur->isEnd = false;
    for (int k = (int)w.size() - 1; k >= 0; k--) {
        Node* child = parents[k]->next[w[k] - 'a'];
        if (child->pass > 0) break;
        delete child;
        parents[k]->next[w[k] - 'a'] = nullptr;
    }
    return true;
}
 
int countPrefix(const string& p) {
    Node* n = findNode(p);
    return n ? n->pass : 0;
}
 
// adds words in alphabetical order until out holds limit words
void collect(Node* n, string& path, vector<string>& out, int limit) {
    if ((int)out.size() >= limit) return;
    if (n->isEnd) out.push_back(path);
    for (int i = 0; i < 26 && (int)out.size() < limit; i++) {
        if (n->next[i]) {
            path.push_back('a' + i);
            collect(n->next[i], path, out, limit);
            path.pop_back();
        }
    }
}
 
int main() {
    string cmd;
    while (cin >> cmd) {
        if (cmd == "end") break;
        if (cmd == "add") {
            string w;
            cin >> w;
            if (!validWord(w)) cout << "invalid\n";
            else cout << (addWord(w) ? "added" : "duplicate") << "\n";
        } else if (cmd == "remove") {
            string w;
            cin >> w;
            if (!validWord(w)) cout << "invalid\n";
            else cout << (removeWord(w) ? "removed" : "missing") << "\n";
        } else if (cmd == "count") {
            string p;
            cin >> p;
            if (!validWord(p)) cout << "invalid\n";
            else cout << countPrefix(p) << "\n";
        } else if (cmd == "suggest") {
            string p;
            int k;
            cin >> p >> k;
            if (!validWord(p) || k < 1 || k > 10) {
                cout << "invalid\n";
                continue;
            }
            vector<string> out;
            Node* start = findNode(p);
            if (start) {
                string path = p;
                collect(start, path, out, k);
            }
            if (out.empty()) cout << "none\n";
            else for (const string& w : out) cout << w << "\n";
        } else {
            cout << "unknown command\n";
        }
    }
}

Notes on the reference. The removeWord function is the lesson three pruning rule, with contains as the existence check. The collect function is the limited search from lesson two. The main loop is the only place that prints, so every command prints exactly one answer. The validWord check runs before any trie work, so an invalid word never changes the trie.

Submit and explain

When you submit, include three things: the program, the output for both examples, and a short note of at least three test inputs of your own. For each test, say what you expected and what the program printed. A test that shows a bug you fixed is worth more than a test that passes on the first try.

Finally, answer one question in two or three sentences: why does count stay fast after many adds and removes, and what would break if removeWord forgot to decrement the pass counts? Your answer should name the pass count and the walk, and it should give one concrete example of a wrong answer.

What you now know

• A trie stores words as paths, so insert, search, prefix listing and prefix counts all use the same walk.
• Pass counts answer prefix counts in one walk, and they must be updated on every add and remove.
• Pruning a removed word frees only the nodes that no other word uses.
• Input validation and the duplicate check belong before any change to the trie.
• Testing with the address sanitizer and with your own inputs catches the bugs that the examples miss.