Count Words with Given Prefix in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of countWordsStartingWith after insertions

What is the output of the following TypeScript code that inserts words and counts how many start with a given prefix?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  count: number = 0;
}

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

  insert(word: string): void {
    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.count++;
    }
  }

  countWordsStartingWith(prefix: string): number {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) {
        return 0;
      }
      node = node.children.get(ch)!;
    }
    return node.count;
  }
}

const trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("application");
trie.insert("apt");
trie.insert("bat");

console.log(trie.countWordsStartingWith("app"));

A 4

B 2

C 3

D 1

💡 Hint

Count how many inserted words start with 'app'.

The words starting with 'app' are 'apple', 'app', and 'application', so the count is 3.

❓ Predict Output

intermediate

Result of countWordsStartingWith for a prefix not present

What will be the output of the code when counting words starting with prefix 'cat' after inserting some words?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  count: number = 0;
}

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

  insert(word: string): void {
    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.count++;
    }
  }

  countWordsStartingWith(prefix: string): number {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) {
        return 0;
      }
      node = node.children.get(ch)!;
    }
    return node.count;
  }
}

const trie = new Trie();
trie.insert("dog");
trie.insert("deer");
trie.insert("deal");

console.log(trie.countWordsStartingWith("cat"));

A 0

B 1

C 3

D 2

💡 Hint

Check if any inserted word starts with 'cat'.

No inserted word starts with 'cat', so the count is 0.

🔧 Debug

advanced

Identify the bug in countWordsStartingWith method

The following TypeScript code is supposed to count how many words start with a given prefix. However, it returns incorrect results. What is the bug?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  count: number = 0;
}

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

  insert(word: string): void {
    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.count++;
  }

  countWordsStartingWith(prefix: string): number {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) {
        return 0;
      }
      node = node.children.get(ch)!;
    }
    return node.count;
  }
}

A The insert method does not create new nodes for characters.

B The count is incremented only at the end node, so intermediate nodes have count 0, causing wrong prefix counts.

C The countWordsStartingWith method does not check if prefix exists.

D The root node's count is incremented incorrectly.

💡 Hint

Think about when counts are updated during insertion.

The count should be incremented at every node along the path during insertion to reflect how many words pass through that node. Here, count is incremented only at the last node, so prefix counts are wrong.

❓ Predict Output

advanced

Output after multiple insertions and prefix counts

Given the following code, what is the output of the two console.log statements?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  count: number = 0;
}

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

  insert(word: string): void {
    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.count++;
    }
  }

  countWordsStartingWith(prefix: string): number {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) {
        return 0;
      }
      node = node.children.get(ch)!;
    }
    return node.count;
  }
}

const trie = new Trie();
trie.insert("car");
trie.insert("card");
trie.insert("care");
trie.insert("cart");
trie.insert("cat");

console.log(trie.countWordsStartingWith("car"));
console.log(trie.countWordsStartingWith("ca"));

A

4
5

B

4
4

C

3
5

D

3
4

💡 Hint

Count words starting with 'car' and 'ca'.

'car', 'card', 'care', and 'cart' start with 'car' (4 words). All five words start with 'ca'.

🧠 Conceptual

expert

Why use a Trie for counting words with a prefix?

Which of the following is the main advantage of using a Trie data structure to count how many words start with a given prefix compared to scanning all words in a list?

A Trie automatically removes duplicate words.

B Trie stores words in sorted order, so counting is faster.

C Trie uses less memory than storing words in a list.

D Trie allows prefix counts in time proportional to prefix length, not total words.

💡 Hint

Think about how prefix queries scale with number of words.

Trie lets you find prefix counts by following nodes for each prefix character, so time depends on prefix length only, not total words. Scanning a list checks every word, which is slower.