Intelligent Search Engine in C++

Build a console search engine with autocomplete, spell check, and ranking.

Introduction

30 Second Summary

Every time you type into a search bar, something is working behind the scenes to guess what you want, fix your typos, and remember what you searched last time. These features feel like magic, but they're built on elegant data structures and algorithms.

In this project, you will build a console-based intelligent search engine in C++ that autocompletes words as you type, corrects your spelling mistakes, and recommends related searches.

What You'll Build

A modular C++ application with 7 interconnected modules that combine a Trie, LRU Cache, and Graph to power autocomplete, spell checking, ranking, and recommendations from a single console menu.

By the end of this project, you'll have:

  • A Trie data structure that delivers instant autocomplete suggestions from any prefix you type.
  • A Levenshtein distance spell checker that detects typos and suggests the closest correct word.
  • An LRU cache and file persistence layer that remembers your recent searches between sessions.
  • A graph-based recommendation engine that suggests related terms based on your search patterns.
  • Secret Mission: Add a search analytics dashboard that displays a visual bar chart of your most searched terms.

Are there any prerequisites?

No prior setup is needed. This guide walks you through installing and configuring all required tools, including VS Code and the g++ compiler.

Before We Start

Before you can build a search engine, you need a workspace with all the right files in place. Think of it like setting up a workshop before starting a build.

In this step, you will verify your C++ compiler is ready, create a project folder, populate a word database, and scaffold all 13 source files that will eventually hold your search engine modules.

In this step, get ready to:
  • Verify your g++ compiler works with C++17 support.
  • Create the project folder and word database.
  • Scaffold all 13 source files as empty stubs.
Verify your C++ compiler

Your search engine uses modern C++ features, so you need a compiler that supports the C++17 standard. The g++ compiler from MinGW-w64 handles this on Windows.

  • Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
  • Type VS Code and press Enter to open it.
  • Open the integrated terminal by pressing Ctrl+` (backtick key, usually above Tab).
  • Check that g++ is installed by running this command:
g++ --version

You should see output showing a version number (e.g. something like 13.x.x or higher).

Not seeing a version number?

If you see an error like "command not found" or "not recognized", g++ is not on your system PATH. Revisit the MinGW-w64 installation and ensure you added its bin folder to your PATH environment variable.

After updating PATH, close and reopen VS Code for the change to take effect.

help me set up MinGW-w64 g++ so it works in VS Code's terminal

Create the project folder and database

Your search engine needs a home folder and a word database to search through. The database is a simple text file where each line has a word followed by its search frequency.

  • Move to your Desktop by running this command:
cd ~/Desktop
  • Create your project folder and move into it by running these commands:
mkdir search-engine
cd search-engine
  • Create the database.txt file by opening VS Code in this folder:
code .
  • In the Explorer sidebar on the left, click the New File icon (the page with a plus sign).
  • Name the file database.txt and press Enter.
  • Paste the following word data into database.txt:
algorithm 5
array 3
binary 4
boolean 2
class 7
compiler 3
computer 8
data 6
database 5
debug 2
encryption 1
exception 2
fibonacci 3
function 6
graph 4
hardware 2
inheritance 3
integer 4
java 5
javascript 6
kernel 2
lambda 3
linux 4
loop 5
machine 3
memory 4
network 5
object 6
operator 3
pointer 4
program 5
programming 4
processor 3
python 7
queue 3
recursion 4
runtime 2
software 5
stack 4
string 6
template 3
thread 2
ubuntu 1
variable 5
vector 4
windows 3

What is this file for?

Each line contains a word and a number separated by a space. The number represents how many times that word has been searched before.

Your search engine will read this file on startup to populate its data structures. It will also write updated frequencies back to this file when you exit, so your search history persists between sessions.

  • Save database.txt by pressing Ctrl+S (Windows) or Cmd+S (macOS).

File not appearing in the sidebar?

Make sure VS Code opened the search-engine folder (check the folder name in the Explorer sidebar title). If it opened a different folder, click File then Open Folder and select the search-engine folder from your Desktop.

help me open the correct project folder in VS Code

Create all source file stubs

Your search engine is built from 6 modules, each with a header file (.h) and an implementation file (.cpp). You will also have a main.cpp that ties everything together.

Why separate header and implementation files?

Header files declare what a class can do (its interface). Implementation files define how it does it.

This separation is a core OOP design pattern in C++. It lets different modules use each other without needing to see each other's full source code.

  • Open the integrated terminal in VS Code by pressing Ctrl+`.
  • Create all 13 source files as empty stubs by running this command:

macOS

for f in Trie.h Trie.cpp SpellChecker.h SpellChecker.cpp Ranking.h Ranking.cpp LRUCache.h LRUCache.cpp Database.h Database.cpp Recommendation.h Recommendation.cpp main.cpp; do echo "// empty stub" > $f; done

What does this command do?

This loops through each filename and creates a file containing a single placeholder comment. You will replace these stubs with real code in the following steps.

Windows

foreach ($f in @("Trie.h","Trie.cpp","SpellChecker.h","SpellChecker.cpp","Ranking.h","Ranking.cpp","LRUCache.h","LRUCache.cpp","Database.h","Database.cpp","Recommendation.h","Recommendation.cpp","main.cpp")) { Set-Content -Path $f -Value "// empty stub" }

What does this command do?

This loops through each filename and creates a file containing a single placeholder comment. You will replace these stubs with real code in the following steps.

  • Confirm all files were created by running:
ls

You should see 14 items listed: database.txt plus your 13 source files (Trie.h, Trie.cpp, SpellChecker.h, SpellChecker.cpp, Ranking.h, Ranking.cpp, LRUCache.h, LRUCache.cpp, Database.h, Database.cpp, Recommendation.h, Recommendation.cpp, and main.cpp).

Missing files in the output?

Double-check that you ran the loop command from inside the search-engine folder. Run pwd to confirm your current directory ends with search-engine.

If any files are missing, re-run the loop command. It will overwrite existing stubs without causing issues.

help me figure out why my source files were not created

✔️ Awesome, I've got everything!

Great. Double check you have saved database.txt and that all 14 files appear in the Explorer sidebar on the left.

ⓧ I'd like to double check the full code

Your database.txt should contain exactly this:

algorithm 5
array 3
binary 4
boolean 2
class 7
compiler 3
computer 8
data 6
database 5
debug 2
encryption 1
exception 2
fibonacci 3
function 6
graph 4
hardware 2
inheritance 3
integer 4
java 5
javascript 6
kernel 2
lambda 3
linux 4
loop 5
machine 3
memory 4
network 5
object 6
operator 3
pointer 4
program 5
programming 4
processor 3
python 7
queue 3
recursion 4
runtime 2
software 5
stack 4
string 6
template 3
thread 2
ubuntu 1
variable 5
vector 4
windows 3

Each of your 13 source files (Trie.h, Trie.cpp, SpellChecker.h, SpellChecker.cpp, Ranking.h, Ranking.cpp, LRUCache.h, LRUCache.cpp, Database.h, Database.cpp, Recommendation.h, Recommendation.cpp, main.cpp) should contain:

// empty stub

Your workspace is ready. Next up, you will fill in the Trie module and watch your search engine deliver instant autocomplete suggestions.

Create the Project Structure

Your project folder already has 15 empty source files waiting to be filled in. Before you can implement any logic, you need to define the blueprint for each module.

In C++, header files (.h) declare what each class can do, while implementation files (.cpp) contain the actual logic. In this step, you will fill in all 7 header files with class declarations so later steps can implement them one at a time.

In this step, get ready to:
  • Write class declarations with include guards for all 7 header files.
  • Update implementation files with stub markers for future steps.
Write the Trie header file

The Trie is the core data structure that powers autocomplete. Its header file needs two class declarations: one for individual nodes and one for the tree itself.

  • In VS Code, open Trie.h from the Explorer sidebar.
  • Replace the empty stub with this class declaration:
#ifndef TRIE_H
#define TRIE_H

#include <string>
#include <vector>
#include <unordered_map>

// Each node holds a map of children and a flag marking complete words
class TrieNode {
public:
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    TrieNode();
    ~TrieNode();
};

// The Trie tree provides insert, search, and prefix-based suggestions
class Trie {
private:
    TrieNode* root;
    void collectWords(TrieNode* node, const std::string& prefix, std::vector<std::string>& results);

public:
    Trie();
    ~Trie();
    void insert(const std::string& word);
    bool search(const std::string& word);
    std::vector<std::string> getSuggestions(const std::string& prefix, int maxResults = 5);
};

#endif

What does this code do?

The #ifndef / #define / #endif wrapper is called an include guard. It prevents the compiler from processing the same header twice when multiple files include it.

TrieNode represents a single character in the tree. Each node holds a map of child characters and a flag to mark whether it completes a word.

The Trie class is the tree itself. It provides insert() to add words, search() to check if a word exists, and getSuggestions() to return autocomplete matches for a prefix.

  • Save Trie.h.

Seeing red squiggly lines in VS Code?

If VS Code shows errors under std::unordered_map or std::string, IntelliSense may not be configured for C++17 yet. The code is still correct and will compile fine with g++. You can ignore these until the project compiles.

help me fix IntelliSense red squiggly lines in my C++ header files

Write the remaining header files

The remaining 5 header files follow the same pattern: include guard, includes, class declaration with public and private sections. Each declares the interface that its matching .cpp file will implement in later steps.

  • Open SpellChecker.h and replace the empty stub with this declaration:
#ifndef SPELLCHECKER_H
#define SPELLCHECKER_H

#include <string>
#include <vector>

// Detects misspelled words and suggests corrections using edit distance
class SpellChecker {
private:
    std::vector<std::string> dictionary;
    int levenshteinDistance(const std::string& s1, const std::string& s2);

public:
    SpellChecker();
    void loadDictionary(const std::vector<std::string>& words);
    void addWord(const std::string& word);
    bool isCorrect(const std::string& word);
    std::string correct(const std::string& word);
    int getDistance(const std::string& s1, const std::string& s2);
};

#endif

What does this class do?

SpellChecker stores a dictionary of known words and uses the Levenshtein distance algorithm to find the closest match when a user misspells something. The correct() method returns the best suggestion.

  • Save SpellChecker.h.
  • Open Ranking.h and replace the empty stub with this declaration:
#ifndef RANKING_H
#define RANKING_H

#include <string>
#include <vector>
#include <unordered_map>

// Tracks search frequency and sorts results by popularity
class Ranking {
private:
    std::unordered_map<std::string, int> frequency;

public:
    Ranking();
    void recordSearch(const std::string& query);
    int getFrequency(const std::string& query);
    std::vector<std::string> rankResults(std::vector<std::string>& results);
    std::unordered_map<std::string, int> getAllFrequencies() const;
    void setFrequency(const std::string& word, int freq);
};

#endif

What does this class do?

Ranking tracks how many times each word has been searched. The rankResults() method sorts autocomplete suggestions so frequently searched words appear first.

  • Save Ranking.h.
  • Open LRUCache.h and replace the empty stub with this declaration:
#ifndef LRUCACHE_H
#define LRUCACHE_H

#include <string>
#include <list>
#include <unordered_map>
#include <vector>

// Stores recent searches with O(1) add and retrieval using a linked list + hashmap
class LRUCache {
private:
    int capacity;
    std::list<std::string> cacheList;
    std::unordered_map<std::string, std::list<std::string>::iterator> cacheMap;

public:
    LRUCache(int capacity = 10);
    void add(const std::string& query);
    std::vector<std::string> getRecent();
    bool contains(const std::string& query);
};

#endif

What does this class do?

LRUCache keeps a fixed-size list of recent searches. When the cache is full, it evicts the least recently used entry. The combination of std::list and std::unordered_map gives O(1) performance for both adding and looking up items.

  • Save LRUCache.h.
  • Open Database.h and replace the empty stub with this declaration:
#ifndef DATABASE_H
#define DATABASE_H

#include <string>
#include <vector>
#include <unordered_map>

// Handles reading and writing word data to database.txt
class Database {
private:
    std::string filename;

public:
    Database(const std::string& filename = "database.txt");
    std::vector<std::string> loadWords();
    std::unordered_map<std::string, int> loadFrequencies();
    void save(const std::unordered_map<std::string, int>& data);
    bool fileExists();
};

#endif

What does this class do?

Database handles file I/O. It reads database.txt to load words and their frequencies at startup, and writes updated frequencies back when the program exits.

  • Save Database.h.
  • Open Recommendation.h and replace the empty stub with this declaration:
#ifndef RECOMMENDATION_H
#define RECOMMENDATION_H

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>

// Builds a graph of related searches using an adjacency list
class Recommendation {
private:
    std::unordered_map<std::string, std::unordered_set<std::string>> graph;

public:
    Recommendation();
    void addRelation(const std::string& word1, const std::string& word2);
    std::vector<std::string> getRecommendations(const std::string& query);
    void buildFromSearchHistory(const std::vector<std::string>& history);
};

#endif

What does this class do?

Recommendation uses a graph (adjacency list) to connect words that are searched one after another. When you search "data" then "algorithm", those two words become linked. Later, searching either one suggests the other.

  • Save Recommendation.h.

Accidentally pasted into the wrong file?

Each header file name matches the class it declares. If you see #ifndef RANKING_H at the top of LRUCache.h, you pasted the wrong content. Use Ctrl+Z (Windows) or Cmd+Z (macOS) to undo and try again.

help me figure out which header content goes in which file

Update the implementation file stubs

The .cpp files will hold the actual logic for each class. For now, update each stub with a comment indicating which step will implement it.

  • Open Trie.cpp and replace its contents with:
// stub - to be implemented in Step 2
  • Open SpellChecker.cpp and Ranking.cpp. Replace each with:
// stub - to be implemented in Step 3
  • Open LRUCache.cpp and Database.cpp. Replace each with:
// stub - to be implemented in Step 4
  • Open Recommendation.cpp and main.cpp. Replace each with:
// stub - to be implemented in Step 5

Why mark stubs with step numbers?

Labelling each stub tells you exactly when you will come back to implement it. This keeps the project navigable as it grows to 15 files.

  • Save all open files. You can press Cmd+S (macOS) or Ctrl+S (Windows) in each tab, or use Cmd+Option+S (macOS) or Ctrl+K S (Windows) to save all at once.
  • Confirm your project has 15 source files plus database.txt by running this in the terminal:
ls

You should see all 16 files listed: 7 .h files, 7 .cpp files, main.cpp, and database.txt.

Missing files in the listing?

Make sure your terminal is inside the search-engine folder. Run pwd (macOS/Linux) or cd (Windows) to check your current directory. If you are in the wrong folder, navigate back with:

cd ~/Desktop/search-engine

✔️ Awesome, I've got everything!

Great. Double check that you have saved every file.

ⓧ I'd like to double check the full code

Here are the complete contents of each header file. Compare yours against these:

#ifndef TRIE_H
#define TRIE_H

#include <string>
#include <vector>
#include <unordered_map>

class TrieNode {
public:
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    TrieNode();
    ~TrieNode();
};

class Trie {
private:
    TrieNode* root;
    void collectWords(TrieNode* node, const std::string& prefix, std::vector<std::string>& results);

public:
    Trie();
    ~Trie();
    void insert(const std::string& word);
    bool search(const std::string& word);
    std::vector<std::string> getSuggestions(const std::string& prefix, int maxResults = 5);
};

#endif
#ifndef SPELLCHECKER_H
#define SPELLCHECKER_H

#include <string>
#include <vector>

class SpellChecker {
private:
    std::vector<std::string> dictionary;
    int levenshteinDistance(const std::string& s1, const std::string& s2);

public:
    SpellChecker();
    void loadDictionary(const std::vector<std::string>& words);
    void addWord(const std::string& word);
    bool isCorrect(const std::string& word);
    std::string correct(const std::string& word);
    int getDistance(const std::string& s1, const std::string& s2);
};

#endif
#ifndef RANKING_H
#define RANKING_H

#include <string>
#include <vector>
#include <unordered_map>

class Ranking {
private:
    std::unordered_map<std::string, int> frequency;

public:
    Ranking();
    void recordSearch(const std::string& query);
    int getFrequency(const std::string& query);
    std::vector<std::string> rankResults(std::vector<std::string>& results);
    std::unordered_map<std::string, int> getAllFrequencies() const;
    void setFrequency(const std::string& word, int freq);
};

#endif
#ifndef LRUCACHE_H
#define LRUCACHE_H

#include <string>
#include <list>
#include <unordered_map>
#include <vector>

class LRUCache {
private:
    int capacity;
    std::list<std::string> cacheList;
    std::unordered_map<std::string, std::list<std::string>::iterator> cacheMap;

public:
    LRUCache(int capacity = 10);
    void add(const std::string& query);
    std::vector<std::string> getRecent();
    bool contains(const std::string& query);
};

#endif
#ifndef DATABASE_H
#define DATABASE_H

#include <string>
#include <vector>
#include <unordered_map>

class Database {
private:
    std::string filename;

public:
    Database(const std::string& filename = "database.txt");
    std::vector<std::string> loadWords();
    std::unordered_map<std::string, int> loadFrequencies();
    void save(const std::unordered_map<std::string, int>& data);
    bool fileExists();
};

#endif
#ifndef RECOMMENDATION_H
#define RECOMMENDATION_H

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>

class Recommendation {
private:
    std::unordered_map<std::string, std::unordered_set<std::string>> graph;

public:
    Recommendation();
    void addRelation(const std::string& word1, const std::string& word2);
    std::vector<std::string> getRecommendations(const std::string& query);
    void buildFromSearchHistory(const std::vector<std::string>& history);
};

#endif

Each .cpp file should contain only a stub comment:

// stub - to be implemented in Step 2
// stub - to be implemented in Step 3
// stub - to be implemented in Step 3
// stub - to be implemented in Step 4
// stub - to be implemented in Step 4
// stub - to be implemented in Step 5
// stub - to be implemented in Step 5

Your project skeleton is complete. Every header file now declares the class interface that you will implement in the next steps. Next up, you will bring the Trie to life and power the autocomplete system.

Build the Trie AutoComplete System

Your project folder is set up with all the header declarations and stubs ready to fill in. Now it is time to build the first core data structure that powers the search engine.

A Trie (pronounced "try") is a tree-shaped data structure optimized for prefix lookups. Each node represents one character, and paths from root to leaf spell out complete words. This makes it perfect for autocomplete because finding all words starting with "pro" means traversing just three nodes, then collecting every branch below.

In this step, get ready to:
  • Implement the TrieNode and Trie classes with insert and search methods.
  • Build the getSuggestions method that collects autocomplete results from a prefix.
  • Compile the Trie module to verify your implementation.
Implement the TrieNode and Trie classes

Every Trie starts with an empty root node. From there, each character in a word creates a child node. The Trie needs two basic operations: inserting words character by character, and searching for whether a word exists.

  • In VS Code, open Trie.cpp from the search-engine folder in the Explorer sidebar.
  • Replace the stub comment with the following code that sets up the class foundations and the insert() method:
#include "Trie.h"
#include <cctype>

// TrieNode constructor - each node starts as not-end-of-word
TrieNode::TrieNode() : isEndOfWord(false) {}

// TrieNode destructor - recursively deletes all child nodes
TrieNode::~TrieNode() {
    for (auto& pair : children) {
        delete pair.second;
    }
}

// Trie constructor - creates an empty root node
Trie::Trie() {
    root = new TrieNode();
}

// Trie destructor - deleting root triggers recursive cleanup
Trie::~Trie() {
    delete root;
}

// Inserts a word into the Trie one character at a time
void Trie::insert(const std::string& word) {
    TrieNode* current = root;
    for (char c : word) {
        char lower = std::tolower(c);
        if (current->children.find(lower) == current->children.end()) {
            current->children[lower] = new TrieNode();
        }
        current = current->children[lower];
    }
    current->isEndOfWord = true;
}

What does this code do?

The TrieNode stores a map of child characters and a flag marking whether it completes a word. The destructor walks through all children and frees their memory recursively.

The insert() method walks down the Trie character by character. If a character node does not exist yet, it creates one. After the last character, it marks that node as the end of a word. Every character is lowercased so searches are case-insensitive.

You will not see a visible change yet. The next chunk adds the search() method that uses this same traversal pattern.

  • Add the search() method below the insert() method you just wrote:
// Checks if an exact word exists in the Trie
bool Trie::search(const std::string& word) {
    TrieNode* current = root;
    for (char c : word) {
        char lower = std::tolower(c);
        if (current->children.find(lower) == current->children.end()) {
            return false;
        }
        current = current->children[lower];
    }
    return current->isEndOfWord;
}

What does this code do?

The search() method follows the same node-by-node traversal as insert(). If any character is missing from the path, the word does not exist. If the traversal completes, it checks whether the final node is marked as end-of-word.

  • Save Trie.cpp.
  • Verify the file compiles by running this in your terminal:
g++ -std=c++17 -c Trie.cpp

If no errors appear, your Trie foundation is syntactically correct. The -c flag compiles without linking, so other stub files do not interfere.

Seeing a compile error?

  • Check that Trie.h is in the same folder as Trie.cpp. The #include "Trie.h" line looks for the file in the current directory.
  • Verify that every opening brace { has a matching closing brace }. Missing braces are the most common copy-paste error.
  • Make sure the #include <cctype> line is present. Without it, std::tolower is undefined.

Why is my Trie.cpp not compiling? I see an error about an undefined function or a missing header file.

Implement the autocomplete suggestions

The real power of a Trie is prefix matching. Given a prefix like "pro", the engine navigates to the node for 'o', then collects every complete word reachable from that point.

  • Add the collectWords() helper method below search() in Trie.cpp:
// Recursively collects all complete words below a given node
void Trie::collectWords(TrieNode* node, const std::string& prefix, std::vector<std::string>& results) {
    if (node->isEndOfWord) {
        results.push_back(prefix);
    }
    for (auto& pair : node->children) {
        collectWords(pair.second, prefix + pair.first, results);
    }
}

What does this code do?

This is a recursive depth-first traversal. Starting from a given node, it checks if the current node completes a word. If so, it adds the built-up prefix to the results. Then it explores every child branch, appending each character to the prefix as it goes deeper.

You will not see a change yet. The getSuggestions() method you write next calls this helper.

  • Add the getSuggestions() method below collectWords() to complete the file:
// Returns up to maxResults words that match the given prefix
std::vector<std::string> Trie::getSuggestions(const std::string& prefix, int maxResults) {
    std::vector<std::string> results;
    TrieNode* current = root;

    // Convert prefix to lowercase for case-insensitive matching
    std::string lowerPrefix;
    for (char c : prefix) {
        lowerPrefix += std::tolower(c);
    }

    // Navigate to the node at the end of the prefix
    for (char c : lowerPrefix) {
        if (current->children.find(c) == current->children.end()) {
            return results;
        }
        current = current->children[c];
    }

    // Collect all words branching from this prefix node
    collectWords(current, lowerPrefix, results);

    // Limit results to maxResults (default 5)
    if (static_cast<int>(results.size()) > maxResults) {
        results.resize(maxResults);
    }

    return results;
}

What does this code do?

First, it lowercases the prefix so matching is case-insensitive. Then it navigates down the Trie to the node where the prefix ends. If any prefix character is missing, it returns an empty list immediately.

Once at the prefix node, it calls collectWords() to gather every complete word below that point. Finally, it trims the results to a maximum of 5 suggestions.

  • Save Trie.cpp.
  • Compile the complete file by running:
g++ -std=c++17 -c Trie.cpp

No output means success. Your Trie implementation compiles cleanly with all methods defined.

Seeing an error about collectWords or getSuggestions?

  • Check that collectWords() appears before getSuggestions() in the file. C++ needs functions defined before they are called (unless declared in the header, which they are, but ordering still matters for readability).
  • Make sure the method signatures match Trie.h exactly. The parameter types and return types must be identical to the header declarations.

Why is getSuggestions not compiling? I added collectWords and getSuggestions but still see errors.

Compile and verify the Trie module

With all methods implemented, you can confirm the Trie module is ready by verifying the object file was created on disk.

  • Confirm the compiled object file exists by running:
ls Trie.o

You should see Trie.o listed in the output. This object file contains your compiled Trie code, ready to be linked into the final executable in a later step.

When will I see autocomplete in action?

The interactive menu that lets you type a prefix and see suggestions is wired up in Step 5 when you implement main.cpp. At that point, typing "pro" in the AutoComplete option will return words like "program", "programming", and "processor" from your database.

✔️ Awesome, I've got everything!

Great. Double check you have saved Trie.cpp and that Trie.o exists in your project folder.

ⓧ I'd like to double check the full code

Here is the complete Trie.cpp file. Compare your version against this:

#include "Trie.h"
#include <cctype>

TrieNode::TrieNode() : isEndOfWord(false) {}

TrieNode::~TrieNode() {
    for (auto& pair : children) {
        delete pair.second;
    }
}

Trie::Trie() {
    root = new TrieNode();
}

Trie::~Trie() {
    delete root;
}

void Trie::insert(const std::string& word) {
    TrieNode* current = root;
    for (char c : word) {
        char lower = std::tolower(c);
        if (current->children.find(lower) == current->children.end()) {
            current->children[lower] = new TrieNode();
        }
        current = current->children[lower];
    }
    current->isEndOfWord = true;
}

bool Trie::search(const std::string& word) {
    TrieNode* current = root;
    for (char c : word) {
        char lower = std::tolower(c);
        if (current->children.find(lower) == current->children.end()) {
            return false;
        }
        current = current->children[lower];
    }
    return current->isEndOfWord;
}

void Trie::collectWords(TrieNode* node, const std::string& prefix, std::vector<std::string>& results) {
    if (node->isEndOfWord) {
        results.push_back(prefix);
    }
    for (auto& pair : node->children) {
        collectWords(pair.second, prefix + pair.first, results);
    }
}

std::vector<std::string> Trie::getSuggestions(const std::string& prefix, int maxResults) {
    std::vector<std::string> results;
    TrieNode* current = root;

    std::string lowerPrefix;
    for (char c : prefix) {
        lowerPrefix += std::tolower(c);
    }

    for (char c : lowerPrefix) {
        if (current->children.find(c) == current->children.end()) {
            return results;
        }
        current = current->children[c];
    }

    collectWords(current, lowerPrefix, results);

    if (static_cast<int>(results.size()) > maxResults) {
        results.resize(maxResults);
    }

    return results;
}

Your Trie is fully built and compiling cleanly. Next up, you will implement the SpellChecker that catches typos and the Ranking system that sorts suggestions by popularity.

Build the SpellChecker and Ranking System

Your Trie can suggest words that start with a given prefix. But what happens when a user misspells their query? Typing "compter" instead of "computer" returns zero results, even though the intended word is in the database.

In this step, you will implement a spell checker that detects typos and suggests the closest correct word. You will also add a ranking system that tracks how often each word is searched, so popular results float to the top of autocomplete suggestions.

In this step, get ready to:
  • Implement the Levenshtein distance algorithm to measure how "far apart" two strings are.
  • Build spell correction that finds the closest dictionary word to a misspelled query.
  • Add frequency-based ranking so popular words appear first in autocomplete results.
Implement the Levenshtein distance algorithm

The Levenshtein distance between two strings is the minimum number of single-character edits (insertions, deletions, or substitutions) needed to transform one string into the other. For example, turning "compter" into "computer" requires one insertion (the missing "u"), so the distance is 1.

Our implementation uses a space-optimized dynamic programming approach with two rolling vectors instead of a full matrix. This keeps memory usage at O(n) instead of O(m*n).

  • Open SpellChecker.cpp in VS Code.
  • Replace the entire file contents with the following code to set up the class foundation and the core algorithm:
#include "SpellChecker.h"
#include <algorithm>
#include <climits>

SpellChecker::SpellChecker() {}

void SpellChecker::loadDictionary(const std::vector<std::string>& words) {
    dictionary = words;
}

void SpellChecker::addWord(const std::string& word) {
    dictionary.push_back(word);
}

int SpellChecker::levenshteinDistance(const std::string& s1, const std::string& s2) {
    int m = static_cast<int>(s1.size());
    int n = static_cast<int>(s2.size());

    // Two rolling vectors: prev holds the previous row, curr holds the current row
    std::vector<int> prev(n + 1);
    std::vector<int> curr(n + 1);

    // Base case: transforming empty s1 prefix into s2 prefix requires j insertions
    for (int j = 0; j <= n; j++) {
        prev[j] = j;
    }

    // Fill the DP table row by row
    for (int i = 1; i <= m; i++) {
        curr[0] = i; // Transforming s1 prefix of length i into empty string requires i deletions
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                // Characters match: no edit needed, carry diagonal value
                curr[j] = prev[j - 1];
            } else {
                // Take minimum of delete, insert, or substitute (each costs 1)
                curr[j] = 1 + std::min({prev[j], curr[j - 1], prev[j - 1]});
            }
        }
        prev = curr; // Roll: current row becomes previous for next iteration
    }

    return prev[n];
}

What does this code do?

The constructor and helper methods (loadDictionary, addWord) manage the word list that the spell checker compares against.

The levenshteinDistance() method is the core algorithm. It builds a DP table row by row, where each cell represents the minimum edits to transform one prefix into another. Instead of storing the full m-by-n matrix, it keeps only two rows (prev and curr) since each row only depends on the one before it.

At each cell, it picks the cheapest of three operations: deletion (prev[j]), insertion (curr[j - 1]), or substitution (prev[j - 1]). If the characters already match, no edit is needed.

You won't see a change yet. The next chunk adds the public methods that use this algorithm to actually correct misspelled words.

Implement spell correction and search ranking

Now you need public methods that use the Levenshtein distance to check spelling and find corrections. You will also implement the Ranking class that tracks search frequency.

  • In SpellChecker.cpp, add the following code below the levenshteinDistance() method:
bool SpellChecker::isCorrect(const std::string& word) {
    // Convert input to lowercase for case-insensitive comparison
    std::string lower = word;
    std::transform(lower.begin(), lower.end(), lower.begin(), ::tolower);
    for (const auto& w : dictionary) {
        std::string dictLower = w;
        std::transform(dictLower.begin(), dictLower.end(), dictLower.begin(), ::tolower);
        if (lower == dictLower) {
            return true;
        }
    }
    return false;
}

std::string SpellChecker::correct(const std::string& word) {
    std::string lower = word;
    std::transform(lower.begin(), lower.end(), lower.begin(), ::tolower);

    // If already correct, return as-is
    if (isCorrect(lower)) {
        return lower;
    }

    // Edge case: empty dictionary means no correction possible
    if (dictionary.empty()) {
        return word;
    }

    // Find the dictionary word with the smallest edit distance
    std::string bestMatch;
    int minDist = INT_MAX;

    for (const auto& w : dictionary) {
        std::string dictLower = w;
        std::transform(dictLower.begin(), dictLower.end(), dictLower.begin(), ::tolower);
        int dist = levenshteinDistance(lower, dictLower);
        if (dist < minDist) {
            minDist = dist;
            bestMatch = dictLower;
        }
    }

    return bestMatch;
}

int SpellChecker::getDistance(const std::string& s1, const std::string& s2) {
    return levenshteinDistance(s1, s2);
}

What does this code do?

The isCorrect() method checks whether a word exists in the dictionary by doing a case-insensitive comparison against every stored word.

The correct() method is the spell checker's main feature. It computes the Levenshtein distance between the misspelled input and every dictionary word, then returns whichever word has the smallest distance. This is a brute-force approach that works well for small dictionaries like ours.

The getDistance() method is a public wrapper that exposes the private levenshteinDistance() method for external use.

  • Save SpellChecker.cpp.

Now implement the Ranking class that tracks how often each word is searched.

  • Open Ranking.cpp and replace its entire contents with this code:
#include "Ranking.h"
#include <algorithm>

Ranking::Ranking() {}

void Ranking::recordSearch(const std::string& query) {
    // Increment the search count for this word
    frequency[query]++;
}

int Ranking::getFrequency(const std::string& query) {
    // Return the search count, or 0 if never searched
    if (frequency.find(query) != frequency.end()) {
        return frequency[query];
    }
    return 0;
}

std::vector<std::string> Ranking::rankResults(std::vector<std::string>& results) {
    // Sort results so the most-searched words appear first
    std::sort(results.begin(), results.end(), [this](const std::string& a, const std::string& b) {
        return frequency[a] > frequency[b];
    });
    return results;
}

std::unordered_map<std::string, int> Ranking::getAllFrequencies() const {
    return frequency;
}

void Ranking::setFrequency(const std::string& word, int freq) {
    frequency[word] = freq;
}

What does this code do?

The frequency map stores how many times each word has been searched. Every call to recordSearch() increments that word's count.

The rankResults() method sorts a list of autocomplete suggestions by frequency (highest first) using a lambda that captures this to access the frequency map. Words searched more often float to the top.

  • Save Ranking.cpp.
  • Recompile the project by running this command in your terminal:
g++ -std=c++17 -o search_engine.exe main.cpp Trie.cpp SpellChecker.cpp Ranking.cpp LRUCache.cpp Database.cpp Recommendation.cpp
  • Confirm the build succeeds with no errors.

Seeing a compile error?

  • If you see an error about INT_MAX being undeclared, make sure you have #include <climits> at the top of SpellChecker.cpp.
  • If you see errors about std::transform or std::sort, make sure both files include <algorithm>.
  • Check that the curly braces match. A missing } at the end of a method causes cascading errors below it.

Still stuck? Help me fix my SpellChecker or Ranking compile error.

Test spell checking and ranking
  • Run the program:
.\search_engine.exe
  • Choose option 1 (Search).
  • Type compter and press Enter.
  • You should see the prompt: Did you mean: "computer"? (y/n):.
  • Type y and press Enter to accept the correction.

The spell checker detected that "compter" is not in the dictionary and found "computer" as the closest match (only 1 edit away).

  • Now test ranking. Search for "python" three or four times using option 1.
  • Choose option 2 (AutoComplete).
  • Type pro as the prefix.
  • Verify that the suggestions now show search counts next to each word, and words you searched more appear higher in the list.

Spell correction not working?

  • Make sure you saved both SpellChecker.cpp and Ranking.cpp before recompiling.
  • Verify you recompiled after saving. Changes to .cpp files only take effect after you run the compile command again.
  • If the program shows "No suggestions found" for autocomplete, make sure database.txt is in the same folder as your executable.

Still stuck? Help me debug why spell correction or ranking is not working.

✔️ Awesome, I've got everything!

Great. Double check you have saved both SpellChecker.cpp and Ranking.cpp.

ⓧ I'd like to double check the full code

Here is the complete SpellChecker.cpp:

#include "SpellChecker.h"
#include <algorithm>
#include <climits>

SpellChecker::SpellChecker() {}

void SpellChecker::loadDictionary(const std::vector<std::string>& words) {
    dictionary = words;
}

void SpellChecker::addWord(const std::string& word) {
    dictionary.push_back(word);
}

bool SpellChecker::isCorrect(const std::string& word) {
    std::string lower = word;
    std::transform(lower.begin(), lower.end(), lower.begin(), ::tolower);
    for (const auto& w : dictionary) {
        std::string dictLower = w;
        std::transform(dictLower.begin(), dictLower.end(), dictLower.begin(), ::tolower);
        if (lower == dictLower) {
            return true;
        }
    }
    return false;
}

int SpellChecker::levenshteinDistance(const std::string& s1, const std::string& s2) {
    int m = static_cast<int>(s1.size());
    int n = static_cast<int>(s2.size());

    std::vector<int> prev(n + 1);
    std::vector<int> curr(n + 1);

    for (int j = 0; j <= n; j++) {
        prev[j] = j;
    }

    for (int i = 1; i <= m; i++) {
        curr[0] = i;
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                curr[j] = prev[j - 1];
            } else {
                curr[j] = 1 + std::min({prev[j], curr[j - 1], prev[j - 1]});
            }
        }
        prev = curr;
    }

    return prev[n];
}

std::string SpellChecker::correct(const std::string& word) {
    std::string lower = word;
    std::transform(lower.begin(), lower.end(), lower.begin(), ::tolower);

    if (isCorrect(lower)) {
        return lower;
    }

    if (dictionary.empty()) {
        return word;
    }

    std::string bestMatch;
    int minDist = INT_MAX;

    for (const auto& w : dictionary) {
        std::string dictLower = w;
        std::transform(dictLower.begin(), dictLower.end(), dictLower.begin(), ::tolower);
        int dist = levenshteinDistance(lower, dictLower);
        if (dist < minDist) {
            minDist = dist;
            bestMatch = dictLower;
        }
    }

    return bestMatch;
}

int SpellChecker::getDistance(const std::string& s1, const std::string& s2) {
    return levenshteinDistance(s1, s2);
}

And here is the complete Ranking.cpp:

#include "Ranking.h"
#include <algorithm>

Ranking::Ranking() {}

void Ranking::recordSearch(const std::string& query) {
    frequency[query]++;
}

int Ranking::getFrequency(const std::string& query) {
    if (frequency.find(query) != frequency.end()) {
        return frequency[query];
    }
    return 0;
}

std::vector<std::string> Ranking::rankResults(std::vector<std::string>& results) {
    std::sort(results.begin(), results.end(), [this](const std::string& a, const std::string& b) {
        return frequency[a] > frequency[b];
    });
    return results;
}

std::unordered_map<std::string, int> Ranking::getAllFrequencies() const {
    return frequency;
}

void Ranking::setFrequency(const std::string& word, int freq) {
    frequency[word] = freq;
}

Your search engine can now catch typos and rank results by popularity. Next up, you will add an LRU cache for recent searches and file-based persistence so your data survives between sessions.

Build the LRU Cache and Database Persistence

Your search engine can autocomplete and fix typos, but it has no memory. Every time you close the program, all search history vanishes.

In this step, you will build two modules that give your engine a brain. An LRU cache tracks the most recent searches in memory, and a Database class reads and writes search frequencies to disk so data survives between sessions.

In this step, get ready to:
  • Implement an LRU cache with O(1) insertion and retrieval.
  • Implement a Database class that loads and saves word frequencies to a file.
  • Verify both modules compile without errors.
Implement the LRU cache add logic

An LRU cache evicts the least recently used item when it runs out of space. The trick to making every operation O(1) is combining a doubly linked list (for ordering) with a hashmap (for instant lookups).

  • Open LRUCache.cpp in VS Code.
  • Replace the stub comment with the following code:
#include "LRUCache.h"

// Initialize with the given capacity
LRUCache::LRUCache(int capacity) : capacity(capacity) {}

void LRUCache::add(const std::string& query) {
    // If already cached, remove the old position
    if (cacheMap.find(query) != cacheMap.end()) {
        cacheList.erase(cacheMap[query]);
    }

    // Insert at the front (most recent position)
    cacheList.push_front(query);
    cacheMap[query] = cacheList.begin();

    // Evict the oldest entry if over capacity
    if (static_cast<int>(cacheList.size()) > capacity) {
        std::string last = cacheList.back();
        cacheList.pop_back();
        cacheMap.erase(last);
    }
}

What does this code do?

The constructor stores the maximum number of items the cache can hold (10 in this project).

  • When add() is called, it first checks if the query is already in the cache. If so, it removes the old entry from the linked list to reposition it.
  • The query is then pushed to the front of cacheList (the most recent position), and its iterator is stored in cacheMap for O(1) lookups.
  • If the list exceeds capacity, the last item (least recently used) is evicted from both the list and the map.

Do not save the file yet. You will add the remaining methods next.

Add the retrieval methods
  • Add the following code below the add() method you just wrote:
// Return all cached items from most recent to oldest
std::vector<std::string> LRUCache::getRecent() {
    std::vector<std::string> recent;
    for (const auto& item : cacheList) {
        recent.push_back(item);
    }
    return recent;
}

// Check if a query exists in the cache
bool LRUCache::contains(const std::string& query) {
    return cacheMap.find(query) != cacheMap.end();
}

What does this code do?

  • getRecent() iterates the linked list front-to-back, copying items into a vector. Because push_front places new entries at the front, the vector is already in most-recent-first order.
  • contains() does a quick hashmap lookup to check whether a query is already cached.
  • Save LRUCache.cpp.

Seeing red squiggles in VS Code?

  • Make sure you included the header #include "LRUCache.h" at the top of the file.
  • Check that LRUCache.h is in the same folder as LRUCache.cpp.
  • Verify there are no typos in the method signatures. They must match the declarations in the header file exactly.

Why isn't my LRUCache.cpp compiling?

✔️ Awesome, I've got everything!

Great. Double check you have saved LRUCache.cpp before moving on.

ⓧ I'd like to double check the full code

#include "LRUCache.h"

LRUCache::LRUCache(int capacity) : capacity(capacity) {}

void LRUCache::add(const std::string& query) {
    if (cacheMap.find(query) != cacheMap.end()) {
        cacheList.erase(cacheMap[query]);
    }

    cacheList.push_front(query);
    cacheMap[query] = cacheList.begin();

    if (static_cast<int>(cacheList.size()) > capacity) {
        std::string last = cacheList.back();
        cacheList.pop_back();
        cacheMap.erase(last);
    }
}

std::vector<std::string> LRUCache::getRecent() {
    std::vector<std::string> recent;
    for (const auto& item : cacheList) {
        recent.push_back(item);
    }
    return recent;
}

bool LRUCache::contains(const std::string& query) {
    return cacheMap.find(query) != cacheMap.end();
}

Why a linked list plus a hashmap?

A linked list alone gives O(1) insertion and removal at the ends, but finding a specific node is O(n). A hashmap alone gives O(1) lookup, but has no concept of ordering.

Combining both gives you the best of each. The hashmap stores an iterator pointing directly to a node in the list, so you can find, remove, and reposition any entry in O(1) time.

Implement the Database file reader

The Database class handles all file I/O. It reads words and their frequencies from database.txt on startup, and writes updated frequencies back when the program exits.

  • Open Database.cpp in VS Code.
  • Replace the stub comment with the following code:
#include "Database.h"
#include <fstream>
#include <sstream>
#include <iostream>

// Store the filename for all read/write operations
Database::Database(const std::string& filename) : filename(filename) {}

// Check if the database file exists on disk
bool Database::fileExists() {
    std::ifstream file(filename);
    return file.good();
}

// Load just the words (first column) from each line
std::vector<std::string> Database::loadWords() {
    std::vector<std::string> words;
    std::ifstream file(filename);

    if (!file.is_open()) {
        std::cerr << "Warning: Could not open " << filename << std::endl;
        return words;
    }

    std::string line;
    while (std::getline(file, line)) {
        std::istringstream iss(line);
        std::string word;
        iss >> word;
        if (!word.empty()) {
            words.push_back(word);
        }
    }

    file.close();
    return words;
}

What does this code do?

  • The constructor stores the filename (defaulting to database.txt) using a member initializer list.
  • fileExists() opens the file and checks whether the stream is in a good state. If the file does not exist, good() returns false.
  • loadWords() reads each line, extracts the first token (the word), and pushes it into a vector. The frequency column is ignored here.

Do not save the file yet. You will add more methods next.

  • Add the loadFrequencies() method below loadWords():
// Load both words and their frequency counts
std::unordered_map<std::string, int> Database::loadFrequencies() {
    std::unordered_map<std::string, int> frequencies;
    std::ifstream file(filename);

    if (!file.is_open()) {
        return frequencies;
    }

    std::string line;
    while (std::getline(file, line)) {
        std::istringstream iss(line);
        std::string word;
        int freq = 0;
        iss >> word >> freq;
        if (!word.empty()) {
            frequencies[word] = freq;
        }
    }

    file.close();
    return frequencies;
}

How is this different from loadWords?

loadWords() only grabs the first token on each line (the word itself). loadFrequencies() reads both columns: the word and its integer frequency count. It stores them in an unordered_map so other modules can look up how often a word has been searched.

Do not save yet. One more method to add.

  • Add the save() method below loadFrequencies():
// Write all word-frequency pairs back to the file
void Database::save(const std::unordered_map<std::string, int>& data) {
    std::ofstream file(filename);

    if (!file.is_open()) {
        std::cerr << "Error: Could not save to " << filename << std::endl;
        return;
    }

    for (const auto& pair : data) {
        file << pair.first << " " << pair.second << "\n";
    }

    file.close();
}

What does this code do?

  • save() opens the file for writing (std::ofstream), which overwrites the existing contents.
  • If the file cannot be opened (e.g. permissions issue), it prints an error and returns early without crashing.
  • Each word-frequency pair is written on its own line in the format word frequency, matching what loadFrequencies() expects to read.
  • Save Database.cpp.

Seeing errors about fstream or sstream?

  • Make sure all four includes are at the top of the file: Database.h, <fstream>, <sstream>, and <iostream>.
  • Check you are using std::ifstream for reading and std::ofstream for writing. Mixing them up causes compile errors.

Help me fix my Database.cpp file I/O errors.

✔️ Awesome, I've got everything!

Great. Double check you have saved Database.cpp before moving on.

ⓧ I'd like to double check the full code

#include "Database.h"
#include <fstream>
#include <sstream>
#include <iostream>

Database::Database(const std::string& filename) : filename(filename) {}

bool Database::fileExists() {
    std::ifstream file(filename);
    return file.good();
}

std::vector<std::string> Database::loadWords() {
    std::vector<std::string> words;
    std::ifstream file(filename);

    if (!file.is_open()) {
        std::cerr << "Warning: Could not open " << filename << std::endl;
        return words;
    }

    std::string line;
    while (std::getline(file, line)) {
        std::istringstream iss(line);
        std::string word;
        iss >> word;
        if (!word.empty()) {
            words.push_back(word);
        }
    }

    file.close();
    return words;
}

std::unordered_map<std::string, int> Database::loadFrequencies() {
    std::unordered_map<std::string, int> frequencies;
    std::ifstream file(filename);

    if (!file.is_open()) {
        return frequencies;
    }

    std::string line;
    while (std::getline(file, line)) {
        std::istringstream iss(line);
        std::string word;
        int freq = 0;
        iss >> word >> freq;
        if (!word.empty()) {
            frequencies[word] = freq;
        }
    }

    file.close();
    return frequencies;
}

void Database::save(const std::unordered_map<std::string, int>& data) {
    std::ofstream file(filename);

    if (!file.is_open()) {
        std::cerr << "Error: Could not save to " << filename << std::endl;
        return;
    }

    for (const auto& pair : data) {
        file << pair.first << " " << pair.second << "\n";
    }

    file.close();
}
Verify both modules compile

Before wiring these modules into the main application (next step), confirm that your new code compiles without errors.

  • Compile LRUCache.cpp by running this command in your VS Code terminal:
g++ -std=c++17 -c LRUCache.cpp
  • Compile Database.cpp by running:
g++ -std=c++17 -c Database.cpp
  • You should see no output from either command. No output means no errors.
  • Confirm the object files were created by running:
ls *.o
  • You should see LRUCache.o and Database.o in the output.

What does the -c flag do?

The -c flag tells g++ to compile the source file into an object file (.o) without linking. This lets you check each module for errors independently, even before main.cpp is ready.

Seeing compile errors?

  • Read the error message carefully. The line number tells you exactly where the problem is.
  • Make sure your terminal is in the search-engine folder. Run ls to confirm you can see your .cpp and .h files listed.
  • Check that the method signatures in your .cpp files match the declarations in the corresponding .h headers exactly.

Help me fix my g++ compile errors for LRUCache or Database.

Both modules are ready. In the next step, you will build the recommendation engine and wire everything together in main.cpp so you can test the full search flow.

Build the Recommendation Engine and Console Menu

Your LRU cache and database persistence are working. Search data now survives between sessions, so the engine remembers how often each word was searched.

The final piece is connecting everything together. In this step, you'll build a graph-based recommendation engine that suggests related words based on your search patterns. Then you'll wire all seven modules into one interactive console application.

In this step, get ready to:
  • Implement the Recommendation class with a graph-based adjacency list.
  • Wire all modules together in the main application loop.
  • Test the complete search engine with all 5 menu options.
Implement the Recommendation class

The recommendation engine uses a graph to connect words that are searched one after another. If you search "algorithm" and then "data", the engine creates a link between those two words so it can suggest one when you search the other.

What is an adjacency list?

An adjacency list is a way to represent a graph where each node stores a set of its neighbors. Here, we use an unordered_map where each key is a word and its value is an unordered_set of related words.

Using unordered_set prevents duplicate edges automatically. If you search "data" after "algorithm" five times, only one link is created between them.

  • In VS Code, open Recommendation.cpp and replace the stub comment with this implementation:
#include "Recommendation.h"

// Constructor initializes an empty recommendation graph
Recommendation::Recommendation() {}

// Create a bidirectional link between two words
void Recommendation::addRelation(const std::string& word1, const std::string& word2) {
    // Skip self-relations (searching the same word twice in a row)
    if (word1 != word2) {
        graph[word1].insert(word2);
        graph[word2].insert(word1);
    }
}

// Return all words connected to the given query
std::vector<std::string> Recommendation::getRecommendations(const std::string& query) {
    std::vector<std::string> results;

    if (graph.find(query) != graph.end()) {
        for (const auto& related : graph[query]) {
            results.push_back(related);
        }
    }

    return results;
}

// Build recommendation links from a list of consecutive searches
void Recommendation::buildFromSearchHistory(const std::vector<std::string>& history) {
    for (size_t i = 1; i < history.size(); i++) {
        addRelation(history[i - 1], history[i]);
    }
}

What does this code do?

  • addRelation() creates bidirectional edges. Searching "algorithm" then "data" means both words point to each other.
  • getRecommendations() looks up a word in the graph and returns all its connected neighbors.
  • buildFromSearchHistory() takes a list of past searches and connects each consecutive pair. This is a utility for batch-building the graph.
  • The if (word1 != word2) guard prevents a word from being recommended to itself.
  • Save Recommendation.cpp.

You won't see a change yet. The next chunk wires this into the main application where you can test it.

Implement the console menu and search flow

Now you'll build the main application that ties all seven modules together into one interactive program. The menu loop lets users search, get autocomplete suggestions, view recent searches, get recommendations, and exit.

  • Open main.cpp and replace the stub comment with the includes and the displayMenu() function:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#include "Trie.h"
#include "SpellChecker.h"
#include "Ranking.h"
#include "LRUCache.h"
#include "Database.h"
#include "Recommendation.h"

// Display the main menu options to the user
void displayMenu() {
    std::cout << "\n========================================\n";
    std::cout << "   Intelligent Search Engine v1.0\n";
    std::cout << "========================================\n";
    std::cout << "1. Search\n";
    std::cout << "2. AutoComplete\n";
    std::cout << "3. Recent Searches\n";
    std::cout << "4. Recommendations\n";
    std::cout << "5. Exit\n";
    std::cout << "========================================\n";
    std::cout << "Choose an option: ";
}

What does this code do?

  • The includes pull in all seven module headers plus the standard library headers for I/O, strings, vectors, and the transform algorithm.
  • displayMenu() prints the numbered menu. This gets called each time the loop repeats, so the user always sees their options.
  • Below displayMenu() in the same file, add the main() function:
int main() {
    // Initialize all modules
    Database db("database.txt");
    Trie trie;
    SpellChecker spellChecker;
    Ranking ranking;
    LRUCache cache(10);
    Recommendation recommendation;

    // Load words and frequencies from the database file
    std::vector<std::string> words = db.loadWords();
    std::unordered_map<std::string, int> frequencies = db.loadFrequencies();

    // Populate the trie and spell checker with all known words
    for (const auto& word : words) {
        trie.insert(word);
        spellChecker.addWord(word);
    }

    // Restore saved search frequencies into the ranking system
    for (const auto& pair : frequencies) {
        ranking.setFrequency(pair.first, pair.second);
    }

    std::cout << "Loaded " << words.size() << " words from database.\n";

    std::vector<std::string> searchHistory;
    int choice;

    while (true) {
        displayMenu();
        std::cin >> choice;
        std::cin.ignore();

        if (choice == 5) {
            db.save(ranking.getAllFrequencies());
            std::cout << "Data saved. Goodbye!\n";
            break;
        }

        switch (choice) {
            case 1: {
                std::cout << "\nEnter search query: ";
                std::string query;
                std::getline(std::cin, query);

                // Convert to lowercase for consistent matching
                std::transform(query.begin(), query.end(), query.begin(), ::tolower);

                // Spell check and offer correction
                if (!spellChecker.isCorrect(query)) {
                    std::string corrected = spellChecker.correct(query);
                    std::cout << "Did you mean: \"" << corrected << "\"? (y/n): ";
                    char response;
                    std::cin >> response;
                    std::cin.ignore();
                    if (response == 'y' || response == 'Y') {
                        query = corrected;
                    }
                }

                // Look up the word in the trie
                if (trie.search(query)) {
                    std::cout << "\nFound: \"" << query << "\"\n";
                } else {
                    std::cout << "\n\"" << query << "\" not found in database.\n";
                }

                // Update ranking and cache
                ranking.recordSearch(query);
                cache.add(query);

                // Build recommendation links from consecutive searches
                searchHistory.push_back(query);
                if (searchHistory.size() >= 2) {
                    recommendation.addRelation(
                        searchHistory[searchHistory.size() - 2],
                        searchHistory[searchHistory.size() - 1]
                    );
                }

                // Display related searches if any exist
                std::vector<std::string> recs = recommendation.getRecommendations(query);
                if (!recs.empty()) {
                    std::cout << "\nRelated searches: ";
                    for (const auto& rec : recs) {
                        std::cout << "\"" << rec << "\" ";
                    }
                    std::cout << "\n";
                }

                break;
            }

            case 2: {
                std::cout << "\nEnter prefix: ";
                std::string prefix;
                std::getline(std::cin, prefix);

                // Get autocomplete suggestions from the trie
                std::vector<std::string> suggestions = trie.getSuggestions(prefix);

                if (suggestions.empty()) {
                    std::cout << "No suggestions found.\n";
                } else {
                    // Sort suggestions by search frequency
                    ranking.rankResults(suggestions);
                    std::cout << "\nSuggestions:\n";
                    for (size_t i = 0; i < suggestions.size(); i++) {
                        std::cout << "  " << (i + 1) << ". " << suggestions[i]
                                  << " (searches: " << ranking.getFrequency(suggestions[i]) << ")\n";
                    }
                }

                break;
            }

            case 3: {
                // Display recent searches from the LRU cache
                std::vector<std::string> recent = cache.getRecent();
                if (recent.empty()) {
                    std::cout << "\nNo recent searches.\n";
                } else {
                    std::cout << "\nRecent Searches:\n";
                    for (size_t i = 0; i < recent.size(); i++) {
                        std::cout << "  " << (i + 1) << ". " << recent[i] << "\n";
                    }
                }
                break;
            }

            case 4: {
                std::cout << "\nEnter a word for recommendations: ";
                std::string word;
                std::getline(std::cin, word);

                std::transform(word.begin(), word.end(), word.begin(), ::tolower);

                // Look up related words in the recommendation graph
                std::vector<std::string> recs = recommendation.getRecommendations(word);
                if (recs.empty()) {
                    std::cout << "No recommendations available for \"" << word << "\".\n";
                    std::cout << "Search more to build recommendations!\n";
                } else {
                    std::cout << "\nRecommended searches related to \"" << word << "\":\n";
                    for (size_t i = 0; i < recs.size(); i++) {
                        std::cout << "  " << (i + 1) << ". " << recs[i] << "\n";
                    }
                }
                break;
            }

            default:
                std::cout << "Invalid option. Please try again.\n";
                break;
        }
    }

    return 0;
}

What does this code do?

The main() function orchestrates all seven modules into one cohesive application:

  • Initialization loads words from database.txt into the Trie, SpellChecker, and Ranking system.
  • Case 1 (Search) runs the full pipeline: lowercase conversion, spell check, trie lookup, ranking update, cache update, and recommendation building.
  • Case 2 (AutoComplete) gets prefix suggestions from the Trie and sorts them by search frequency.
  • Case 3 (Recent Searches) pulls the most recent queries from the LRU cache.
  • Case 4 (Recommendations) queries the graph for related words.
  • Case 5 (Exit) saves all frequencies back to database.txt before closing.

Why build recommendations from consecutive searches?

When you search "algorithm" and then "data", those two topics are likely related in your mind. By linking consecutive searches, the engine learns your personal associations between terms without needing a pre-built knowledge graph.

  • Save main.cpp.

Seeing a compile error?

  • Make sure displayMenu() appears before main() in the file. C++ requires functions to be declared before they are called.
  • Check that all six #include lines for your module headers are present at the top of the file.
  • Verify the opening and closing braces match for each case block. Each case uses { } to scope its local variables.

Help me fix a compile error in my main.cpp search engine file.

✔️ Awesome, I've got everything!

Great. Double check you've saved both Recommendation.cpp and main.cpp.

ⓧ I'd like to double check the full code

Here is the complete Recommendation.cpp:

#include "Recommendation.h"

Recommendation::Recommendation() {}

void Recommendation::addRelation(const std::string& word1, const std::string& word2) {
    if (word1 != word2) {
        graph[word1].insert(word2);
        graph[word2].insert(word1);
    }
}

std::vector<std::string> Recommendation::getRecommendations(const std::string& query) {
    std::vector<std::string> results;

    if (graph.find(query) != graph.end()) {
        for (const auto& related : graph[query]) {
            results.push_back(related);
        }
    }

    return results;
}

void Recommendation::buildFromSearchHistory(const std::vector<std::string>& history) {
    for (size_t i = 1; i < history.size(); i++) {
        addRelation(history[i - 1], history[i]);
    }
}

Here is the complete main.cpp:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#include "Trie.h"
#include "SpellChecker.h"
#include "Ranking.h"
#include "LRUCache.h"
#include "Database.h"
#include "Recommendation.h"

void displayMenu() {
    std::cout << "\n========================================\n";
    std::cout << "   Intelligent Search Engine v1.0\n";
    std::cout << "========================================\n";
    std::cout << "1. Search\n";
    std::cout << "2. AutoComplete\n";
    std::cout << "3. Recent Searches\n";
    std::cout << "4. Recommendations\n";
    std::cout << "5. Exit\n";
    std::cout << "========================================\n";
    std::cout << "Choose an option: ";
}

int main() {
    Database db("database.txt");
    Trie trie;
    SpellChecker spellChecker;
    Ranking ranking;
    LRUCache cache(10);
    Recommendation recommendation;

    std::vector<std::string> words = db.loadWords();
    std::unordered_map<std::string, int> frequencies = db.loadFrequencies();

    for (const auto& word : words) {
        trie.insert(word);
        spellChecker.addWord(word);
    }

    for (const auto& pair : frequencies) {
        ranking.setFrequency(pair.first, pair.second);
    }

    std::cout << "Loaded " << words.size() << " words from database.\n";

    std::vector<std::string> searchHistory;
    int choice;

    while (true) {
        displayMenu();
        std::cin >> choice;
        std::cin.ignore();

        if (choice == 5) {
            db.save(ranking.getAllFrequencies());
            std::cout << "Data saved. Goodbye!\n";
            break;
        }

        switch (choice) {
            case 1: {
                std::cout << "\nEnter search query: ";
                std::string query;
                std::getline(std::cin, query);

                std::transform(query.begin(), query.end(), query.begin(), ::tolower);

                if (!spellChecker.isCorrect(query)) {
                    std::string corrected = spellChecker.correct(query);
                    std::cout << "Did you mean: \"" << corrected << "\"? (y/n): ";
                    char response;
                    std::cin >> response;
                    std::cin.ignore();
                    if (response == 'y' || response == 'Y') {
                        query = corrected;
                    }
                }

                if (trie.search(query)) {
                    std::cout << "\nFound: \"" << query << "\"\n";
                } else {
                    std::cout << "\n\"" << query << "\" not found in database.\n";
                }

                ranking.recordSearch(query);
                cache.add(query);

                searchHistory.push_back(query);
                if (searchHistory.size() >= 2) {
                    recommendation.addRelation(
                        searchHistory[searchHistory.size() - 2],
                        searchHistory[searchHistory.size() - 1]
                    );
                }

                std::vector<std::string> recs = recommendation.getRecommendations(query);
                if (!recs.empty()) {
                    std::cout << "\nRelated searches: ";
                    for (const auto& rec : recs) {
                        std::cout << "\"" << rec << "\" ";
                    }
                    std::cout << "\n";
                }

                break;
            }

            case 2: {
                std::cout << "\nEnter prefix: ";
                std::string prefix;
                std::getline(std::cin, prefix);

                std::vector<std::string> suggestions = trie.getSuggestions(prefix);

                if (suggestions.empty()) {
                    std::cout << "No suggestions found.\n";
                } else {
                    ranking.rankResults(suggestions);
                    std::cout << "\nSuggestions:\n";
                    for (size_t i = 0; i < suggestions.size(); i++) {
                        std::cout << "  " << (i + 1) << ". " << suggestions[i]
                                  << " (searches: " << ranking.getFrequency(suggestions[i]) << ")\n";
                    }
                }

                break;
            }

            case 3: {
                std::vector<std::string> recent = cache.getRecent();
                if (recent.empty()) {
                    std::cout << "\nNo recent searches.\n";
                } else {
                    std::cout << "\nRecent Searches:\n";
                    for (size_t i = 0; i < recent.size(); i++) {
                        std::cout << "  " << (i + 1) << ". " << recent[i] << "\n";
                    }
                }
                break;
            }

            case 4: {
                std::cout << "\nEnter a word for recommendations: ";
                std::string word;
                std::getline(std::cin, word);

                std::transform(word.begin(), word.end(), word.begin(), ::tolower);

                std::vector<std::string> recs = recommendation.getRecommendations(word);
                if (recs.empty()) {
                    std::cout << "No recommendations available for \"" << word << "\".\n";
                    std::cout << "Search more to build recommendations!\n";
                } else {
                    std::cout << "\nRecommended searches related to \"" << word << "\":\n";
                    for (size_t i = 0; i < recs.size(); i++) {
                        std::cout << "  " << (i + 1) << ". " << recs[i] << "\n";
                    }
                }
                break;
            }

            default:
                std::cout << "Invalid option. Please try again.\n";
                break;
        }
    }

    return 0;
}
Test the complete flow

Time to see all seven modules working together. You'll compile the full project and run through the search flow to verify recommendations build correctly.

  • Compile the project by running this command in your terminal:
g++ -std=c++17 -o search_engine.exe main.cpp Trie.cpp SpellChecker.cpp Ranking.cpp LRUCache.cpp Database.cpp Recommendation.cpp
  • Run the executable:
.\search_engine.exe

You should see "Loaded 46 words from database." followed by the menu.

  • Choose option 1 (Search) and type algorithm.
  • Choose option 1 again and type data.
  • Choose option 1 again and type graph.
  • Choose option 1 one more time and type data.

After your second search for "data", you should see "algorithm" and "graph" listed as related searches. This confirms the recommendation graph is building connections from your consecutive searches.

  • Choose option 4 (Recommendations) and type data.

You should see "algorithm" and "graph" listed as recommended searches related to "data".

  • Choose option 5 to exit. You should see "Data saved. Goodbye!" confirming your frequencies were written back to database.txt.

Not seeing recommendations?

  • Make sure you searched at least two different words before expecting recommendations. The engine needs consecutive searches to build links.
  • Check that you typed the word exactly the same both times. The graph stores lowercase versions, so capitalization differences would create separate entries.
  • If the program crashes on input, verify the std::cin.ignore() line appears after every std::cin >> choice and std::cin >> response call. This clears leftover newline characters from the input buffer.

Help me debug why my search engine recommendations are not appearing after consecutive searches.

Secret mission

Add a Search Analytics Dashboard

Your search engine collects frequency data on every search. What if you could visualize that data as a bar chart right in the console? Add an analytics dashboard that shows the top 5 most searched words with scaled visual bars.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your project files to continue experimenting, or delete them entirely.

Resources you used:

  • The search-engine project folder on your Desktop (15 source files, database.txt, and the compiled search_engine.exe).

Keep everything running

No action needed. Choose this if you want to keep experimenting with your search engine, adding more words to the database, or extending the code with new features.

  • Your project files stay in the search-engine folder on your Desktop.
  • You can recompile and run anytime by opening the folder in VS Code and using the terminal.

Pause - I'll come back to this later

Since this is a local project with no running processes, there is nothing to pause. Your files will stay on your Desktop until you decide to delete them.

  • Close VS Code to free up memory.
  • Your search-engine folder and all source files remain on your Desktop for when you return.

Delete - I don't want to use this again

Remove all project files from your machine.

  • Close VS Code.
  • Delete the search-engine folder by running the command for your operating system below.

macOS

rm -rf ~/Desktop/search-engine

Windows

rmdir /s /q %USERPROFILE%\Desktop\search-engine
  • Confirm the folder is gone by checking your Desktop.

Nice Work!

Nice Work!

Nice work! You just built a fully functional intelligent search engine in C++ from scratch, combining multiple data structures and algorithms into one cohesive application.

You've learned how to:

  • Build a Trie data structure from scratch that performs instant prefix-based autocomplete suggestions.
  • Implement the Levenshtein edit distance algorithm to detect typos and suggest spelling corrections using dynamic programming.
  • Design interconnected modules using object-oriented programming patterns, wiring together an LRU cache, a graph-based recommendation engine, and file persistence into one clean console interface.
  • Secret Mission: Added a visual analytics dashboard displaying search frequency patterns as a scaled bar chart.

Ready to quiz yourself?