SyntaxPilot
Courses/C++ Coding Questions/Lesson 11
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 11 of 30

Sorting questions

sort with a custom comparator (the <= strict weak ordering crash)sort by two keys (tie-break, stable_sort)sort strings by length then alphabet

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 <:

  1. comp(a, a) is always false (nothing goes before itself).
  2. If comp(a, b) is true, then comp(b, a) is false (two items never both go first).
  3. If a goes before b and b goes before c, then a goes before c.
  4. 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

  1. What does a comparator passed to std::sort return? true if its first argument should come before the second.
  2. What is strict weak ordering? The rules a comparator must follow: comp(a, a) is false; comp(a, b) and comp(b, a) are never both true; it is transitive; "equivalence" is transitive.
  3. Why can return a >= b; crash std::sort? The partition loop relies on comp(x, x) being false to stop scanning; with >= it can run past the end of the range: undefined behaviour.
  4. Is std::sort stable? What is? No. std::stable_sort is (merge sort), at the cost of extra memory.
  5. How do you sort by two keys? One comparator: if key 1 differs, compare key 1; otherwise compare key 2. Or compare tuples / pairs.
  6. How do you sort in descending order? greater<int>(), [](int a, int b) { return a > b; }, or sort and reverse, or sort(v.rbegin(), v.rend()).
  7. Why take the arguments by const&? The comparator runs O(n log n) times; by value copies every object every time.
  8. Why might a broken comparator pass your tests? For ranges of 16 or fewer elements libstdc++'s std::sort is 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 >= b crashed std::sort on 100 equal marks.
  • std::sort is not stable; sorting twice only works with stable_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 < b says both items go first. pair and tuple compare 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).