Trie vs Hash Map for Prefix Matching in DSA Typescript - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Search Using Trie

What is the output of the following TypeScript code that uses a Trie to find words with a given prefix?

DSA Typescript

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

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string) {
    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.isWord = true;
  }

  searchPrefix(prefix: string): string[] {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return [];
      node = node.children.get(char)!;
    }
    const results: string[] = [];
    const dfs = (currNode: TrieNode, path: string) => {
      if (currNode.isWord) results.push(path);
      for (const [ch, nextNode] of currNode.children) {
        dfs(nextNode, path + ch);
      }
    };
    dfs(node, prefix);
    return results;
  }
}

const trie = new Trie();
['apple', 'app', 'apex', 'bat', 'bath'].forEach(w => trie.insert(w));
console.log(trie.searchPrefix('ap'));

A ["apple", "apex"]

B ["app", "apple", "apex"]

C ["app", "apex"]

D ["bat", "bath"]

💡 Hint

Think about all words starting with 'ap' inserted into the trie.

The trie stores words 'apple', 'app', and 'apex' starting with 'ap'. The searchPrefix method collects all words starting with the prefix 'ap'.

❓ Predict Output

intermediate

Output of Prefix Search Using Hash Map

What is the output of the following TypeScript code that uses a Hash Map to find words with a given prefix?

DSA Typescript

const words = ['app', 'apple', 'apex', 'bat', 'bath'];
const prefix = 'ap';
const result = words.filter(word => word.startsWith(prefix));
console.log(result);

A ["bat", "bath"]

B ["apple", "apex"]

C ["app", "apex"]

D ["app", "apple", "apex"]

💡 Hint

Filter words that start with the prefix 'ap'.

The filter method returns all words starting with 'ap' from the array.

🧠 Conceptual

advanced

Why Use Trie Over Hash Map for Prefix Matching?

Which of the following is the main advantage of using a Trie over a Hash Map for prefix matching in large datasets?

A Trie allows efficient prefix search with time complexity proportional to prefix length, not dataset size.

B Trie uses less memory than a Hash Map for storing all words.

C Hash Map cannot store strings as keys.

D Trie automatically sorts words alphabetically without extra steps.

💡 Hint

Consider how search time depends on prefix length vs number of words.

Trie search time depends on prefix length only, making it efficient for prefix queries in large datasets.

🧠 Conceptual

advanced

Memory Usage Comparison Between Trie and Hash Map

Which statement best describes memory usage when comparing Trie and Hash Map for storing many words?

A Hash Map uses more memory because it stores characters individually.

B Hash Map always uses less memory because it stores only full words as keys.

C Trie can use more memory due to storing nodes for each character, especially with sparse data.

D Trie uses less memory because it compresses common prefixes automatically.

💡 Hint

Think about how tries store each character as a node.

Tries store nodes for each character, which can increase memory usage if many prefixes are unique.

🔧 Debug

expert

Identify the Bug in Trie Prefix Search Implementation

Given the following TypeScript Trie prefix search code, what error will it produce when searching for prefix 'ap'?

DSA Typescript

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

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string) {
    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.isWord = true;
  }

  searchPrefix(prefix: string): string[] {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return [];
      node = node.children.get(char)!;
    }
    const results: string[] = [];
    const dfs = (currNode: TrieNode, path: string) => {
      if (currNode.isWord) results.push(path);
      for (const [ch, nextNode] of currNode.children) {
        dfs(nextNode, path + ch);
      }
    };
    dfs(node, prefix);
    return results;
  }
}

const trie = new Trie();
['apple', 'app', 'apex', 'bat', 'bath'].forEach(w => trie.insert(w));
console.log(trie.searchPrefix('ap'));

A No error; outputs ["app", "apple", "apex"]

B TypeError because node.children is undefined

C Stack overflow due to infinite recursion in dfs

D SyntaxError due to missing return statement in dfs

💡 Hint

Check how dfs is called and if recursion ends properly.

The code correctly implements dfs with base case and recursion, so no error occurs and output is correct.

Practice

1. Which data structure is generally more efficient for prefix matching in a large set of strings?

easy

A. Trie, because it stores prefixes explicitly and allows fast prefix queries

B. Hash Map, because it stores keys with constant time lookup

C. Array, because it stores elements in order

D. Linked List, because it allows sequential access

Solution

1. Step 1: Understand prefix matching requirements

   Prefix matching means finding all strings that start with a given prefix efficiently.

2. Step 2: Compare Trie and Hash Map for prefix queries

   Trie stores prefixes explicitly in its structure, allowing quick traversal to all words sharing a prefix. Hash Map only allows exact key lookups, not prefix searches.

3. Final Answer:

   Trie, because it stores prefixes explicitly and allows fast prefix queries -> Option A

4. Quick Check:

   Prefix matching = Trie [OK]

Hint: Trie stores prefixes; Hash Map does not support prefix search [OK]

Common Mistakes:

• Thinking Hash Map supports prefix search efficiently
• Confusing prefix matching with exact key lookup
• Assuming arrays or linked lists are efficient for prefix queries

2. Which of the following TypeScript code snippets correctly initializes a Trie node for prefix matching?

easy

A. class TrieNode { children: object = {}; isEnd: number = 0; }

B. class TrieNode { children: string[] = []; isEnd: boolean = true; }

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

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

Solution

1. Step 1: Identify correct data types for TrieNode properties

   Children should map characters (string) to TrieNode objects. isEnd should be boolean to mark word end.

2. Step 2: Check each option's correctness

   class TrieNode { children: Map = new Map(); isEnd: boolean = false; } uses Map and boolean isEnd, which is correct. Others use wrong types or incorrect isEnd values.

3. Final Answer:

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

4. Quick Check:

   TrieNode children = Map [OK]

Hint: Trie children map chars to nodes; isEnd is boolean [OK]

Common Mistakes:

• Using array instead of Map for children
• Setting isEnd as number instead of boolean
• Mapping children with wrong key or value types

3. What will be the output of the following TypeScript code snippet?

const map = new Map();
map.set('app', true);
map.set('apple', true);
console.log(map.has('app'));
console.log(map.has('appl'));

medium

A. false\ntrue

B. true\ntrue

C. false\nfalse

D. true\nfalse

Solution

1. Step 1: Understand Map key lookups

   Map.has(key) returns true only if exact key exists. 'app' and 'apple' are keys, 'appl' is not.

2. Step 2: Evaluate console.log outputs

   map.has('app') is true; map.has('appl') is false because 'appl' is not a key.

3. Final Answer:

   true\nfalse -> Option D

4. Quick Check:

   Exact keys only: 'app' true, 'appl' false [OK]

Hint: Map.has checks exact keys, not prefixes [OK]

Common Mistakes:

• Assuming map.has supports prefix matching
• Confusing keys 'appl' and 'apple'
• Expecting true for partial keys

4. Consider this buggy TypeScript Trie insert method:

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

What is the main issue causing a runtime error?

medium

A. node.children.get(char) can return undefined, causing assignment to node to fail

B. The loop variable char is not declared properly

C. The isEnd property is set before the loop

D. The root node is not initialized

Solution

1. Step 1: Analyze node.children.get(char) usage

   Even after checking node.children.has(char), node.children.get(char) can theoretically return undefined if the Map is modified concurrently or due to incorrect initialization.

2. Step 2: Identify runtime error cause

   Assigning undefined to node causes subsequent property access to fail, leading to runtime error.

3. Final Answer:

   node.children.get(char) can return undefined, causing assignment to node to fail -> Option A

4. Quick Check:

   Ensure node.children.get(char) is not undefined before assignment [OK]

Hint: Check that node.children.get(char) returns a valid TrieNode before assignment [OK]

Common Mistakes:

• Thinking Map.get() returns undefined despite prior has() check
• Overlooking need for root initialization in constructor
• Assuming object-style children access instead of Map methods

5. You want to implement a prefix search feature that returns all words starting with a given prefix from a large dictionary. Which approach is best and why?

// Approach 1: Store all words in a Hash Map and check each key for prefix match
// Approach 2: Build a Trie from all words and traverse to prefix node to collect matches

hard

A. Approach 1 is better because Hash Map lookups are O(1) and prefix checks are fast

B. Approach 2 is better because Trie traversal to prefix node is efficient and collects matches quickly

C. Both approaches are equally efficient for prefix search

D. Neither approach works well; use a sorted array with binary search instead

Solution

1. Step 1: Evaluate Approach 1 (Hash Map with prefix checks)

   Hash Map allows O(1) exact lookups but requires checking every key for prefix, which is O(n) and inefficient for large data.

2. Step 2: Evaluate Approach 2 (Trie traversal)

   Trie stores prefixes explicitly; traversing to prefix node is O(k) where k is prefix length, then collecting matches is efficient.

3. Step 3: Compare efficiency and scalability

   Trie approach scales better for prefix search due to structured prefix storage and avoids scanning all keys.

4. Final Answer:

   Approach 2 is better because Trie traversal to prefix node is efficient and collects matches quickly -> Option B

5. Quick Check:

   Prefix search = Trie traversal [OK]

Hint: Trie stores prefixes; Hash Map needs full scan for prefix [OK]

Common Mistakes:

• Assuming Hash Map prefix checks are fast
• Ignoring Trie traversal efficiency
• Thinking both approaches perform the same