Counting Words With a Given Prefix

Counting Words With a Given Prefix

What is this problem about?

The Counting Words With a Given Prefix interview question asks you to find the number of strings in an array that start with a specific string called pref. You are given an array of strings words and a string pref. For each word in the array, you must check if it begins with the exact characters of the prefix.

Why is this asked in interviews?

Companies like Microsoft and Meta use the Counting Words With a Given Prefix coding problem as a basic screening question to evaluate a candidate's familiarity with string manipulation and library functions. It's an "Easy" difficulty problem that tests for speed, accuracy, and understanding of the "Prefix" concept in string matching. It also serves as a gateway to more complex problems like building a Trie (Prefix Tree).

Algorithmic pattern used

This problem follows a simple Linear Scan / String Matching pattern.

1. Iterate through each word in the words array.
2. Use a string comparison method (like startsWith() in Java/JavaScript or slicing in Python) to check if the current word matches the prefix.
3. Maintain a counter and increment it for every match found.

Example explanation

Words: ["apple", "app", "apricot", "banana"], Prefix: "app"

1. "apple" starts with "app". (Match!)
2. "app" starts with "app". (Match!)
3. "apricot" starts with "apr", not "app". (No match).
4. "banana" starts with "ban". (No match). Total count: 2.

Common mistakes candidates make

• Substring vs. Prefix: Confusing a general substring match (where the target can be anywhere in the word) with a prefix match (where it must be at the very start).
• Case Sensitivity: Forgetting to clarify if "App" matches "app" (usually string matching is case-sensitive unless specified).
• Inefficient Checks: Manually looping through characters of each word when built-in methods are more optimized and readable.

Interview preparation tip

While this problem is simple, mention that for a very large number of words and prefix queries, a Trie (Prefix Tree) data structure would be the optimal way to handle these requests in O(L) time, where L is the length of the prefix.