Gain insights into trie data structures, their implementation in C++ and Java, and their application in solving algorithmic problems and designing complex systems, enhancing your software engineering skills.

edited - Advanced Data Structures - TRIES.png

Trie is an efficient tree-like data structure used to store and retrieve information. It is frequently tested in coding interviews, indicating its widespread use in solving many real-world software engineering challenges.

This course covers every aspect of the trie data structure, from the intuition of building a trie to coding it in famous programming languages for solving algorithmic problems and designing real-world systems. It assumes a prior knowledge of trees and basic data structures like lists and arrays. 

The problems in this course are categorized into various patterns, which will help you map new solutions to known issues using tries. The problems are of varying difficulties, from easy to hard, thus giving you an iterative learning experience. By the end of this course, you’ll be able to decode relevant trie problems, code their solutions in C++ and Java, and apply trie concepts to design complex software systems.

Advanced Data Structures: Implementing Tries in C++ and Java

searchData: ['h','i','s','\n','h','e','r','\n','h','i','m','\n','h','i','t','\n','h','i','m','\n','h','i','\n']

query = h
autocomplete suggestion -->
query = hi
autocomplete suggestion -->
query = his
autocomplete suggestion -->
query = h
autocomplete suggestion --> his
query = he
autocomplete suggestion -->
query = her
autocomplete suggestion -->
query = h
autocomplete suggestion --> her his
query = hi
autocomplete suggestion --> his
query = him
autocomplete suggestion -->
query = h
autocomplete suggestion --> her him his
query = hi
autocomplete suggestion --> him his
query = hit
autocomplete suggestion -->
query = h
autocomplete suggestion --> her him his
query = hi
autocomplete suggestion --> him his hit
query = him
autocomplete suggestion --> him
query = h
autocomplete suggestion --> him her his
query = hi
autocomplete suggestion --> him his hit

#include <iostream>
#include <vector>
using namespace std;

vector<vector<string>> findQueryResults(vector<char> searchQuery){
    // your code goes here
    vector<vector<string>> result;
    return result;
}

#include <vector>
#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

// Definition of a trie node
class TrieNode
{
    public:
       	// key is the char and value if the trie node
        unordered_map<char, TrieNode*> children;
       	// key is the complete word and it's count is the value
        unordered_map<string, int> counter;
};

class Trie
{
    public:
        TrieNode * root;
        Trie()
        {
            root = new TrieNode();
        }
    
        string prefix;
    
       	// insert the character in the trie
        vector<string> insert(char c)
        {
           	// on encoutering a new line chacrater
           	// update the prefix count in trie
           	// reset prefix
            if (c == '\n')
            {
                add(prefix, 1);
                prefix.clear();
                return {};
    
            }
    
            prefix += c;
            cout << "query = " << prefix << endl;
            TrieNode *curr = root;
            for (char ch: prefix)
            {
               	// if prefix not found
               	// return empty array
                if (!curr->children[ch])
                {
                    return {};
    
                }
    
                curr = curr->children[ch];
            }
    
           	// use a priority queue for sorting
            priority_queue<pair<int, string>, vector< pair<int, string>>, compare> pq;
           	// insert words and their frequency in priority queue
            for (auto p: curr->counter)
            {
                pq.push({ p.second, p.first });
            }
    
            vector<string> autocomplete;
    
           	// fetch the top three words from priority queue
            for (int i = 0; i < 3 && !pq.empty(); i++)
            {
                autocomplete.push_back(pq.top().second);
                pq.pop();
            }
    
            return autocomplete;
        }
    
       	// custom comparator
       	// for sorting data based on frequency
       	// and then alphabetical order
        struct compare
        {
            bool operator()(pair<int, string> &s1, pair<int, string> &s2)
            {
                return s1.first < s2.first || (s1.first == s2.first && s1.second.compare(s2.second) > 0);
            }
        };
    
       	// increment the frequency 
       	// of the word in trie
        void add(string word, int frequency)
        {
            TrieNode *curr = root;
            for (char c: word)
            {
                if (!curr->children[c])
                {
                    curr->children[c] = new TrieNode();
                }
    
                curr = curr->children[c];
                curr->counter[word] += frequency;
            }
        }
};

vector<vector < string>> findQueryResults(vector<char> searchQuery)
{
    vector<vector < string>> result;

   	// intialize a new trie
    Trie *trie = new Trie();

    for (auto s: searchQuery)
    {
       	// insert query character to the trie
        vector<string> queryOutput = trie->insert(s);
        result.push_back(queryOutput);
        if (s == '\n')
            continue;
        cout<<"autocomplete suggestion -->";
        for (auto a: queryOutput)
            cout << a << " ";
        cout << endl;
    }

    return result;
}

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    static List<List<String>> findQueryResults(List<Character> searchQuery){
        // your code goes here
        List<List<String>> results = new ArrayList<>();
        return results;
    }
}

import java.util.*;
import java.lang.*;
import java.io.*;

class Pair
{
    int key;
    String value;
   	//Constructor of the class  
    public Pair(int key, String value)
    {
        this.key = key;
        this.value = value;
    }

    public int getKey()
    {
        return this.key;
    }

    public String getValue()
    {
        return this.value;
    }
}

// Definition of a trie node
class TrieNode
{
   	// key is the char and value is the trie node
    HashMap<Character, TrieNode> children = new HashMap < > ();
   	// key is the complete word and it's count is the value
    HashMap<String, Integer> counter = new HashMap < > ();
}

class Trie
{
    TrieNode root = new TrieNode();
    String prefix = "";

   	// insert the character in the trie
    List<String> insert(char c)
    {
       	// on encoutering a new line chacrater
       	// update the prefix count in trie
       	// reset prefix
        if (c == '\n')
        {
            add(prefix, 1);
            prefix = "";
            return Collections.<String> emptyList();
        }

        prefix += c;
        System.out.println("query " + prefix);

        TrieNode curr = root;

        for (char ch: prefix.toCharArray())
        {
           	// if prefix not found
           	// return empty array
            if (curr.children.get(ch) == null)
            {
                return Collections.<String> emptyList();
            }

            curr = curr.children.get(ch);
        }

       	// use a priority queue for sorting
        PriorityQueue<Pair> pq = new PriorityQueue<Pair> (new Comparator<Pair> ()
        {
           	// custom comparator
           	// for sorting data based on frequency
           	// and then alphabetical order
            public int compare(Pair s1, Pair s2)
            {
                if (s1.getKey() < s2.getKey() ||
                    (s1.getKey() == s2.getKey() && s1.getValue().compareTo(s2.getValue()) > 0))
                {
                    return 1;
                }
                else
                {
                    return -1;
                }
            } });

       	// insert words and their frequency in priority queue
        HashMap<String, Integer> counterMap = curr.counter;

        for (String key: counterMap.keySet())
        {
            pq.add(new Pair(counterMap.get(key), key));
        }

        List<String> autocomplete = new ArrayList < > ();

       	// fetch the top three words from priority queue
        for (int i = 0; i < 3 && pq.size() > 0; i++)
        {
            autocomplete.add(pq.poll().getValue());
        }

        return autocomplete;
    }

   	// increment the frequency 
   	// of the word in trie
    void add(String word, int frequency)
    {
        TrieNode curr = root;
        for (char c: word.toCharArray())
        {
            if (curr.children.get(c) == null)
            {
                curr.children.put(c, new TrieNode());
            }

            curr = curr.children.get(c);
            curr.counter.put(word, curr.counter.getOrDefault(word, 0) + frequency);
        }
    }
}

class Solution
{
    static List<List < String>> findQueryResults(List<Character> searchQuery)
    {
        List<List < String>> results = new ArrayList < > ();
       	// intialize a new trie
        Trie trie = new Trie();

        for (char c: searchQuery)
        {
           	//insert query character to the trie

            List<String> queryOutput = trie.insert(c);
            results.add(queryOutput);
            if (c == '\n')
                continue;
            System.out.print("autocomplete suggestion --> ");
            for (String a: queryOutput)
                System.out.print(a + " ");
            System.out.println();
        }

        return results;
    }
}

Java

Solve a hard-level problem for designing search auto-complete that suggests keywords based on search history using tries. 

Search History-Based Auto-Complete

Solve a hard-level problem for designing search auto-complete that suggests keywords based on search history using tries.

Introduction to Tries

Prefix Search

Suffix Search

Bitwise Tries

Pattern Matching

File Systems

Trie Traversal

Search Engine

Miscellaneous

Conclusion

Search History-Based Auto-Complete