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

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why is a Trie preferred over a Hash Map for prefix searches?

Imagine you want to find all words starting with 'app' in a large dictionary. Why is a Trie better than a Hash Map for this task?

A Trie stores characters in a tree structure allowing efficient prefix search, while Hash Map cannot efficiently find keys by prefix.

B Hash Map uses less memory than Trie, so it is better for prefix searches.

C Trie is slower than Hash Map for prefix searches because it stores entire words.

D Hash Map can find prefixes faster because it hashes the prefix directly.

💡 Hint

Think about how each data structure organizes keys and how that affects searching by starting letters.

A Trie stores strings character by character in a tree, making it easy to find all words sharing a prefix by traversing the tree. A Hash Map stores whole keys and cannot efficiently find keys by partial prefixes.

❓ Predict Output

intermediate

Output of Trie prefix search vs Hash Map lookup

Given the following TypeScript code, what is the output?

DSA Typescript

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

class Trie {
  root = 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;
  }

  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;
  }
}

const trie = new Trie();
trie.insert('apple');
trie.insert('app');

const hashMap = new Map<string, boolean>();
hashMap.set('apple', true);
hashMap.set('app', true);

console.log(trie.startsWith('app'));
console.log(hashMap.has('app'));
console.log(hashMap.has('ap'));
console.log(trie.startsWith('ap'));

A

true
true
false
true

B

true
true
true
true

C

false
true
false
false

D

true
false
false
true

💡 Hint

Check how Trie and Hash Map handle prefixes and exact keys differently.

Trie.startsWith('app') returns true because 'app' is a prefix in the Trie. Hash Map.has('app') returns true because 'app' is a key. Hash Map.has('ap') returns false because 'ap' is not a key. Trie.startsWith('ap') returns true because 'ap' is a prefix of inserted words.

🔧 Debug

advanced

Why does this Trie prefix search fail for some prefixes?

Find the bug in this TypeScript Trie startsWith method that causes it to return false for some prefixes that exist.

DSA Typescript

class TrieNode {
  children: {[key: string]: TrieNode} = {};
  isWord = false;
}

class Trie {
  root = new TrieNode();

  insert(word: string) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isWord = true;
  }

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

const trie = new Trie();
trie.insert('hello');
console.log(trie.startsWith('hel'));

A The startsWith method should check for isWord at each character.

B The startsWith method incorrectly returns node.isWord instead of true after prefix traversal.

C The children property should be a Map instead of an object.

D The insert method does not add nodes for each character properly.

💡 Hint

Think about what startsWith should return after successfully finding the prefix path.

startsWith should return true if the prefix path exists, regardless of whether the prefix itself is a complete word. Returning node.isWord causes false for prefixes that are not complete words.

❓ Predict Output

advanced

Memory usage difference between Trie and Hash Map for many strings

Consider storing 1000 English words in a Trie and a Hash Map. Which statement about memory usage is true?

A Hash Map uses less memory because it stores only keys without extra nodes.

B Both use the same memory because they store all words fully.

C Trie uses less memory because it shares common prefixes among words.

D Trie uses more memory because it stores each character as a separate node.

💡 Hint

Think about how words with common beginnings are stored in each structure.

Trie shares nodes for common prefixes, reducing memory for overlapping parts. Hash Map stores each key fully, so it uses more memory when many words share prefixes.

🧠 Conceptual

expert

Why can't Hash Maps efficiently support autocomplete features like Tries?

Autocomplete requires finding all words starting with a prefix quickly. Why is a Trie better suited than a Hash Map for this feature?

A Hash Map automatically sorts keys, making prefix search faster than Trie.

B Hash Map can store prefixes as keys, so it is equally efficient as Trie for autocomplete.

C Trie is slower because it needs to check each character, while Hash Map hashes the prefix directly.

D Trie organizes words by characters allowing traversal to prefix node and collecting descendants; Hash Map lacks this structure and requires scanning all keys.

💡 Hint

Consider how each data structure organizes and accesses keys related by prefixes.

Trie nodes represent characters and link to children, so after reaching the prefix node, all words with that prefix are descendants. Hash Map stores keys independently, so finding all keys with a prefix requires checking every key, which is inefficient.