These are the notes for C++ Coding Questions, episode 13, placement practice for people who finished the SyntaxPilot C++ course. Three questions that come up in almost every placement round, all solved with std::map and std::set: word frequency in alphabetical order (and why unordered_map prints in no order at all), the first repeating element (with the two meanings interviewers use), and grouping anagrams (and why the sum of the letters is a bad key).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program that runs too long (Time Limit Exceeded, TLE), like an online judge.
Real-life pictures
| In real life | In C++ |
|---|---|
| A chai stall notebook: one line per item, a tally mark per order | map<string, int>: key = item, value = count; freq[w]++ |
| The notebook's lines kept in A to Z order | map keeps its keys sorted |
| Scraps of paper thrown into numbered boxes | unordered_map: keys go into buckets chosen by a hash, no order |
| The school gate guard's register: "has this ID card already come in?" | set<int> seen; seen.count(x) |
| Letter tiles lined up A to Z: eat, tea, ate → a e t | the sorted word as the key of a group |
| Two different bags that weigh the same | a collision: two different things with the same key |
Two tools, one line each
std::set<T>: a collection of unique values kept in sorted order.insert,count(0 or 1),erase,find: each O(log n).std::map<K, V>: key → value pairs; every key appears once; keys are kept sorted.m[k]gives the value for k and, if k is missing, first inserts it with a value-initialised V (0 forint,""forstring).std::unordered_set/std::unordered_map: the same jobs using hashing: O(1) on average, but no order at all.
#include <iostream>
#include <set>
#include <map>
#include <string>
using namespace std;
int main() {
set<int> s = {5, 1, 5, 3};
for (int x : s) cout << x << " ";
cout << "| size " << s.size() << "\n";
map<string, int> m;
m["chai"]++;
m["chai"]++;
m["tea"]++;
for (auto& [k, v] : m) cout << k << "=" << v << " ";
cout << "\n";
return 0;
}
1 3 5 | size 3
chai=2 tea=1
Q1: Word frequency
Problem. Read words until the input ends. Print each different word once with how many times it appeared, in alphabetical order.
| Input | Output |
|---|---|
chai samosa chai tea samosa chai vada |
chai 3, samosa 2, tea 1, vada 1 |
Think out loud. A word → count table: a map. Edge cases: a single word, every word the same, and real sentences with capitals and punctuation.
The obvious attempt: unordered_map
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<string, int> freq;
string w;
while (cin >> w) freq[w]++;
for (auto& [word, c] : freq) cout << word << " " << c << "\n";
return 0;
}
With the seven words, and then with 14 different snacks (chai samosa tea vada poha idli dosa upma lassi jalebi kachori pakora bhel puri):
vada 1
tea 1
samosa 2
chai 3
samosa 1
tea 1
vada 1
idli 1
dosa 1
lassi 1
jalebi 1
pakora 1
poha 1
upma 1
puri 1
kachori 1
chai 1
bhel 1
The counts are right, but the order is not alphabetical. With 4 words it happens to look reversed; with 14 it is scrambled.
Why. An unordered_map turns each key into a number (its hash) and uses it to choose a bucket. Iterating walks the buckets, so the order depends on the hash values, the number of buckets, and the library version. The standard promises no order.
Fix 1: std::map
A map is a balanced binary search tree (a red-black tree in libstdc++): walking it visits the keys in sorted order.
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map<string, int> freq;
string w;
while (cin >> w) freq[w]++;
for (auto& [word, c] : freq) cout << word << " " << c << "\n";
return 0;
}
The seven words, then the sentence Chai, chai! Samosa and CHAI. Tea and samosa.:
chai 3
samosa 2
tea 1
vada 1
CHAI. 1
Chai, 1
Samosa 1
Tea 1
and 2
chai! 1
samosa. 1
Sorted now. But in a real sentence, CHAI., Chai, and chai! are three different keys, and capital letters sort first ('C' is 67, 'a' is 97).
Fix 2: clean every word into a key
Decide what "the same word" means and make the key say exactly that: letters only, lowercase. isalpha checks for a letter, tolower lowercases it; cast char to unsigned char first, because passing a negative char (any non-ASCII byte) to them is undefined behaviour. Skip words that become empty (like --).
#include <iostream>
#include <string>
#include <map>
#include <cctype>
using namespace std;
string clean(const string& w) {
string s;
for (char ch : w)
if (isalpha((unsigned char)ch)) s += tolower((unsigned char)ch);
return s;
}
int main() {
map<string, int> freq;
string w;
while (cin >> w) {
string s = clean(w);
if (!s.empty()) freq[s]++;
}
for (auto& [word, c] : freq) cout << word << " " << c << "\n";
return 0;
}
The sentence, the seven words, and -- --:
and 2
chai 3
samosa 2
tea 1
chai 3
samosa 2
tea 1
vada 1
(The last run, -- --, prints nothing: both words became empty.)
Complexity. n words, d different words, word length L: each map operation compares strings O(log d) times, so O(n · L · log d) time, O(d · L) space. Usually written O(n log n).
When is unordered_map the right choice?
When you only look things up (or the output order doesn't matter, or you sort the results yourself). It is O(1) on average instead of O(log n). If you need both speed and sorted output, count with unordered_map, then copy the pairs into a vector and sort it.
Q2: First repeating element
Problem. Read n numbers. Going left to right, print the first number that was already seen; or no repeat.
| Input | Output |
|---|---|
5 3 4 3 5 |
3 (the second 3, at index 3, comes before the second 5) |
9 8 7 |
no repeat |
Think out loud. Edge cases: no repeat, everything the same, n = 1. Big test: 500,000 numbers whose only repeat is at the very end (the test block, when n is 0, builds 1 2 3 ... 499999 7).
The obvious attempt: ask everyone already inside
#include <iostream>
#include <vector>
using namespace std;
int firstRepeat(const vector<int>& a) {
for (int i = 0; i < (int)a.size(); i++)
for (int j = 0; j < i; j++)
if (a[j] == a[i]) return a[i];
return -1;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 500,000 numbers, one repeat at the end
n = 500000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = i + 1;
a[n - 1] = 7;
}
int r = firstRepeat(a);
if (r == -1) cout << "no repeat\n";
else cout << "first repeat: " << r << "\n";
return 0;
}
first repeat: 3
With 0 (the big test) it runs for about 40 seconds on our machine: Time Limit Exceeded in the SyntaxPilot compiler.
Why. Every new number re-checks all earlier ones: 1 + 2 + ... + n ≈ n²/2 ≈ 125 billion comparisons for n = 500,000. But the earlier numbers never change: remember them once.
Fix: a set of seen numbers
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int firstRepeat(const vector<int>& a) {
set<int> seen;
for (int x : a) {
if (seen.count(x)) return x;
seen.insert(x);
}
return -1;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 500,000 numbers, one repeat at the end
n = 500000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = i + 1;
a[n - 1] = 7;
}
int r = firstRepeat(a);
if (r == -1) cout << "no repeat\n";
else cout << "first repeat: " << r << "\n";
return 0;
}
Inputs 5 3 4 3 5, the big test (0), 9 8 7, a single 4, and 2 2 2 2:
first repeat: 3
first repeat: 7
no repeat
no repeat
first repeat: 2
O(n log n) time, O(n) space. A shorter form uses the return value of insert, a pair whose .second is false when the value was already there: if (!seen.insert(x).second) return x;. unordered_set<int> makes it O(n) on average.
The other meaning: the first element (by position) that appears again
Some interviewers mean: "among the values that occur more than once, which one comes first in the array?" For 5 3 4 3 5 that is 5 (index 0), not 3. Count everything first, then walk the array again:
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int firstRepeat(const vector<int>& a) {
map<int, int> cnt;
for (int x : a) cnt[x]++;
for (int x : a)
if (cnt[x] > 1) return x;
return -1;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 500,000 numbers, one repeat at the end
n = 500000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = i + 1;
a[n - 1] = 7;
}
int r = firstRepeat(a);
if (r == -1) cout << "no repeat\n";
else cout << "first repeat: " << r << "\n";
return 0;
}
5 3 4 3 5, then the big test:
first repeat: 5
first repeat: 7
Two passes, O(n log n) time, O(n) space. In an interview, ask which meaning they want and check it on 5 3 4 3 5.
Q3: Group anagrams
Problem. Read lowercase words and print them in groups, so that words made of exactly the same letters (same letters, same counts) are together.
| Input | Groups |
|---|---|
eat tea tan ate nat bat ad bc |
[eat tea ate], [tan nat], [bat], [ad], [bc] |
Think out loud. "Same group" ⇔ "same key": what key? Edge cases: a word with no partner; different words with the same length and the same letter total, like ad and bc.
The obvious attempt: the sum of the letters
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
int main() {
map<int, vector<string>> groups;
string w;
while (cin >> w) {
int key = 0;
for (char ch : w) key += ch; // add up the letters
groups[key].push_back(w);
}
for (auto& [key, g] : groups) {
for (auto& s : g) cout << s << " ";
cout << "\n";
}
return 0;
}
ad bc
bat
eat tea ate
tan nat
ad and bc ended up in one group: 'a' + 'd' = 97 + 100 = 197 and 'b' + 'c' = 98 + 99 = 197.
Why. Anagrams always have the same sum, but the same sum does not mean anagrams. When two different things get the same key, that is a collision. A good key is equal if and only if the things are "the same".
Fix: the sorted word as the key
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main() {
map<string, vector<string>> groups;
string w;
while (cin >> w) {
string key = w;
sort(key.begin(), key.end()); // eat, tea, ate -> aet
groups[key].push_back(w);
}
for (auto& [key, g] : groups) {
cout << key << ": ";
for (auto& s : g) cout << s << " ";
cout << "\n";
}
return 0;
}
The eight words, then listen silent enlist google banana:
abt: bat
ad: ad
aet: eat tea ate
ant: tan nat
bc: bc
aaabnn: banana
eggloo: google
eilnst: listen silent enlist
Groups come out in key order (abt, ad, aet, ant, bc) because it's a map; inside a group, words keep their input order.
Complexity. n words of length up to k: sorting each word O(k log k), each map operation O(k log n) (string comparisons): O(n · k · (log k + log n)) time, O(n · k) space.
Another good key: the 26 letter counts
No sorting: count each letter. The key is a 26-character string of counts (this simple version is fine while no letter appears more than about 200 times, because each count is stored in one char).
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
int main() {
map<string, vector<string>> groups;
string w;
while (cin >> w) {
string key(26, '0');
for (char ch : w) key[ch - 'a']++; // letter counts: no sort
groups[key].push_back(w);
}
for (auto& [key, g] : groups) {
for (auto& s : g) cout << s << " ";
cout << "\n";
}
return 0;
}
bc
tan nat
eat tea ate
ad
bat
Same groups, in a different order (the keys sort differently). O(n · k) to build the keys.
The real skill: choosing the key
| Question | "The same" means | Key |
|---|---|---|
| Word frequency | same word, ignoring case and punctuation | letters only, lowercase |
| First repeat | same number | the number |
| Group anagrams | same letters, same counts | the sorted word, or the 26 counts |
The test for any key: two things get the same key exactly when they really are the same. Need sorted output? map / set. Only lookups? unordered_ is fine.
Complexity summary
| Program | Time | Extra space |
|---|---|---|
word frequency, map |
O(n log n) | O(distinct words) |
word frequency, unordered_map |
O(n) average, but no order | O(distinct words) |
| first repeat, nested loops | O(n²): TLE for 500,000 | O(1) |
first repeat, set |
O(n log n) | O(n) |
first repeat (meaning B), map + second pass |
O(n log n) | O(n) |
| group anagrams, sorted key | O(n · k log k) plus map lookups | O(n · k) |
| group anagrams, letter-count key | O(n · k) plus map lookups | O(n · k) |
Every insert, find, count, erase and [] on a map / set is O(log n) guaranteed; on unordered_ containers O(1) on average.
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
unordered_map when the output must be sorted |
vada tea samosa chai, or scrambled |
hashing gives no order | map, or copy to a vector and sort |
| counting raw words | CHAI. 1, Chai, 1, chai! 1 |
keys must match exactly | clean: isalpha, tolower |
tolower(ch) with a plain char |
undefined behaviour for non-ASCII bytes | negative values | tolower((unsigned char)ch) |
| nested loops for "seen before?" | Time Limit Exceeded | O(n²) re-checks | set<int> seen |
| assuming one meaning of "first repeating" | 3 where the interviewer wanted 5 | two common meanings | ask, test on 5 3 4 3 5 |
| sum of letters as an anagram key | ad bc grouped together |
a collision | sorted word / letter counts |
if (m[k] == 0) just to check |
the map grows (k inserted with 0) | [] inserts missing keys |
m.count(k) or m.find(k) |
Your turn: common roll numbers (solution)
Problem. Two attendance lists. Print the roll numbers that are in both, sorted, each once. 5 1 3 3 9 and 3 9 9 4 → 3 9.
Idea. Put each list in a set (duplicates disappear, values sorted). Walk the first set; print a value if the second set has it. Since we walk a sorted set, the output is sorted.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main() {
int n, m;
while (cin >> n >> m) {
set<int> a, b;
for (int i = 0; i < n; i++) { int x; cin >> x; a.insert(x); }
for (int i = 0; i < m; i++) { int x; cin >> x; b.insert(x); }
bool any = false;
for (int x : a)
if (b.count(x)) { cout << x << " "; any = true; }
cout << (any ? "" : "none") << "\n";
}
return 0;
}
Input 5 4 / 5 1 3 3 9 / 3 9 9 4, then 3 2 / 1 2 3 / 7 8:
3 9
none
O((n + m) log(n + m)) time, O(n + m) space. (std::set_intersection from <algorithm> does the walk for you on two sorted ranges.)
Practice questions (with solutions)
1. Isomorphic strings. Can the letters of s be replaced (each letter always by the same letter, two letters never by the same one) to get t? egg / add → yes, foo / bar → no, ab / aa → no.
Solution
Keep two maps, s → t and t → s; every pair must agree with both.
#include <iostream>
#include <string>
#include <map>
using namespace std;
bool isomorphic(const string& s, const string& t) {
if (s.size() != t.size()) return false;
map<char, char> st, ts;
for (size_t i = 0; i < s.size(); i++) {
char a = s[i], b = t[i];
if (st.count(a) && st[a] != b) return false;
if (ts.count(b) && ts[b] != a) return false;
st[a] = b;
ts[b] = a;
}
return true;
}
int main() {
string s, t;
while (cin >> s >> t) cout << s << " " << t << ": " << (isomorphic(s, t) ? "yes" : "no") << "\n";
return 0;
}
egg add: yes
foo bar: no
ab aa: no
paper title: yes
O(n log 256) = O(n) time.
2. Top 3 most frequent words (ties in alphabetical order).
Solution
Count with a map, copy the pairs into a vector, sort by count (bigger first), then by word.
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main() {
map<string, int> freq;
string w;
while (cin >> w) freq[w]++;
vector<pair<string, int>> v(freq.begin(), freq.end());
sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
if (a.second != b.second) return a.second > b.second; // more frequent first
return a.first < b.first; // tie: A to Z
});
for (int i = 0; i < 3 && i < (int)v.size(); i++) cout << v[i].first << " " << v[i].second << "\n";
return 0;
}
chai 3
poha 2
tea 2
poha and tea both appear twice; poha comes first alphabetically. O(n log n).
3. Count the distinct numbers in a vector.
Solution
#include <iostream>
#include <set>
using namespace std;
int main() {
int n;
cin >> n;
set<int> s;
for (int i = 0; i < n; i++) { int x; cin >> x; s.insert(x); }
cout << s.size() << "\n";
return 0;
}
4
O(n log n). Alternative without a set: sort, then unique (episode 9) and count.
Mini project: the chai stall's closing report
Read the day's orders (item quantity per line), then print every item A to Z with its total, the bestseller, and how many different items were sold.
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map<string, int> total;
string item;
int qty;
while (cin >> item >> qty) total[item] += qty;
string best;
int bestQty = 0;
cout << "Closing report\n";
for (auto& [name, q] : total) {
cout << " " << name << ": " << q << "\n";
if (q > bestQty) { bestQty = q; best = name; } // strict >: a tie keeps the A-to-Z first
}
cout << "Bestseller: " << best << " (" << bestQty << ")\n";
cout << "Different items: " << total.size() << "\n";
return 0;
}
Input: chai 3, samosa 2, chai 2, vada 4, samosa 1, chai 1, lassi 2:
Closing report
chai: 6
lassi: 2
samosa: 3
vada: 4
Bestseller: chai (6)
Different items: 4
Quick quiz
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<string, int> m;
m["tea"] = 2;
m["chai"]++;
if (m["vada"] == 0) cout << m.size() << " ";
for (auto& [k, v] : m) cout << k << v << " ";
cout << "\n";
return 0;
}
(A) 2 chai1 tea2 (B) 3 chai1 tea2 vada0 (C) 3 tea2 chai1 vada0 (D) 2 chai1 tea2 vada0
Answer
(B). Just reading m["vada"] inserts vada with the value 0, so the size is 3; a map prints its keys in sorted order.
3 chai1 tea2 vada0
To check for a key without inserting it, use m.count("vada") or m.find("vada") != m.end().
Interview questions
mapvsunordered_map?map: a balanced tree, keys sorted, O(log n) guaranteed.unordered_map: a hash table, no order, O(1) on average (O(n) in the worst case).- What does
m[k]do if k is missing? Inserts k with a value-initialised value (0 for numbers) and returns a reference to it. That's whym[w]++counts from 0, and whym[k] == 0as a "check" adds keys. - How do you check for a key without inserting?
m.count(k),m.find(k) != m.end(), orm.contains(k)in C++20. setvsunordered_setfor "seen before?" Both work;unordered_setis O(1) average,setO(log n) but sorted and with no bad worst case.- What does
s.insert(x)return? A pair: an iterator to the element, and aboolthat isfalseif x was already there. - Two meanings of "first repeating element"? The first element met that was seen before (
5 3 4 3 5→ 3), or the first element by position that appears again (→ 5). - Why is the sum of letters a bad anagram key? Collisions:
adandbcboth sum to 197. A key must be equal exactly when the things are equal. - Group anagrams without sorting each word? Use the 26 letter counts as the key: O(k) per word instead of O(k log k).
- Iterating a
mapgives keys in what order? Ascending byoperator<(or by the comparator you give it, e.g.map<string, int, greater<string>>for Z to A).
Glossary
| Term | Meaning | Example |
|---|---|---|
std::set |
Unique values kept in sorted order | set<int> s = {5, 1, 5, 3} holds 1 3 5 |
std::map |
Key → value pairs, unique keys, sorted by key | map<string, int> freq |
std::unordered_set / unordered_map |
The same jobs with hashing: O(1) average, no order | unordered_map<string, int> |
| Key | What a map is looked up by | the word "chai" |
| Value | What is stored for a key | its count, 3 |
| Hash | A number computed from a key, used to choose a bucket | hash<string>{}("chai") |
| Bucket | One slot of a hash table; holds the keys with that hash position | — |
| Balanced binary search tree | A tree kept sorted and short, so lookups take O(log n) | how map and set are built |
m[k] |
The value for k; inserts k with 0 if missing | freq[w]++ |
count(k) |
1 if k is present, else 0 (set and map) | seen.count(x) |
find(k) |
An iterator to k, or end() |
m.find("tea") != m.end() |
| Structured binding | Unpacking a pair into names | for (auto& [word, c] : freq) |
isalpha / tolower |
Is it a letter? / lowercase it (from <cctype>) |
tolower((unsigned char)ch) |
| Word frequency | How many times each word appears | chai 3 |
| First repeating element | The first value met that was seen before (or: the first by position that appears again) | 5 3 4 3 5 → 3 (or 5) |
| Anagram | A word with the same letters, same counts, in another order | eat, tea, ate |
| Collision | Two different things with the same key | ad and bc both sum to 197 |
| O(log n) | Work grows by one step each time n doubles | a set of 500,000 → ~19 steps |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | nested loops on 500,000 numbers |
| Undefined behaviour (UB) | Code the C++ standard gives no meaning to | tolower with a negative char |
Summary
- Word frequency:
map<string, int>andfreq[w]++; amapprints keys A to Z, anunordered_mapin no promised order. Clean words into keys: letters only, lowercase. - First repeat: a
setof seen values turns O(n²) into O(n log n). There are two meanings: ask, and test on5 3 4 3 5. - Group anagrams:
map<string, vector<string>>with the sorted word (or the letter counts) as the key; a sum of letters collides. - The real skill is choosing the key: equal keys exactly when the things are the same.
Next episode: Hashing questions: the longest consecutive sequence, subarray sum equals k (prefix sums with unordered_map), and a duplicate within distance k.