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

Challenge - 5 Problems

🧠 Conceptual

intermediate

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

Which reason best explains why a Trie is more suitable than a Hash Map when searching for all words starting with a given prefix?

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

B A Hash Map uses less memory than a Trie, making it better for prefix searches.

C A Trie hashes the entire word, so it is faster than a Hash Map for any search.

D A Hash Map automatically sorts keys, so prefix search is faster than in a Trie.

💡 Hint

Think about how data is organized and accessed in each structure.

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

❓ Predict Output

intermediate

Output of prefix search using Trie vs Hash Map

Given the following code snippets, what is the output of searching for prefix 'app' in each data structure?

DSA Javascript

const words = ['apple', 'app', 'application', 'bat'];

// Trie prefix search result for 'app'
const trieResult = ['app', 'apple', 'application'];

// Hash Map keys
const hashMap = { apple: 1, app: 1, application: 1, bat: 1 };

// Hash Map prefix search simulation
const hashMapResult = Object.keys(hashMap).filter(word => word.startsWith('app'));

A

Trie result: ['app', 'apple', 'application']
Hash Map result: ['app', 'apple', 'application']

B

Trie result: []
Hash Map result: ['app', 'apple', 'application']

C

Trie result: ['app', 'apple', 'application']
Hash Map result: []

D

Trie result: ['app', 'apple']
Hash Map result: ['app', 'apple', 'application']

💡 Hint

Consider how prefix search is done in each structure.

The Trie stores words in a way that prefix search returns all words starting with 'app'. The Hash Map keys can be filtered by prefix using startsWith, so both return the same list here.

However, in practice, Hash Map prefix search is inefficient for large data sets.

🚀 Application

advanced

Why can't Hash Maps efficiently support autocomplete features?

Which limitation of Hash Maps makes them less suitable for autocomplete features compared to Tries?

A Hash Maps cannot store string keys at all, only numbers.

B Hash Maps do not store keys in a way that allows quick retrieval of all keys sharing a prefix, requiring scanning all keys.

C Hash Maps automatically delete keys after insertion, so autocomplete is impossible.

D Hash Maps sort keys alphabetically, which slows down autocomplete.

💡 Hint

Think about how autocomplete needs to find many keys sharing a prefix quickly.

Autocomplete requires quickly finding all keys starting with a prefix. Hash Maps store keys hashed and unordered, so to find all keys with a prefix, you must check every key, which is slow. Tries organize keys by prefix inherently.

🔧 Debug

advanced

Why does this Hash Map prefix search code perform poorly on large data?

Consider this JavaScript code to find words starting with 'pre' in a large Hash Map: const result = Object.keys(hashMap).filter(word => word.startsWith('pre')); Why does this approach become inefficient as the data grows?

A Because Hash Maps automatically sort keys, making filter slow.

B Because Object.keys only returns keys starting with 'pre', so no filtering is needed.

C Because startsWith is not a valid JavaScript method, causing runtime errors.

D Because Object.keys returns all keys, so filter checks every key, causing O(n) time complexity.

💡 Hint

Consider how many keys are checked during filtering.

Object.keys returns all keys in the Hash Map. The filter then checks each key with startsWith, so the time grows linearly with the number of keys. This is inefficient for large data sets.

🧠 Conceptual

expert

What unique property of Tries enables efficient prefix-based operations that Hash Maps lack?

Which property of Tries allows them to perform prefix-based operations efficiently, unlike Hash Maps?

A Tries compress keys into single strings, reducing memory usage compared to Hash Maps.

B Tries hash entire keys to unique integers, making prefix search constant time.

C Tries store keys as paths in a tree where each node represents a character, enabling shared prefixes to be traversed once.

D Tries store keys in sorted arrays, allowing binary search for prefixes.

💡 Hint

Think about how Tries organize characters and prefixes.

Tries represent keys as paths in a tree, where each node is a character. This structure allows all keys sharing a prefix to share the same path, so prefix operations traverse the prefix path once and then explore children efficiently. Hash Maps do not have this structure.

Practice

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

easy

A. Because Trie automatically sorts strings alphabetically.

B. Because Trie uses less memory than a Hash Map for any data.

C. Because Hash Map cannot store strings as keys.

D. Because Trie can efficiently find all words with a given prefix, which Hash Map cannot do easily.

Solution

1. Step 1: Understand Trie prefix search

   Trie stores strings character by character, allowing quick prefix lookups.

2. Step 2: Compare with Hash Map capabilities

   Hash Map stores full keys but cannot efficiently find all keys sharing a prefix without checking all keys.

3. Final Answer:

   Because Trie can efficiently find all words with a given prefix, which Hash Map cannot do easily. -> Option D

4. Quick Check:

   Trie = prefix search [OK]

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

Common Mistakes:

• Thinking Hash Map can do prefix search efficiently
• Believing Trie always uses less memory
• Assuming Hash Map cannot store string keys

2. Which of the following is the correct way to initialize an empty Trie node in JavaScript?

easy

A. const node = null;

B. const node = new Map();

C. const node = { children: {}, isEndOfWord: false };

D. const node = [];

Solution

1. Step 1: Identify Trie node structure

   A Trie node typically has a children object for next letters and a boolean to mark word end.

2. Step 2: Match with options

   const node = { children: {}, isEndOfWord: false }; correctly creates an object with children as empty object and isEndOfWord as false.

3. Final Answer:

   const node = { children: {}, isEndOfWord: false }; -> Option C

4. Quick Check:

   Trie node = object with children and end flag [OK]

Hint: Trie node = object with children map and end flag [OK]

Common Mistakes:

• Using array instead of object for children
• Using null instead of an object
• Using Map without isEndOfWord flag

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

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }
  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEndOfWord;
  }
}

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
console.log(trie.search('cat'));
console.log(trie.search('cap'));

medium

A. true true

B. true false

C. false true

D. false false

Solution

1. Step 1: Insert 'cat' and 'car' into Trie

   Both words are added character by character, marking end of word at last character.

2. Step 2: Search 'cat' and 'cap'

   'cat' exists and ends at isEndOfWord true, so returns true. 'cap' path breaks at 'p' missing, returns false.

3. Final Answer:

   true false -> Option B

4. Quick Check:

   Search 'cat' = true, 'cap' = false [OK]

Hint: Search returns true only if full word inserted before [OK]

Common Mistakes:

• Assuming partial prefix returns true
• Confusing isEndOfWord flag
• Missing character check in search

4. The following code tries to insert words into a Trie but has a bug. What is the bug?

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    // Missing line here
  }
}

medium

A. The code does not mark the end of the word after insertion.

B. The code uses an object instead of a Map for children.

C. The constructor does not initialize the root node.

D. The loop does not iterate over each character of the word.

Solution

1. Step 1: Review insert method steps

   Characters are added correctly, but after loop, isEndOfWord should be set true to mark word end.

2. Step 2: Identify missing line

   The comment '// Missing line here' indicates missing 'node.isEndOfWord = true;' which is essential.

3. Final Answer:

   The code does not mark the end of the word after insertion. -> Option A

4. Quick Check:

   Mark word end after insertion [OK]

Hint: Always set isEndOfWord true after inserting full word [OK]

Common Mistakes:

• Forgetting to mark end of word
• Confusing children structure with Map vs object
• Assuming constructor bug without checking insert

5. You want to find all words in a large dictionary that start with the prefix 'pro'. Which data structure is best and why? const words = ['program', 'progress', 'promise', 'problem', 'profile', 'project'];

hard

A. Use a Trie because it can quickly find all words with the prefix 'pro' without checking every word.

B. Use a Hash Map because it stores words as keys and can find prefixes instantly.

C. Use an array and filter words starting with 'pro' for best performance.

D. Use a linked list to store words and traverse to find prefix matches.

Solution

1. Step 1: Understand prefix search requirement

   Finding all words starting with 'pro' means searching by prefix efficiently.

2. Step 2: Compare data structures

   Trie stores words character by character, allowing fast prefix traversal. Hash Map and array require checking all words, linked list is slow.

3. Final Answer:

   Use a Trie because it can quickly find all words with the prefix 'pro' without checking every word. -> Option A

4. Quick Check:

   Prefix search = Trie best [OK]

Hint: Prefix search? Choose Trie for fast lookup [OK]

Common Mistakes:

• Thinking Hash Map supports prefix search efficiently
• Choosing array filter for large datasets
• Using linked list for prefix search