Longest Word in Dictionary Using Trie in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Word Found Using Trie

What is the output of the following TypeScript code that builds a Trie from a list of words and finds the longest word where all prefixes are also words in the list?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: boolean = false;
}

class Trie {
  root: TrieNode = 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.isEnd = true;
  }

  longestWord(): string {
    let result = "";
    const dfs = (node: TrieNode, path: string): void => {
      if (path.length > result.length || (path.length === result.length && path < result)) {
        result = path;
      }
      for (const [char, child] of [...node.children.entries()].sort((a, b) => a[0].localeCompare(b[0]))) {
        if (child.isEnd) {
          dfs(child, path + char);
        }
      }
    };
    dfs(this.root, "");
    return result;
  }
}

const words = ["a", "app", "ap", "apply", "apple", "appl", "b", "ban", "banana"];
const trie = new Trie();
for (const w of words) {
  trie.insert(w);
}
console.log(trie.longestWord());

A "apple"

B "apply"

C "appl"

D "banana"

💡 Hint

Think about which word has all its prefixes present in the list and is the longest.

The code builds a Trie and searches for the longest word such that every prefix of the word is also a word in the list. Among the given words, "apple" has prefixes "a", "ap", "app", "appl" all present. "apply" is not valid because "appl" is present but "apply" is not marked as end in the Trie (not inserted as a complete word). "banana" is longer but prefixes like "banan" are missing.

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the purpose of the 'isEnd' property in a Trie node when finding the longest word in a dictionary?

A It points to the parent node in the Trie.

B It counts how many words pass through this node.

C It stores the character value of the node.

D It marks the node as the end of a valid word in the dictionary.

💡 Hint

Think about how the Trie knows a word ends at a node.

The 'isEnd' boolean indicates that the path from the root to this node forms a complete word in the dictionary. This helps in checking if prefixes are valid words.

🔧 Debug

advanced

Identify the Bug in Trie Longest Word Search

The following code attempts to find the longest word in a dictionary using a Trie, but it returns an empty string. What is the bug?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: boolean = false;
}

class Trie {
  root: TrieNode = 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.isEnd = true;
  }

  longestWord(): string {
    let result = "";
    const dfs = (node: TrieNode, path: string): void => {
      if (path.length > result.length || (path.length === result.length && path < result)) {
        result = path;
      }
      for (const [char, child] of node.children.entries()) {
        if (child.isEnd) {
          dfs(child, path + char);
        }
      }
    };
    dfs(this.root, "");
    return result;
  }
}

const words = ["a", "app", "ap", "apply", "apple", "appl"];
const trie = new Trie();
for (const w of words) {
  trie.insert(w);
}
console.log(trie.longestWord());

A The root node's isEnd is false, so DFS starts from a node that is not a valid prefix, causing no updates to result.

B The DFS does not sort children, so traversal order is random and may miss the lexicographically smallest word.

C The insert method does not mark the last node as isEnd = true, so no words are recognized as complete.

D The DFS does not check if the current node is the root before updating the result, causing empty string to be returned.

💡 Hint

Consider what happens at the root node and how the DFS updates the result.

The DFS starts from the root node which has isEnd = false. Since the DFS only continues down children nodes that have isEnd = true, and the root is not marked as a word, the initial call does not update the result. The root should be considered as a valid starting point or marked as isEnd = true to allow traversal.

📝 Syntax

advanced

Identify Syntax Error in Trie Implementation

Which option contains a syntax error that will prevent the TypeScript Trie code from compiling?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: boolean = false;
}

class Trie {
  root: TrieNode = 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.isEnd = true;
  }

  longestWord(): string {
    let result = "";
    const dfs = (node: TrieNode, path: string): void => {
      if (path.length > result.length || (path.length === result.length && path < result)) {
        result = path;
      }
      for (const [char, child] of [...node.children.entries()].sort()) {
        if (child.isEnd) {
          dfs(child, path + char);
        }
      }
    };
    dfs(this.root, "");
    return result;
  }
}

A Missing semicolon after 'node.isEnd = true' in insert method.

B Using 'sort()' directly on Map entries without a compare function causes a syntax error.

C The arrow function in dfs is missing a return type annotation.

D The exclamation mark '!' after get(char) is invalid syntax in TypeScript.

💡 Hint

Check how sorting is applied to Map entries in TypeScript.

Calling sort() on an array of Map entries without a compare function is valid syntax but may not sort as expected. However, in TypeScript, sorting Map entries requires a compare function to avoid errors. The other options are valid syntax: semicolons are optional, arrow functions can omit return type, and '!' is a valid non-null assertion operator.

🚀 Application

expert

Longest Word with All Prefixes Present - Result Count

Given the following list of words inserted into a Trie, how many words in the list qualify as the longest word where all prefixes are also present in the dictionary?

DSA Typescript

const words = ["a", "ap", "app", "appl", "apple", "apply", "b", "ban", "bana", "banan", "banana"];
// Assume Trie insertion and longest word logic as usual.

A 1

B 3

C 2

D 4

💡 Hint

Check which words have all prefixes present and are the longest among them.

Words "apple" and "banana" both have all prefixes present in the list. "apply" is invalid because "appl" is present but "apply" is not marked as a complete word in the dictionary (assuming it is). Here, "apply" is present, but "appl" is also present, so "apply" qualifies. So the longest words with all prefixes are "apple" and "banana" (both length 5 and 6 respectively). So count is 2.

Practice

1. What is the main purpose of using a Trie data structure when finding the longest word in a dictionary?

easy

A. To efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To count the total number of words

D. To reverse the words quickly

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by breaking them into characters and linking nodes for prefixes.

2. Step 2: Connect Trie to longest word search

   This structure allows quick prefix checks, which helps find the longest word built from other words.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is best for prefix-based word searches [OK]

Common Mistakes:

• Thinking Trie sorts words alphabetically
• Confusing Trie with simple arrays
• Assuming Trie counts words only

2. Which of the following TypeScript code snippets correctly initializes a Trie node with children and an end-of-word flag?

easy

A. class TrieNode { children: Map = new Map(); isEnd: boolean = false; }

B. class TrieNode { children: string[] = []; isEnd: number = 0; }

C. class TrieNode { children: object = {}; isEnd: string = 'false'; }

D. class TrieNode { children: Map = new Map(); isEnd: boolean = true; }

Solution

1. Step 1: Check children type

   Children should map characters (string) to TrieNode objects, so Map is correct.

2. Step 2: Check isEnd flag type

   isEnd should be boolean to mark word end, so boolean = false is correct.

3. Final Answer:

   class TrieNode { children: Map = new Map(); isEnd: boolean = false; } -> Option A

4. Quick Check:

   Correct types = class TrieNode { children: Map = new Map(); isEnd: boolean = false; } [OK]

Hint: Use Map and boolean for TrieNode [OK]

Common Mistakes:

• Using array instead of Map for children
• Using wrong types for isEnd flag
• Mixing key and value types in Map

3. Given the following TypeScript code snippet that inserts words into a Trie and finds the longest word, what will be the output?

const words = ["a", "app", "apple", "apply", "ap"];
const trie = new Trie();
words.forEach(word => trie.insert(word));
console.log(trie.findLongestWord());

medium

A. "a"

B. "apply"

C. "apple"

D. "app"

Solution

1. Step 1: Insert words into Trie

   Words "a", "app", "apple", "apply", "ap" are inserted. Trie stores prefixes for all.

2. Step 2: Find longest word with all prefixes present

   "app" has all prefixes present: "a", "ap", "app". "apple" and "apply" require "appl" which is not a word in the list.

3. Final Answer:

   "app" -> Option D

4. Quick Check:

   Longest word with all prefixes = "app" [OK]

Hint: Choose longest word with all prefixes present, lex smallest if tie [OK]

Common Mistakes:

• Choosing "apple" or "apply" without checking if "appl" is a word
• Ignoring that intermediate prefixes like "appl" must be full words
• Picking the overall longest word without prefix validation

4. Consider this buggy TypeScript code snippet for inserting words into a Trie:

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

What is the main issue causing a runtime error?

medium

A. The loop does not iterate over all characters

B. The isEnd flag is set before inserting nodes

C. node.children.get(char) can return undefined, causing node to be undefined

D. The children map is not initialized

Solution

1. Step 1: Analyze node update inside loop

   node.children.get(char) may return undefined if key missing, but code assumes it returns TrieNode.

2. Step 2: Identify cause of runtime error

   If undefined assigned to node, next iteration fails accessing children of undefined.

3. Final Answer:

   node.children.get(char) can return undefined, causing node to be undefined -> Option C

4. Quick Check:

   Undefined node from get() causes error [OK]

Hint: Check if get() can return undefined before assignment [OK]

Common Mistakes:

• Ignoring possibility of undefined from Map.get()
• Assuming loop skips characters
• Confusing isEnd flag placement

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"]. Using a Trie, which word will be the longest word in the dictionary where every prefix is also a word in the list?

hard

A. "banana"

B. "world"

C. "banan"

D. "worl"

Solution

1. Step 1: Check prefixes for "world"

   Prefixes: "w", "wo", "wor", "worl" all exist in list.

2. Step 2: Check prefixes for "banana" and "banan"

   "banana" and "banan" are missing shorter prefixes like "b" and "ba" which are not in the list.

3. Step 3: Compare valid longest words

   "world" is longest with all prefixes present; others longer but invalid.

4. Final Answer:

   "world" -> Option B

5. Quick Check:

   Longest word with all prefixes = "world" [OK]

Hint: Check all prefixes exist; longest valid word wins [OK]

Common Mistakes:

• Choosing "banana" ignoring missing prefix like "b"
• Confusing similar prefixes
• Not verifying all prefixes exist