Interview Questions — Implementing an Autocomplete System Using a Trie Data Structure

Photo by Zach Reiner on Unsplash

Question

Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set with s as a prefix.

For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal].

Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries.

Explanation

Implementing an autocomplete system requires creating a data structure for efficient prefix searching. A popular choice for this kind of task is the Trie data structure. A Trie is a search tree — an ordered tree data structure that stores a dynamic set or associative array where the keys are usually strings. Each node in the Trie represents a single character of a string, and the strings in the dataset are stored so that common prefixes are shared.

Solution with Javascript

1. Trie Node Structure: Create a class or a constructor function for Trie nodes. Each node should contain a character, a map (or object) to child nodes, and a flag to mark the end of a word.
2. Insertion Method: Implement a method to insert words into the Trie. This method should iterate over each character of the inserted word, creating new nodes for characters not already present in the Trie.
3. Search Method: Implement a method to search for all words in the Trie with a given prefix. This involves finding the node in the Trie that represents the last character of the prefix and then recursively finding all words that stem from that node.

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }
    findAllWithPrefix(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return []; // Prefix not in Trie
            }
            node = node.children[char];
        }
        return this._findAllWords(node, prefix);
    }
    _findAllWords(node, prefix) {
        let words = [];
        if (node.isEndOfWord) {
            words.push(prefix);
        }
        for (let char in node.children) {
            words = words.concat(this._findAllWords(node.children[char], prefix + char));
        }
        return words;
    }
}
// Example usage:
const trie = new Trie();
trie.insert("dog");
trie.insert("deer");
trie.insert("deal");
console.log(trie.findAllWithPrefix("de")); // Should print ["deer", "deal"]

Solution with PHP

Implementing an autocomplete system in PHP involves a similar approach to the one used in other programming languages, with adjustments for PHP’s syntax and standard library functions. While PHP doesn’t have a built-in Trie data structure like some other languages might, you can still implement one manually or use associative arrays (dictionaries) creatively to simulate similar functionality for this specific use case.

However, for a straightforward implementation, especially if the dataset is small or if performance is acceptable with more superficial structures, you can use associative arrays to store the set of query strings and then filter them based on the prefix.

<?php
function autocomplete($query, $dictionary) {
  $results = [];
  foreach ($dictionary as $word) {
          // If the word starts with the query string, add it to the results
          if (strpos($word, $query) === 0) {
              $results[] = $word;
          }
      }
      return $results;
  }
  $dictionary = ["dog", "deer", "deal"];
  $query = "de";
  // Test the autocomplete function
  $results = autocomplete($query, $dictionary);
  print_r($results); // Should output ['deer', 'deal']
?>

Implementing an autocomplete system with a Trie in PHP offers a more efficient solution for prefix matching, especially as the dataset grows.

<?php
class TrieNode {
    public $children = [];
    public $isEndOfWord = false;
    public function __construct() {
        $this->children = array_fill(0, 26, null);
        $this->isEndOfWord = false;
    }
}
class Trie {
    private $root;
    public function __construct() {
        $this->root = new TrieNode();
    }
    // Function to insert a word into the Trie
    public function insert($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $index = ord($word[$i]) - ord('a');
            if (!isset($node->children[$index])) {
                $node->children[$index] = new TrieNode();
            }
            $node = $node->children[$index];
        }
        $node->isEndOfWord = true;
    }
    // Function to search the Trie and find all words with the given prefix
    public function getWordsWithPrefix($prefix) {
        $node = $this->root;
        $words = [];
        for ($i = 0; $i < strlen($prefix); $i++) {
            $index = ord($prefix[$i]) - ord('a');
            if (!isset($node->children[$index])) {
                return []; // Prefix not found
            }
            $node = $node->children[$index];
        }
        $this->findAllWords($node, $prefix, $words);
        return $words;
    }
    // Helper function to recursively find all words in the Trie that start with the given prefix
    private function findAllWords($node, $word, &$words) {
        if ($node->isEndOfWord) {
            $words[] = $word;
        }
        for ($i = 0; $i < 26; $i++) {
            if (isset($node->children[$i])) {
                $this->findAllWords($node->children[$i], $word . chr($i + ord('a')), $words);
            }
        }
    }
}
// Example usage
$trie = new Trie();
$trie->insert("dog");
$trie->insert("deer");
$trie->insert("deal");
// Find and print words with prefix "de"
$prefix = "de";
$wordsWithPrefix = $trie->getWordsWithPrefix($prefix);
print_r($wordsWithPrefix);
?>

Follow me on Instagram, Facebook or Twitter if you like to keep posted about tutorials, tips and experiences from my side.

You can support me from Patreon, Github Sponsors, Ko-fi or Buy me a coffee