SyntaxPilot
Courses/C++ Coding Questions/Lesson 13
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 13 of 30

Map and set questions

word frequency (map vs unordered_map order)first repeating element (set)group anagrams (map of sorted key)

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 for int, "" for string).
  • 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

  1. map vs unordered_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).
  2. 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 why m[w]++ counts from 0, and why m[k] == 0 as a "check" adds keys.
  3. How do you check for a key without inserting? m.count(k), m.find(k) != m.end(), or m.contains(k) in C++20.
  4. set vs unordered_set for "seen before?" Both work; unordered_set is O(1) average, set O(log n) but sorted and with no bad worst case.
  5. What does s.insert(x) return? A pair: an iterator to the element, and a bool that is false if x was already there.
  6. 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).
  7. Why is the sum of letters a bad anagram key? Collisions: ad and bc both sum to 197. A key must be equal exactly when the things are equal.
  8. Group anagrams without sorting each word? Use the 26 letter counts as the key: O(k) per word instead of O(k log k).
  9. Iterating a map gives keys in what order? Ascending by operator< (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> and freq[w]++; a map prints keys A to Z, an unordered_map in no promised order. Clean words into keys: letters only, lowercase.
  • First repeat: a set of seen values turns O(n²) into O(n log n). There are two meanings: ask, and test on 5 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.