Interview Cheat Sheets | Tries Cheat Sheet

December 30th, 2023

Introduction

This article will serve to further summarize the excellent overview of recursion from the tech interview handbook.

Overviews

Tries, also known as prefix trees, are specialized trees designed to enhance the efficiency of searching and storing strings. They find applications in various scenarios like searches and autocomplete features.

TypeScript Implementation of a Trie Class

class TrieNode {
  children: Map<string, TrieNode>;
  isEndOfWord: boolean;

  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

class Trie {
  root: TrieNode;

  constructor() {
    this.root = new TrieNode();
  }

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEndOfWord = true;
  }

  search(word: string): boolean {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char)!;
    }
    return node.isEndOfWord;
  }

  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char)!;
    }
    return true;
  }

  delete(word: string): void {
    const deleteHelper = (node: TrieNode, depth: number): boolean => {
      if (depth === word.length) {
        if (!node.isEndOfWord) {
          return false; // Word not found
        }
        node.isEndOfWord = false;

        return node.children.size === 0; // Check if node has no children
      }

      const char = word[depth];
      if (!node.children.has(char)) {
        return false; // Word not found
      }

      const shouldDeleteCurrentNode = deleteHelper(
        node.children.get(char)!,
        depth + 1
      );

      if (shouldDeleteCurrentNode) {
        node.children.delete(char);
        return node.children.size === 0;
      }

      return false;
    };

    deleteHelper(this.root, 0);
  }
}

// Example usage:
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple")); // Output: true
console.log(trie.search("app")); // Output: false
console.log(trie.startsWith("app")); // Output: true
trie.insert("app");
console.log(trie.search("app")); // Output: true
trie.delete("app");
console.log(trie.search("app")); // Output: false

Time Complexity

For operations where m is the length of the string involved.

Operation	Big-O
Search	O(m)
Insert	O(m)
Remove	O(m)

Corner Cases

Searching for a string in an empty trie
Inserting empty strings into a trie

Techniques

Preprocessing a dictionary of words into a trie can significantly enhance the efficiency of searching. For a word of length k among n words, searching becomes O(k) instead of O(n).

Essential Questions

Implement Trie (Prefix Tree) - My solution