These are the notes for C++ Coding Questions, episode 11, placement practice for people who finished the SyntaxPilot C++ course. Sorting questions: sorting numbers small to big is one line, but interviews ask for your own order. Today: a comparator with one extra = that makes std::sort crash, a rank list sorted by two keys (and why sorting twice breaks it), and words sorted by length, then A to Z (and the innocent-looking || that gives nonsense).
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, libstdc++), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real.
Real-life pictures
| In real life | In C++ |
|---|---|
| The assembly line, tallest in front | sorting with your own order (a comparator) |
| The PT teacher's rule "taller or the same height, go in front": two students of the same height must each go in front of the other, forever | return a >= b; breaks sort's rule: for equal items the comparator must say false |
| "Strictly taller, go in front": the same height, nobody moves | return a > b;, or greater<int>() |
| The class rank list: marks high to low, the same marks in A to Z order | sorting by two keys with a tie-break |
| Re-sorting the A to Z register only by marks, hoping the names stay in order | std::sort is not stable; std::stable_sort is |
| A spelling-bee list: short words first, the same length in dictionary order | if (a.size() != b.size()) return a.size() < b.size(); return a < b; |
How a comparator works
sort(v.begin(), v.end(), comp) sorts with your order. comp(a, b) answers one question: should a go before b? It returns true or false. We usually write it as a lambda, a small function written right where it is used:
sort(v.begin(), v.end(), [](int a, int b) { return a > b; }); // highest first
The rule (strict weak ordering). A comparator must behave like <:
comp(a, a)is alwaysfalse(nothing goes before itself).- If
comp(a, b)istrue, thencomp(b, a)isfalse(two items never both go first). - If a goes before b and b goes before c, then a goes before c.
- Items that are "equal" (neither goes first) behave consistently: if a ~ b and b ~ c, then a ~ c.
Break it and the behaviour is undefined: a crash, a wrong order, or (worst) it seems to work.
Q1: Marks in descending order
Problem. Read n marks and print them highest first. 3 9 1 9 4 → 9 9 4 3 1.
Think out loud. Equal marks. A whole class with the same marks. The test block: when n is 0, the program makes 100 students who all have 7 marks.
The obvious attempt: a >= b
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int& x : v) cin >> x;
if (n == 0) v.assign(100, 7); // test: 100 students, all 7 marks
sort(v.begin(), v.end(), [](int a, int b) { return a >= b; });
for (int i = 0; i < min((int)v.size(), 10); i++) cout << v[i] << " ";
cout << "(" << v.size() << " sorted)\n";
return 0;
}
Input 5 / 3 9 1 9 4:
9 9 4 3 1 (5 sorted)
Correct. Now 0 (100 equal marks):
double free or corruption (out)
(the program was killed: signal 6, SIGABRT)
The program crashed (the compiler shows Runtime Error (SIGABRT)). "double free or corruption" means the memory around the vector was overwritten.
Why. With >=, comp(7, 7) is true: seven goes before seven, and the other seven also goes before the first one. That is the PT teacher's rule. To be fast, std::sort's partition step scans without bounds checks, trusting that some element will stop the scan (an element that is not "before" the pivot). With >=, equal elements never stop it, so it runs past the end of the vector and writes outside it. On 5 numbers it looked fine (std::sort uses insertion sort for small ranges), which is exactly why this bug escapes small tests.
Fix: strictly greater
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int& x : v) cin >> x;
if (n == 0) v.assign(100, 7); // test: 100 students, all 7 marks
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
for (int i = 0; i < min((int)v.size(), 10); i++) cout << v[i] << " ";
cout << "(" << v.size() << " sorted)\n";
return 0;
}
9 9 4 3 1 (5 sorted)
7 7 7 7 7 7 7 7 7 7 (100 sorted)
The ready-made comparator greater<int>() (header <functional>) does the same:
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int& x : v) cin >> x;
if (n == 0) v.assign(100, 7); // test: 100 students, all 7 marks
sort(v.begin(), v.end(), greater<int>());
for (int i = 0; i < min((int)v.size(), 10); i++) cout << v[i] << " ";
cout << "(" << v.size() << " sorted)\n";
return 0;
}
9 9 4 3 1 (5 sorted)
Complexity. std::sort is O(n log n) comparisons, O(log n) extra space.
Q2: The rank list (two keys)
Problem. Read n students (name marks). Print them with marks high to low; students with the same marks in A to Z order of name.
Think out loud. Lots of ties. And more than 16 students: below 17, std::sort only runs insertion sort, which happens to keep equal items in order, so a wrong approach can look right. The test class has 20 students; 7 of them have 90.
20
Asha 90 Ravi 75 Neha 90 Arjun 82 Priya 75
Kabir 90 Meera 82 Dev 68 Isha 90 Rohit 75
Zoya 82 Aman 90 Tara 68 Vikram 75 Diya 82
Karan 90 Sneha 75 Yash 68 Nisha 82 Om 90
The obvious attempt: sort by name, then sort by marks
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Student { string name; int marks; };
int main() {
int n;
cin >> n;
vector<Student> s(n);
for (auto& x : s) cin >> x.name >> x.marks;
sort(s.begin(), s.end(), [](const Student& a, const Student& b) { return a.name < b.name; });
sort(s.begin(), s.end(), [](const Student& a, const Student& b) { return a.marks > b.marks; });
for (int i = 0; i < n; i++)
cout << s[i].name << " " << s[i].marks << (i % 5 == 4 ? "\n" : ", ");
return 0;
}
Asha 90, Om 90, Aman 90, Isha 90, Kabir 90
Karan 90, Neha 90, Nisha 82, Zoya 82, Meera 82
Diya 82, Arjun 82, Priya 75, Ravi 75, Rohit 75
Sneha 75, Vikram 75, Dev 68, Tara 68, Yash 68
The marks are in order, but the names are not: Asha, Om, Aman, Isha. The second sort scrambled the first.
Why. A sort is stable when equal items keep the order they had before. std::sort (an introsort: quicksort + heapsort + insertion sort) is not stable: it promises nothing about the order of equal items.
Fix 1: stable_sort for the second sort
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Student { string name; int marks; };
int main() {
int n;
cin >> n;
vector<Student> s(n);
for (auto& x : s) cin >> x.name >> x.marks;
sort(s.begin(), s.end(), [](const Student& a, const Student& b) { return a.name < b.name; });
stable_sort(s.begin(), s.end(), [](const Student& a, const Student& b) { return a.marks > b.marks; });
for (int i = 0; i < n; i++)
cout << s[i].name << " " << s[i].marks << (i % 5 == 4 ? "\n" : ", ");
return 0;
}
Aman 90, Asha 90, Isha 90, Kabir 90, Karan 90
Neha 90, Om 90, Arjun 82, Diya 82, Meera 82
Nisha 82, Zoya 82, Priya 75, Ravi 75, Rohit 75
Sneha 75, Vikram 75, Dev 68, Tara 68, Yash 68
stable_sort (a merge sort) keeps the A to Z order from the first sort among students with equal marks. O(n log n) time, up to O(n) extra memory.
Fix 2 (best): one sort with a tie-break comparator
Ask key 2 only when key 1 is equal:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Student { string name; int marks; };
int main() {
int n;
cin >> n;
vector<Student> s(n);
for (auto& x : s) cin >> x.name >> x.marks;
sort(s.begin(), s.end(), [](const Student& a, const Student& b) {
if (a.marks != b.marks) return a.marks > b.marks; // key 1: marks, high first
return a.name < b.name; // key 2: name, A to Z
});
for (int i = 0; i < n; i++)
cout << s[i].name << " " << s[i].marks << (i % 5 == 4 ? "\n" : ", ");
return 0;
}
Aman 90, Asha 90, Isha 90, Kabir 90, Karan 90
Neha 90, Om 90, Arjun 82, Diya 82, Meera 82
Nisha 82, Zoya 82, Priya 75, Ravi 75, Rohit 75
Sneha 75, Vikram 75, Dev 68, Tara 68, Yash 68
One sort, and the result does not depend on the order of the input. Note the comparator takes const Student&: a comparator runs about n log n times, and taking the structs by value would copy two strings every time.
Q3: Words by length, then A to Z
Problem. Read words and print them shortest first; words of the same length in dictionary order. kiwi fig apple banana date pear plum → fig date kiwi pear plum apple banana.
Attempt 1: compare only the sizes
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
vector<string> w;
string x;
while (cin >> x) w.push_back(x);
sort(w.begin(), w.end(), [](const string& a, const string& b) {
return a.size() < b.size();
});
for (const string& s : w) cout << s << " ";
cout << "\n";
return 0;
}
fig kiwi date pear plum apple banana
Shortest first, but kiwi date pear plum are in the order they were typed: key 2 is missing.
Attempt 2: add || a < b
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
vector<string> w;
string x;
while (cin >> x) w.push_back(x);
sort(w.begin(), w.end(), [](const string& a, const string& b) {
return a.size() < b.size() || a < b;
});
for (const string& s : w) cout << s << " ";
cout << "\n";
return 0;
}
date apple banana fig kiwi pear plum
Now apple (5 letters) comes before fig (3 letters): not even sorted by length.
Why. Ask the comparator both ways:
comp(fig, apple): 3 < 5 → true (fig first)
comp(apple, fig): 5 < 3 || "apple" < "fig" → true (apple first)
Both true: rule 2 of strict weak ordering is broken, so the result is undefined (here, garbage order).
Fix: key 2 only on a tie
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
vector<string> w;
string x;
while (cin >> x) w.push_back(x);
sort(w.begin(), w.end(), [](const string& a, const string& b) {
if (a.size() != b.size()) return a.size() < b.size();
return a < b;
});
for (const string& s : w) cout << s << " ";
cout << "\n";
return 0;
}
fig date kiwi pear plum apple banana
Shortcut: compare pairs. A pair (and a tuple) compares its first item, and only on a tie the next one, so it writes the tie-break for you:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
vector<string> w;
string x;
while (cin >> x) w.push_back(x);
sort(w.begin(), w.end(), [](const string& a, const string& b) {
return pair(a.size(), a) < pair(b.size(), b);
});
for (const string& s : w) cout << s << " ";
cout << "\n";
return 0;
}
fig date kiwi pear plum apple banana
Complexity. O(n log n) comparisons; comparing two words costs up to their length, so O(L · n log n) for words of length up to L. (The pair version also copies each word into the pair; for big inputs prefer the if version.)
Complexity summary
| Program | Time | Extra space |
|---|---|---|
sort(b, e, comp) |
O(n log n) | O(log n) |
stable_sort(b, e, comp) |
O(n log n) (O(n log² n) if no extra memory is available) | O(n) |
sort by name, then stable_sort by marks |
2 × O(n log n) | O(n) |
| one sort with a tie-break | O(n log n) | O(log n) |
| strings by length, then A to Z | O(L · n log n) | O(log n) |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
[](int a, int b) { return a >= b; } |
double free or corruption (out), Runtime Error (SIGABRT) |
comp(a, a) must be false |
a > b, or greater<int>() |
sort by name, then sort by marks |
ties not in A to Z order | std::sort is not stable |
stable_sort, or one tie-break comparator |
| testing comparators on 5 items only | "works" | under 17 items std::sort is insertion sort |
test with 20+ items and many ties |
return a.size() < b.size() \|\| a < b; |
apple before fig |
comp(a, b) and comp(b, a) both true |
key 2 only when key 1 is equal |
comparator taking Student a, Student b |
no error, just slow | copies both every comparison | const Student& |
| printing or changing data inside a comparator | strange order, slow | it runs n log n times, in any order | keep it a pure, quick yes/no |
Your turn: sort by frequency (solution)
Problem. Sort numbers by how often they appear, most frequent first; on a tie, the smaller number first. 4 6 2 6 4 4 6 3 → 4 4 4 6 6 6 2 3 (4 and 6 both appear 3 times: 4 first).
Idea. Count with a map, then one sort with a two-key comparator. The lambda captures the map by reference ([&]).
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main() {
vector<int> v;
int x;
while (cin >> x) v.push_back(x);
map<int, int> freq;
for (int y : v) freq[y]++;
sort(v.begin(), v.end(), [&](int a, int b) {
if (freq[a] != freq[b]) return freq[a] > freq[b]; // key 1: more frequent first
return a < b; // key 2: smaller number first
});
for (int y : v) cout << y << " ";
cout << "\n";
return 0;
}
4 4 4 6 6 6 2 3
O(n log n) time (each freq[a] lookup in a map adds a log factor: O(n log n · log k); copy the counts into an unordered_map or a vector of pairs for speed), O(k) extra space for k different numbers.
Practice questions (with solutions)
1. Sort points by distance from the origin (ties: by x, then y). Compare squared distances: no sqrt, no rounding.
Solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Point { int x, y; };
int main() {
int n;
cin >> n;
vector<Point> p(n);
for (auto& q : p) cin >> q.x >> q.y;
sort(p.begin(), p.end(), [](const Point& a, const Point& b) {
long long da = 1LL * a.x * a.x + 1LL * a.y * a.y; // squared distance: no sqrt, no doubles
long long db = 1LL * b.x * b.x + 1LL * b.y * b.y;
if (da != db) return da < db;
return make_pair(a.x, a.y) < make_pair(b.x, b.y);
});
for (auto& q : p) cout << "(" << q.x << "," << q.y << ") ";
cout << "\n";
return 0;
}
Input 4 / 3 4 / 1 1 / -1 1 / 0 2:
(-1,1) (1,1) (0,2) (3,4)
2. Even numbers first, keeping the original order of the evens and of the odds. "a goes first only if a is even and b is odd" is a valid strict weak ordering, and stable_sort keeps the order inside each group. (std::stable_partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; }) does the same in O(n).)
Solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v;
int x;
while (cin >> x) v.push_back(x);
stable_sort(v.begin(), v.end(), [](int a, int b) {
return a % 2 == 0 && b % 2 != 0; // a goes first only if a is even and b is odd
});
for (int y : v) cout << y << " ";
cout << "\n";
return 0;
}
2 8 4 6 5 1 7
3. The largest number from a list of numbers. 3 30 34 5 9 → 9534330. Put a before b when a + b > b + a as strings ("9" + "34" = "934" beats "349"). Watch the all-zeros case.
Solution
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
vector<string> s;
string x;
while (cin >> x) s.push_back(x);
sort(s.begin(), s.end(), [](const string& a, const string& b) {
return a + b > b + a; // "9" + "34" = "934" beats "349"
});
string ans;
for (auto& t : s) ans += t;
if (!ans.empty() && ans[0] == '0') ans = "0"; // 0 0 0 → 0, not 000
cout << ans << "\n";
return 0;
}
9534330
Input 0 0:
0
Mini project: a coding contest leaderboard
Three keys: more problems solved first, then fewer minutes, then name A to Z. tuple compares item by item; -a.solved turns "more first" into "smaller first".
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;
struct Entry { string name; int solved; int minutes; };
int main() {
int n;
cin >> n;
vector<Entry> e(n);
for (auto& x : e) cin >> x.name >> x.solved >> x.minutes;
// key 1: more problems solved · key 2: fewer minutes · key 3: name A to Z
sort(e.begin(), e.end(), [](const Entry& a, const Entry& b) {
return tuple(-a.solved, a.minutes, a.name) < tuple(-b.solved, b.minutes, b.name);
});
for (int i = 0; i < n; i++)
cout << i + 1 << ". " << e[i].name << " (" << e[i].solved << " solved, " << e[i].minutes << " min)\n";
return 0;
}
1. Isha (5 solved, 120 min)
2. Kabir (5 solved, 120 min)
3. Arjun (4 solved, 80 min)
4. Neha (4 solved, 80 min)
5. Asha (4 solved, 95 min)
Quick quiz
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
vector<pair<int, string>> v =
{{2, "b"}, {1, "z"}, {2, "a"}, {1, "y"}};
sort(v.begin(), v.end());
for (auto& [k, s] : v) cout << s;
cout << "\n";
return 0;
}
(A) zyba (B) yzab (C) abyz (D) bazy
Answer
(B) yzab. With no comparator, sort uses < on the pairs: the int first, and only on a tie the string. So (1, y), (1, z), (2, a), (2, b).
yzab
Interview questions
- What does a comparator passed to
std::sortreturn?trueif its first argument should come before the second. - What is strict weak ordering? The rules a comparator must follow:
comp(a, a)is false;comp(a, b)andcomp(b, a)are never both true; it is transitive; "equivalence" is transitive. - Why can
return a >= b;crashstd::sort? The partition loop relies oncomp(x, x)being false to stop scanning; with>=it can run past the end of the range: undefined behaviour. - Is
std::sortstable? What is? No.std::stable_sortis (merge sort), at the cost of extra memory. - How do you sort by two keys? One comparator: if key 1 differs, compare key 1; otherwise compare key 2. Or compare
tuples /pairs. - How do you sort in descending order?
greater<int>(),[](int a, int b) { return a > b; }, or sort and reverse, orsort(v.rbegin(), v.rend()). - Why take the arguments by
const&? The comparator runs O(n log n) times; by value copies every object every time. - Why might a broken comparator pass your tests? For ranges of 16 or fewer elements libstdc++'s
std::sortis plain insertion sort, which tolerates (and hides) many broken comparators.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Comparator | A function that says whether a goes before b | [](int a, int b) { return a > b; } |
| Lambda | A small unnamed function written where it's used | [](int a, int b) { ... } |
Capture [&] |
Lets a lambda use local variables by reference | [&](int a, int b) { return freq[a] > freq[b]; } |
| Strict weak ordering | The rules a comparator must follow (like <) |
comp(a, a) is false |
| Descending order | Highest first | 9 9 4 3 1 |
greater<int>() |
A ready-made "a > b" comparator from <functional> |
sort(b, e, greater<int>()) |
| Key | What you sort by | marks, name |
| Tie-break | The second key, used only when the first is equal | same marks → compare names |
| Stable sort | Equal items keep their original order | stable_sort |
std::stable_sort |
A stable O(n log n) sort (merge sort) | stable_sort(b, e, comp) |
| Introsort | std::sort's algorithm: quicksort, heapsort if too deep, insertion sort for small parts |
not stable |
| Insertion sort | Sorts by inserting each item into the sorted part; stable | used for ≤ 16 items |
struct |
A type grouping named values | struct Student { string name; int marks; }; |
pair / tuple |
Groups of 2 / n values; compared item by item | pair(a.size(), a) |
| Lexicographic order | Dictionary order: compare item by item | "apple" < "fig" |
| Undefined behaviour (UB) | Code the C++ standard gives no meaning to | a broken comparator |
| SIGABRT | The signal a program gets when it aborts itself | "double free or corruption" |
| O(n log n) | Sorting-speed growth | std::sort |
Summary
- A comparator answers "should a go before b?" and must say false for equal items: never
>=or<=.a >= bcrashedstd::sorton 100 equal marks. std::sortis not stable; sorting twice only works withstable_sort. Better: one sort with a tie-break comparator.- With two keys, look at key 2 only when key 1 is equal;
size < size || a < bsays both items go first.pairandtuplecompare in order and write the tie-break for you. - Test comparators with more than 16 items and many ties: small tests lie.
Next episode: Binary search questions: lower_bound and upper_bound, the first and last occurrence of a number and its count, and binary search on the answer (the integer square root, and the mid overflow).