Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Typescript - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the Trie node children.

DSA Typescript

if (!node.children.has(word[i])) {
  node.children.set(word[i], new [1]());
}

Drag options to blanks, or click blank then click option'

ATrieNode

BObject

CSet

DArray

Attempts:

3 left

💡 Hint

Common Mistakes

Using Object/Set/Array instead of TrieNode for the child node.

Confusing with the Map structure used for children.

We create a new TrieNode() as the child node for the current character word[i].

2fill in blank

medium

Complete the code to check if a word exists in the Trie.

DSA Typescript

for (let i = 0; i < word.length; i++) {
  if (!node.children.has(word[i])) {
    return false;
  }
  node = node.children.get([1])!;
}
return node.isEndOfWord;

Drag options to blanks, or click blank then click option'

Aword

Bword[i]

Ci

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'i' instead of 'word[i]' which is an index, not a key.

Using 'node' which is the current node, not the child.

We get the child node corresponding to the current character word[i] to continue traversal.

3fill in blank

hard

Fix the error in the code to correctly count how many words start with a given prefix.

DSA Typescript

function countPrefix(node: TrieNode, prefix: string): number {
  for (let i = 0; i < prefix.length; i++) {
    if (!node.children.has(prefix[i])) {
      return 0;
    }
    node = node.children.get(prefix[i])!;
  }
  return [1];
}

Drag options to blanks, or click blank then click option'

Anode.count

Bnode.isEndOfWord

Cnode.children.size

Dprefix.length

Attempts:

3 left

💡 Hint

Common Mistakes

Returning isEndOfWord which is a boolean, not a count.

Returning children.size which counts child nodes, not words.

We return node.count which tracks how many words share this prefix in the Trie.

4fill in blank

hard

Fill all three blanks to create a Trie node class with a children map, prefix count, and a boolean flag for word end.

DSA Typescript

class TrieNode {
  children: [1]<string, TrieNode>;
  count: [3];
  isEndOfWord: [2];

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

Drag options to blanks, or click blank then click option'

AMap

BSet

Cboolean

Dnumber

Attempts:

3 left

💡 Hint

Common Mistakes

Using Set instead of Map for children.

Using boolean instead of number for count.

Using number instead of boolean for isEndOfWord.

The children are stored in a Map<string, TrieNode>, count is number for prefix frequency, and isEndOfWord is a boolean flag.

5fill in blank

hard

Fill all three blanks to implement a function that inserts a word into the Trie and updates counts.

DSA Typescript

function insertWord(root: TrieNode, word: string): void {
  let node = root;
  for (let i = 0; i < word.length; i++) {
    if (!node.children.has(word[i])) {
      node.children.set(word[i], new [1]());
    }
    node = node.children.get(word[i])!;
    node.[2] += 1;
  }
  node.[3] = true;
}

Drag options to blanks, or click blank then click option'

ATrieNode

Bcount

CisEndOfWord

Dchildren

Attempts:

3 left

💡 Hint

Common Mistakes

Using children instead of count for counting prefixes.

Not marking isEndOfWord true at the end.

Wrong type for new node.

We create new TrieNode instances, increment the count property on each node, and mark isEndOfWord true at the end.

Practice

1. Why do we use a Trie data structure instead of a Hash Map for storing many strings?

easy

A. Because Trie is faster for exact string lookups than Hash Maps

B. Because Trie uses less memory than a Hash Map for all cases

C. Because Hash Maps cannot store strings as keys

D. Because Trie efficiently supports prefix-based searches and auto-completion

Solution

1. Step 1: Understand Trie and Hash Map capabilities

   Trie stores strings in a tree form, allowing quick prefix searches. Hash Maps store keys but do not support prefix queries efficiently.

2. Step 2: Compare use cases for prefix search

   Trie can find all strings starting with a prefix quickly, which Hash Maps cannot do without scanning all keys.

3. Final Answer:

   Because Trie efficiently supports prefix-based searches and auto-completion -> Option D

4. Quick Check:

   Prefix search = Trie [OK]

Hint: Trie = prefix search; Hash Map = exact key lookup [OK]

Common Mistakes:

• Thinking Hash Maps support prefix search efficiently
• Assuming Trie always uses less memory
• Believing Hash Maps cannot store strings as keys

2. Which of the following is the correct TypeScript syntax to declare a Trie node with children as a Map of characters to nodes?

easy

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

B. class TrieNode { children: Map = new Map(); }

C. class TrieNode { children: Map = new Map(); }

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

Solution

1. Step 1: Understand Map type declaration in TypeScript

   Map keys and values must be typed as Map. Here keys are characters (string), values are TrieNode.

2. Step 2: Check each option's syntax

   class TrieNode { children: Map = new Map(); } correctly declares children as Map initialized with new Map(). Others have wrong generic order or types.

3. Final Answer:

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

4. Quick Check:

   Map syntax correct [OK]

Hint: Map with correct order and initialization [OK]

Common Mistakes:

• Swapping key and value types in Map
• Not initializing Map with new Map()
• Using wrong generic types for Map

3. Given the following TypeScript Trie insertion code snippet, what will be the output after inserting words ['cat', 'car', 'dog'] and searching for prefix 'ca'?

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

class Trie {
  root = new TrieNode();

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

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

const trie = new Trie();
['cat', 'car', 'dog'].forEach(w => trie.insert(w));
console.log(trie.startsWith('ca'));

medium

A. undefined

B. true

C. false

D. Error at runtime

Solution

1. Step 1: Insert words into Trie

   Words 'cat', 'car', and 'dog' are inserted. 'ca' prefix nodes are created for 'c' and 'a'.

2. Step 2: Check startsWith for 'ca'

   Traversal finds nodes for 'c' and 'a' successfully, so returns true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Prefix 'ca' exists = true [OK]

Hint: If prefix nodes exist, startsWith returns true [OK]

Common Mistakes:

• Confusing startsWith with exact word search
• Assuming isEnd must be true for prefix check
• Expecting false if prefix is partial

4. The following TypeScript Trie search method is intended to check if a word exists. What is the bug?

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

medium

A. It always returns false even if word exists

B. It throws an error when word is empty

C. It returns true for any prefix, not full word

D. It does not check if node is null

Solution

1. Step 1: Analyze the return statement after loop

   The method returns false after the loop without checking if the last node marks end of a word.

2. Step 2: Identify missing isEnd check

   It should return node.isEnd to confirm full word presence, not just prefix.

3. Final Answer:

   It always returns false even if word exists -> Option A

4. Quick Check:

   Missing isEnd check causes always false [OK]

Hint: Check isEnd after traversal to confirm full word [OK]

Common Mistakes:

• Returning false without checking isEnd
• Confusing prefix search with full word search
• Ignoring empty string edge case

5. You want to store a large dictionary of words and quickly find all words starting with a given prefix. Why is a Trie better than a Hash Map for this, and what is a limitation of Hash Map in this scenario?

hard

A. Trie uses less memory than Hash Map; Hash Map cannot store string keys longer than 10 characters.

B. Trie supports exact word search only; Hash Map supports prefix search but slower.

C. Trie stores words in a prefix tree allowing fast prefix queries; Hash Map can't efficiently find keys by prefix without scanning all keys.

D. Trie is slower for insertion; Hash Map is faster for prefix search.

Solution

1. Step 1: Understand Trie prefix storage

   Trie organizes words by shared prefixes in a tree, enabling quick retrieval of all words with a prefix.

2. Step 2: Understand Hash Map limitations

   Hash Map stores keys without order, so prefix search requires checking all keys, which is inefficient.

3. Final Answer:

   Trie stores words in a prefix tree allowing fast prefix queries; Hash Map can't efficiently find keys by prefix without scanning all keys. -> Option C

4. Quick Check:

   Prefix search efficiency = Trie advantage [OK]

Hint: Trie = fast prefix search; Hash Map = no prefix search [OK]

Common Mistakes:

• Thinking Hash Map supports prefix search efficiently
• Assuming Trie uses less memory always
• Confusing exact search with prefix search