Trie vs Hash Map for Prefix Matching in DSA Javascript - Build Both Approaches

Trie vs Hash Map for Prefix Matching

📖 Scenario: You are building a simple search feature for a phone contacts app. Users want to find contacts quickly by typing the first few letters of a name.Two common ways to do this are using a Trie (a tree-like structure) or a Hash Map (a dictionary). This project will help you understand how both work for prefix matching.

🎯 Goal: Build two data structures: a Trie and a Hash Map that store contact names. Then, find all contacts starting with a given prefix using both methods.

📋 What You'll Learn

Create a list of contact names

Create a prefix string to search

Build a Trie data structure and insert all contacts

Build a Hash Map grouping contacts by their prefixes

Write functions to find contacts starting with the prefix using both Trie and Hash Map

Print the results of both searches

💡 Why This Matters

🌍 Real World

Search features in phone contacts, autocomplete in search bars, and prefix-based filtering in apps.

💼 Career

Understanding Trie and Hash Map helps in building efficient search and autocomplete features, common in software engineering roles.

1

Create the contacts list

Create a list called contacts with these exact names: 'Alice', 'Alfred', 'Bob', 'Bobby', 'Charlie'

DSA Javascript

# Create the contacts list
# Your code here

Hint

Use square brackets [] to create a list (array) and include the names as strings.

2

Set the prefix to search

Create a variable called prefix and set it to the string 'Al'

DSA Javascript

const contacts = ['Alice', 'Alfred', 'Bob', 'Bobby', 'Charlie'];
# Create the prefix variable
# Your code here

Hint

Use const prefix = 'Al'; to create the prefix variable.

3

Build Trie and Hash Map for prefix matching

Write a class called TrieNode with a constructor that initializes children as an empty object and isEndOfWord as false. Then write a class called Trie with methods insert(word) to add words and startsWith(prefix) to return all words starting with prefix. Also, create a hashMap object that groups contacts by their first two letters as keys. Insert all contacts into both the Trie and the hashMap.

DSA Javascript

const contacts = ['Alice', 'Alfred', 'Bob', 'Bobby', 'Charlie'];
const prefix = 'Al';
// Define TrieNode and Trie classes
// Create hashMap object
// Insert contacts into Trie and hashMap
# Your code here

Hint

Define TrieNode and Trie classes with the described methods. Use a loop to insert contacts into both data structures.

4

Search and print contacts starting with prefix

Use console.log to print the result of trie.startsWith(prefix) and the result of looking up hashMap[prefix] or an empty list if undefined.

DSA Javascript

const contacts = ['Alice', 'Alfred', 'Bob', 'Bobby', 'Charlie'];
const prefix = 'Al';

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

    startsWith(prefix) {
        let node = this.root;
        for (const char of prefix) {
            if (!node.children[char]) {
                return [];
            }
            node = node.children[char];
        }
        const results = [];
        const dfs = (currentNode, path) => {
            if (currentNode.isEndOfWord) {
                results.push(path);
            }
            for (const child in currentNode.children) {
                dfs(currentNode.children[child], path + child);
            }
        };
        dfs(node, prefix);
        return results;
    }
}

const trie = new Trie();
const hashMap = {};

for (const contact of contacts) {
    trie.insert(contact);
    const key = contact.slice(0, 2);
    if (!hashMap[key]) {
        hashMap[key] = [];
    }
    hashMap[key].push(contact);
}

// Print results below
console.log(trie.startsWith(prefix));
console.log(hashMap[prefix] || []);

Hint

Use console.log(trie.startsWith(prefix)) and console.log(hashMap[prefix] || []) to print the matching contacts.

Practice

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

easy

A. Linked List, because it allows sequential access

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

C. Array, because it stores elements in order

D. Trie, because it stores prefixes explicitly and allows fast prefix search

Solution

1. Step 1: Understand prefix matching requirement

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

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

   Trie stores prefixes explicitly, allowing quick traversal to all words with that prefix. Hash Map does not store prefixes, so it requires checking all keys or additional structures.

3. Final Answer:

   Trie, because it stores prefixes explicitly and allows fast prefix search -> Option D

4. Quick Check:

   Prefix search = Trie [OK]

Hint: Trie stores prefixes explicitly, ideal for prefix search [OK]

Common Mistakes:

• Thinking hash map can do prefix search directly
• Confusing prefix matching with exact key lookup
• Assuming arrays or linked lists are efficient for prefix search

2. Which of the following is the correct way to check if a prefix exists in a Trie node in JavaScript?

easy

A. if (prefix in trieNode) { ... }

B. if (trieNode.hasOwnProperty(prefix)) { ... }

C. if (trieNode[prefix]) { ... }

D. if (trieNode.contains(prefix)) { ... }

Solution

1. Step 1: Understand how to check keys in JavaScript objects

   The 'in' operator checks if a property exists in an object or its prototype chain.

2. Step 2: Compare options for checking prefix in Trie node

   if (prefix in trieNode) { ... } uses 'prefix in trieNode', which correctly checks if the prefix key exists. if (trieNode.hasOwnProperty(prefix)) { ... } uses hasOwnProperty which is valid but less common for prefix check. if (trieNode[prefix]) { ... } checks truthiness which can fail if value is falsy. if (trieNode.contains(prefix)) { ... } uses a non-existent method.

3. Final Answer:

   if (prefix in trieNode) { ... } -> Option A

4. Quick Check:

   Use 'in' operator to check keys [OK]

Hint: Use 'in' operator to check keys in objects [OK]

Common Mistakes:

• Using non-existent 'contains' method
• Checking property truthiness instead of existence
• Confusing hasOwnProperty with 'in' operator

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

const trie = {};
function insert(word) {
  let node = trie;
  for (const char of word) {
    if (!(char in node)) node[char] = {};
    node = node[char];
  }
  node.isEnd = true;
}

insert('cat');
insert('car');
insert('dog');

console.log('c' in trie, 'a' in trie['c'], 't' in trie['c']['a'], trie['c']['a']['t'].isEnd);

medium

A. true true true true

B. true true false undefined

C. true false false undefined

D. false false false undefined

Solution

1. Step 1: Trace insertions of words into the trie

   Inserting 'cat' creates nodes c -> a -> t with isEnd true at 't'. Inserting 'car' adds r under c -> a. Inserting 'dog' adds d -> o -> g separately.

2. Step 2: Check existence of keys and isEnd property

   'c' exists in trie, 'a' exists under 'c', 't' exists under 'a', and 't' node has isEnd true from 'cat' insertion.

3. Final Answer:

   true true true true -> Option A

4. Quick Check:

   All keys and isEnd exist as expected [OK]

Hint: Trace each insertion step-by-step [OK]

Common Mistakes:

• Assuming 't' node missing after insertions
• Confusing isEnd property placement
• Not updating node reference inside loop

4. The following code attempts to check if a prefix exists in a Trie but does not work correctly. What is the bug?

function startsWith(trie, prefix) {
  let node = trie;
  for (const char of prefix) {
    if (!node[char]) return false;
    node = node[char];
  }
  return true;
}

medium

A. It incorrectly returns false if a node exists but is falsy

B. It does not check if the prefix is a complete word

C. It should use 'char in node' instead of '!node[char]'

D. It does not handle empty prefix input

Solution

1. Step 1: Analyze the condition '!node[char]'

   This condition fails if node[char] exists but is falsy (like an empty object or false), causing incorrect false return.

2. Step 2: Suggest correct key existence check

   Using 'char in node' correctly checks if the key exists regardless of value truthiness.

3. Final Answer:

   It should use 'char in node' instead of '!node[char]' -> Option C

4. Quick Check:

   Use 'in' operator to check keys, not truthiness [OK]

Hint: Check key existence with 'in', not truthiness [OK]

Common Mistakes:

• Using falsy check instead of key existence
• Confusing prefix existence with complete word check
• Ignoring empty prefix edge case

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

// Approach 1: Use a Hash Map storing all words as keys
// Approach 2: Use a Trie storing words character by character
// Approach 3: Use an array and filter words by prefix
// Approach 4: Use a sorted array and binary search for prefix

hard

A. Approach 4, because binary search on sorted array quickly finds prefix range

B. Approach 2, because Trie allows efficient prefix traversal and retrieval

C. Approach 3, because filtering arrays is simple and fast for large data

D. Approach 1, because Hash Map has constant time lookup for prefixes

Solution

1. Step 1: Evaluate each approach for prefix search

   Hash Map (Approach 1) cannot do prefix search efficiently as keys are exact. Array filter (Approach 3) is slow for large data. Sorted array with binary search (Approach 4) helps but retrieving all matches requires scanning range.

2. Step 2: Understand Trie advantages

   Trie (Approach 2) stores prefixes explicitly, allowing fast traversal to all words sharing the prefix, making it best for prefix search in large datasets.

3. Final Answer:

   Approach 2, because Trie allows efficient prefix traversal and retrieval -> Option B

4. Quick Check:

   Prefix search efficiency = Trie [OK]

Hint: Trie stores prefixes explicitly, best for prefix search [OK]

Common Mistakes:

• Assuming hash map supports prefix search
• Ignoring performance cost of filtering large arrays
• Overestimating binary search for prefix retrieval