Frontend School

Trie-based Prefix Counter

DSA
medium

Trie-based Prefix Counter

Medium
Trie
Data Structures
String
Prefix Search

Overview

Paytm operates at immense scale, processing millions of transactions and managing vast directories of merchants and products. Efficiently searching and retrieving data based on partial inputs is a critical capability. This problem simulates a core component of such systems: designing a data structure to quickly determine the number of items that match a given prefix.

What you need to do / Task

Implement a function getPrefixCounts that takes two arrays of strings: dictionary and queries. Your task is to build an efficient data structure from the dictionary and then, for each string in queries, find and return the total count of words in the dictionary that start with that particular query string as a prefix.

Input & output

  • dictionary: An array of strings representing the collection of words to be indexed. Each string in this array is considered a distinct item, even if duplicate strings exist.
  • queries: An array of strings representing the prefixes for which you need to find counts.
  • Return: An array of numbers. The i-th element of the returned array should be the count of words in the dictionary that have queries[i] as their prefix.

Clarifications

  • All words in dictionary and queries will consist only of lowercase English letters ('a'-'z').
  • An empty prefix (e.g., "") should return the total count of words in the dictionary if encountered in queries.

Examples

1

Example 1

Input:

dictionary = ["apple", "apricot", "application", "banana"], queries = ["app", "apr", "ban", "gra"]

Output:

[2,1,1,0]

Note:

For "app", "apple" and "application" are matches (count = 2). For "apr", "apricot" is a match (count = 1). For "ban", "banana" is a match (count = 1). For "gra", no words match (count = 0).

2

Example 2

Input:

dictionary = ["cat", "car", "dog", "catamaran"], queries = ["ca", "c", "do", "d"]

Output:

[3,3,1,1]

Note:

For "ca", "cat", "car", "catamaran" are matches (count = 3). For "c", "cat", "car", "catamaran" are matches (count = 3). For "do", "dog" is a match (count = 1). For "d", "dog" is a match (count = 1).

3

Example 3

Input:

dictionary = ["test", "tester", "test"], queries = ["test", "tes", "t"]

Output:

[2,3,3]

Note:

For "test", both instances of "test" are matches (count = 2). For "tes", both instances of "test" and "tester" are matches (count = 3). For "t", both instances of "test" and "tester" are matches (count = 3).

Constraints

Constraints & assumptions

  • 1 <= dictionary.length <= 10^4
  • 1 <= queries.length <= 10^4
  • 1 <= dictionary[i].length, queries[i].length <= 30
  • All strings in dictionary and queries consist of lowercase English letters ('a'-'z').
  • Duplicate words in dictionary should be handled such that each occurrence contributes to the prefix count (e.g., if dictionary = ["apple", "apple"] and query = "app", the count should be 2).

Out of scope

  • Handling non-alphabetic characters, uppercase letters, or special symbols.
  • Advanced memory optimizations like compressed Tries.
  • Concurrency or persistence requirements.

What interviewers evaluate

  • Correctness of Trie Implementation: Ability to design and implement a functional Trie data structure.
  • Efficient Prefix Counting Logic: Correctly incorporating and utilizing counters within the Trie nodes to efficiently determine prefix counts.
  • Time and Space Complexity: Achieving optimal performance (time) for both building the Trie and processing queries, along with reasonable space usage.
  • Edge Case Handling: Demonstrating robustness for cases such as prefixes not found, or exact matches.

Loading editor...