DSA interview question

Counting Frequencies of Array Elements

Easy · Algorithms · Topics: hashing, array, frequency map

The problem

A survey app collects answers as numeric option codes, and the results screen must list each distinct answer with how many times it was chosen, in the order the answers first appeared, so the list matches what respondents saw. Counting with nested loops (for each element, scan the whole array) is O(N²) and also prints duplicates unless you track what's already been reported. A hash map does the counting in one pass, and a second pass over the original array gives the first-appearance order.

Example: [10, 5, 10, 15, 10, 5] → 10: 3, 5: 2, 15: 1.

Function signature

vector<pair<int, int>> frequencies(const vector<int>& arr);  // (value, count) in first-appearance order

Test cases

Input `arr`	Output	Explanation
`[10, 5, 10, 15, 10, 5]`	`10:3 5:2 15:1`	Ordered by first appearance, not by value
`[2, 2, 2, 2]`	`2:4`	A single distinct value
`[1]`	`1:1`
`[]`	(empty)
`[-1, 0, -1]`	`-1:2 0:1`	Negative values work with a hash map

(Confirm: values can be any int, including negatives; each distinct value is reported once, in order of first appearance.)

How interviewers phrase it

"Count the frequency of every element in an array."
GeeksforGeeks variant: "Given N positive integers in the range 1..N, count the frequency of each number from 1 to N, ideally in O(1) extra space."
A building block for majority element, anagram checks, and "top k frequent" problems.

Clarifying questions to ask

What range can the values take? (Small range → array; otherwise hash map.)
In what order should the output be: first appearance, sorted by value, or any order?
Can I use extra space, or must it be in place?
How large is N?

Follow-ups to expect

"What's wrong with the nested-loop approach?"
"How do you keep first-appearance order?"
"What if the values are 1..N and you can't use extra space?"
"Sorted by value instead?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview