PPractick

The problem

An analytics dashboard receives an array of product IDs from today's orders, then a list of queries: "how many times was product X ordered?" A second panel does the same for letters in a search string: "how many times does 'a' appear?" Scanning the whole array for every query is O(N × Q), which is far too slow when both are 10^5. Hashing fixes this: count everything once up front into a frequency table, and then each query is a single O(1) lookup. This problem introduces the three table types you'll use constantly: a plain array (for small, dense keys like letters), map, and unordered_map.

Example: array [1, 2, 1, 3, 2], queries [1, 3, 4, 12] → [2, 1, 0, 0].

Function signature

vector<int> countNumbers(const vector<int>& arr, const vector<int>& queries);  // unordered_map
vector<int> countLetters(const string& s, const string& queries);             // array of 26

Test cases

Input	Output	Explanation
arr [1, 2, 1, 3, 2], queries [1, 3, 4, 12]	[2, 1, 0, 0]	Missing keys count as 0
arr [1000000000, 5, 1000000000], queries [1000000000, 5]	[2, 1]	Large keys need a map, not an array
arr [], queries [7]	[0]	Nothing counted
s "abcdabehf", queries "abfz"	[2, 2, 1, 0]	Letter counts from a size-26 array

(Confirm: numbers can be up to 10^9, so the numeric table must be a hash map; the string contains lowercase letters only.)

How interviewers phrase it

• "Given an array and Q queries, return how many times each queried number appears."
• "Count the frequency of each character in a string."
• Theory: "What is hashing? How does a hash map work? What's a collision? map vs unordered_map?"

Clarifying questions to ask

1. What's the range of the values? (Small and dense → array; large or sparse → hash map.)
2. How many elements and queries?
3. For strings: lowercase only, or any character?
4. Do I need the keys in sorted order? (Then map.)

Follow-ups to expect

1. "When can you use a plain array as the table?"
2. "map vs unordered_map?"
3. "What's a collision and how is it handled?"
4. "What hash function maps a number to a bucket?"
5. "Can unordered_map be attacked?"

Related questions

• Counting Frequencies of Array Elements Easy
• Highest Occurring Element in an Array Easy
• Reverse an array Easy
• Largest Element Easy
• Second Largest Element Easy
• Check if the Array is Sorted II Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in