These are the notes for C++ Coding Questions, episode 24, placement practice for people who finished the SyntaxPilot C++ course. "Design a class" in an interview means: write a small class that behaves like a built-in type. Three classics: a Fraction class you can add, compare and print (operator overloading, and why 2/6 must equal 1/3), a Stack<T> that works for any type (class templates, and a clear error on an empty stack), and the rule of three (the shallow copy that frees the same memory twice).
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 cost.
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, including the compiler errors and warnings.
Real-life pictures
| In real life | In C++ |
|---|---|
| A recipe: 1/6 cup of sugar, then 1/6 more | adding two Fractions |
| A calculator's 0.1666...: decimals that never end | double is approximate |
| A cup marked 2/6 and a cup marked 1/3 hold the same sugar | equal values, different spellings: normalise |
| Cut the top and bottom by their biggest common divisor | std::gcd |
| A stack of plates: put on top, take from the top | a stack (last in, first out) |
| A stack of chai order slips: same rules, different thing | the same class for another type |
| One stencil, "Stack of ____", fill in the blank | template <typename T> |
| The marks register in a cupboard; you hold the key | an object holding a pointer to an array |
| Copying only the KEY: two keys, one register | a shallow copy |
| Both owners shred the same register at year end | a double free |
| Photocopying the register itself | a deep copy |
Q1: Design a Fraction class
Problem. Read two fractions p/q and r/s and a third x/y. Print their sum, and whether the sum equals x/y. Fractions are always shown in lowest terms, with the sign on top.
| Input | Output |
|---|---|
1 6 1 6 1 3 |
1/6 + 1/6 = 1/3, equal to 1/3? yes |
1 2 1 3 5 6 |
1/2 + 1/3 = 5/6, yes |
1 2 1 -3 1 6 |
1/2 + -1/3 = 1/6, yes |
Think out loud. Why not just use double?
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
double a = 0.1, b = 0.2;
cout << setprecision(17) << a + b << "\n"; // all the digits
cout << (a + b == 0.3 ? "equal" : "not equal") << "\n";
return 0;
}
Output:
0.30000000000000004
not equal
A double stores numbers in binary (base 2). 0.1 has no exact binary form, just like 1/3 has no exact decimal form, so it is stored as the nearest binary number, and the tiny errors show up when you add and compare. For money, ratios and exact answers we keep two whole numbers: a numerator (top) and a denominator (bottom). And we want to write a + b, a == b and cout << a as if Fraction were built in: that is operator overloading, giving an operator a meaning for your own class.
(If you must compare doubles, compare with a tolerance:)
#include <iostream>
#include <cmath>
using namespace std;
int main() {
double a = 0.1, b = 0.2;
cout << (fabs((a + b) - 0.3) < 1e-9 ? "close enough" : "different") << "\n";
return 0;
}
Output:
close enough
The obvious attempt: a class with +, then print it
#include <iostream>
using namespace std;
class Fraction {
public:
long long num, den; // numerator / denominator
Fraction(long long n, long long d) : num(n), den(d) {}
};
Fraction operator+(const Fraction& a, const Fraction& b) {
return Fraction(a.num * b.den + b.num * a.den, a.den * b.den);
}
int main() {
Fraction a(1, 6), b(1, 6);
cout << a + b << "\n";
return 0;
}
Compiler output (first lines; the full message lists every operator<< cout knows):
main.cpp: In function ‘int main()’:
main.cpp:16:10: error: no match for ‘operator<<’ (operand types are ‘std::ostream’ {aka ‘std::basic_ostream<char>’} and ‘Fraction’)
16 | cout << a + b << "\n";
| ~~~~ ^~ ~~~~~
| | |
| | Fraction
| std::ostream {aka std::basic_ostream<char>}
In file included from /usr/include/c++/13/iostream:41,
cout knows how to print int, double, string... It has no idea how to print our class.
Fix 1: operator<< and operator==
ostream& operator<<(ostream& out, const Fraction& f) {
return out << f.num << "/" << f.den; // return the stream so cout << a << b chains
}
bool operator==(const Fraction& a, const Fraction& b) {
return a.num == b.num && a.den == b.den;
}
operator<<takes the stream by reference (streams cannot be copied) and returns it, socout << a << " + " << bworks: each<<returnscoutfor the next one.const Fraction&means: read it without copying it, and promise not to change it.- Both are free functions (outside the class). That works here because
numanddenare public; with private members you would declare themfriendinside the class.
#include <iostream>
using namespace std;
class Fraction {
public:
long long num, den; // numerator / denominator
Fraction(long long n, long long d) : num(n), den(d) {}
};
Fraction operator+(const Fraction& a, const Fraction& b) {
return Fraction(a.num * b.den + b.num * a.den, a.den * b.den);
}
bool operator==(const Fraction& a, const Fraction& b) {
return a.num == b.num && a.den == b.den;
}
ostream& operator<<(ostream& out, const Fraction& f) {
return out << f.num << "/" << f.den; // return out: so << chains
}
int main() {
long long p, q, r, s, x, y;
cin >> p >> q >> r >> s >> x >> y;
Fraction a(p, q), b(r, s), c(x, y);
cout << a << " + " << b << " = " << a + b << "\n";
cout << "equal to " << c << "? " << (a + b == c ? "yes" : "no") << "\n";
return 0;
}
Input 1 6 1 6 1 3:
1/6 + 1/6 = 12/36
equal to 1/3? no
The sum 12/36 is correct but not in lowest terms, and equal to 1/3? no is wrong.
Why it fails
12/36, 2/6 and 1/3 are the same value spelled three ways. Comparing the fields only works if every fraction uses the same spelling.
Fix 2: normalise in the constructor
Every Fraction, the moment it is made, is stored in lowest terms with a positive denominator. Then == can simply compare the fields, and printing is always tidy.
- Move a minus sign from the bottom to the top:
if (den < 0) { num = -num; den = -den; }. - Divide both by their gcd, the greatest common divisor (the biggest number that divides both):
gcd(12, 36) = 12, so 12/36 → 1/3.std::gcdis in<numeric>(C++17) and always returns a non-negative value:gcd(-2, 6) = 2. gcd(0, 5) = 5, so 0/5 → 0/1. Theg != 0check only matters for 0/0.
#include <iostream>
#include <numeric>
using namespace std;
class Fraction {
public:
long long num, den; // numerator / denominator
Fraction(long long n, long long d) : num(n), den(d) {
if (den < 0) { num = -num; den = -den; } // sign on top
long long g = gcd(num, den); // std::gcd, never negative
if (g != 0) { num /= g; den /= g; } // lowest terms
}
};
Fraction operator+(const Fraction& a, const Fraction& b) {
return Fraction(a.num * b.den + b.num * a.den, a.den * b.den);
}
bool operator==(const Fraction& a, const Fraction& b) {
return a.num == b.num && a.den == b.den;
}
ostream& operator<<(ostream& out, const Fraction& f) {
return out << f.num << "/" << f.den; // return out: so << chains
}
int main() {
long long p, q, r, s, x, y;
cin >> p >> q >> r >> s >> x >> y;
Fraction a(p, q), b(r, s), c(x, y);
cout << a << " + " << b << " = " << a + b << "\n";
cout << "equal to " << c << "? " << (a + b == c ? "yes" : "no") << "\n";
return 0;
}
Input 1 6 1 6 1 3:
1/6 + 1/6 = 1/3
equal to 1/3? yes
Input 1 2 1 3 5 6:
1/2 + 1/3 = 5/6
equal to 5/6? yes
Input 1 2 1 -3 1 6:
1/2 + -1/3 = 1/6
equal to 1/6? yes
Input 0 5 0 7 0 1 (zeros):
0/1 + 0/1 = 0/1
equal to 0/1? yes
Cost. Each operation does a few multiplications and one gcd: O(log(min(num, den))) with Euclid's algorithm. Space: two numbers per fraction.
Things an interviewer may ask next.
- A zero denominator? The constructor should reject it: if (d == 0) throw invalid_argument("zero denominator");.
- Overflow? a.den * b.den can overflow long long for big denominators. Multiplying by b.den / gcd(a.den, b.den) (that is, using the lcm) keeps the numbers smaller:
#include <iostream>
#include <numeric>
using namespace std;
int main() {
long long a = 3000000000LL, b = 4000000000LL; // two big denominators
long long p = a * b; // 1.2e19 > LLONG_MAX (9.2e18)
cout << p << "\n";
cout << lcm(a, b) << "\n"; // the smallest common denominator
return 0;
}
Output:
-6446744073709551616
12000000000
The product wrapped around to a negative number (signed overflow is undefined behaviour; here it wrapped), while lcm is 12000000000.
Q2: A Stack that works for any type
Problem. Design a stack with push, pop, top, empty and size that works for ints and for strings from one class, and gives a clear error, not garbage, on top or pop of an empty stack.
Think out loud. A stack is last in, first out (LIFO): you only touch the top. A vector already gives us push_back, pop_back and back, so the stack is a thin wrapper around one. Edge case: an empty stack. back() or pop_back() on an empty vector is undefined behaviour: anything can happen.
The obvious attempt: IntStack
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class IntStack {
vector<int> items;
public:
void push(int x) { items.push_back(x); }
void pop() { items.pop_back(); }
int top() const { return items.back(); }
bool empty() const { return items.empty(); }
};
int main() {
IntStack plates;
plates.push(1);
plates.push(2);
cout << plates.top() << "\n";
IntStack orders; // now a stack of chai orders
orders.push(string("masala chai"));
cout << orders.top() << "\n";
return 0;
}
Compiler output:
main.cpp: In function ‘int main()’:
main.cpp:21:17: error: cannot convert ‘std::string’ {aka ‘std::__cxx11::basic_string<char>’} to ‘int’
21 | orders.push(string("masala chai"));
| ^~~~~~~~~~~~~~~~~~~~~
| |
| std::string {aka std::__cxx11::basic_string<char>}
main.cpp:9:19: note: initializing argument 1 of ‘void IntStack::push(int)’
9 | void push(int x) { items.push_back(x); }
IntStack can only ever hold ints. The "fix" of copy-pasting it into a StringStack (and a BookStack...) means every bug fix has to be made in every copy.
Fix: a class template
template <typename T> makes T a placeholder type. You write the class once; Stack<int> and Stack<string> make the compiler write (instantiate) a real class for each type. std::vector, std::stack and std::map are class templates too.
For the empty stack we throw an exception: throw out_of_range("...") stops the function and reports the problem. The caller can catch it; if nobody does, the program stops with terminate called after throwing an instance of 'std::out_of_range'. out_of_range is in <stdexcept>, and e.what() returns its message.
#include <iostream>
#include <vector>
#include <string>
#include <stdexcept>
using namespace std;
template <typename T> // T = any type, chosen later
class Stack {
vector<T> items;
public:
void push(const T& x) { items.push_back(x); }
void pop() {
if (items.empty()) throw out_of_range("pop() on an empty stack");
items.pop_back();
}
const T& top() const {
if (items.empty()) throw out_of_range("top() on an empty stack");
return items.back();
}
bool empty() const { return items.empty(); }
int size() const { return (int)items.size(); }
};
int main() {
Stack<int> plates;
plates.push(1);
plates.push(2);
cout << plates.top() << " (" << plates.size() << " plates)\n";
Stack<string> orders;
orders.push("masala chai");
orders.push("cutting chai");
cout << orders.top() << "\n";
orders.pop();
orders.pop();
try {
cout << orders.top() << "\n"; // nothing left
} catch (const out_of_range& e) {
cout << "error: " << e.what() << "\n";
}
return 0;
}
Output:
2 (2 plates)
cutting chai
error: top() on an empty stack
top() returns const T&: a reference, so a big T (a long string) is not copied, and const so the caller cannot change the top through it.
Cost. push: amortised O(1) (the vector sometimes grows and copies everything, but on average it is constant). pop, top, empty, size: O(1). Space: O(n).
In real code use std::stack<T> from <stack>; note that its top() and pop() do not check for empty: that is your job.
Q3: The rule of three
Problem. A Marks class stores n students' marks in an array it makes with new int[n] in the constructor and frees with delete[] in the destructor (~Marks(), which runs by itself when the object dies, here at the closing brace of main). Copies must be independent: if b is a copy of a and b changes a mark, a must not change.
The obvious attempt: a constructor and a destructor only
#include <iostream>
#include <algorithm>
using namespace std;
class Marks { // n students' marks, on the heap
int* data;
int n;
public:
Marks(int size) : data(new int[size]()), n(size) {}
~Marks() { delete[] data; } // give the memory back
void set(int i, int v) { data[i] = v; }
int get(int i) const { return data[i]; }
};
int main() {
Marks a(3);
a.set(0, 90);
Marks b = a; // a copy for the re-check
b.set(0, 35);
cout << "a[0] = " << a.get(0) << endl; // endl: print it right now
cout << "b[0] = " << b.get(0) << endl;
return 0;
}
Output:
Compiler (g++ -Wall):
In destructor ‘Marks::~Marks()’,
inlined from ‘int main()’ at main.cpp:23:1:
main.cpp:10:25: warning: pointer used after ‘void operator delete [](void*)’ [-Wuse-after-free]
10 | ~Marks() { delete[] data; } // give the memory back
| ^~~~
In destructor ‘Marks::~Marks()’,
inlined from ‘int main()’ at main.cpp:23:1:
main.cpp:10:25: note: call to ‘void operator delete [](void*)’ here
a[0] = 35
b[0] = 35
free(): double free detected in tcache 2
Three problems: the compiler warns (pointer used after delete, it can see the destructor run twice on one pointer), changing b changed a (a[0] = 35), and at the end the program is killed with free(): double free detected in tcache 2 (exit code 134, SIGABRT). endl flushes each line at once; with "\n" the two lines would still be waiting in the output buffer when the program is killed, and you would see only the error.
Why it fails: a shallow copy
a.data ──┐
├──> [90, 0, 0] one array
b.data ──┘
If you do not write a copy constructor, the compiler writes one that copies each field. data is a pointer, so the pointer is copied, not the array: a shallow copy. At the end of main, b's destructor deletes the array, then a's destructor deletes the same array again: a double free, which is undefined behaviour (here the memory allocator caught it and aborted).
Assignment has the same problem, plus a leak. With only a copy constructor written, c = a still uses the compiler's shallow assignment:
#include <iostream>
#include <algorithm>
using namespace std;
class Marks { // n students' marks, on the heap
int* data;
int n;
public:
Marks(int size) : data(new int[size]()), n(size) {}
~Marks() { delete[] data; } // give the memory back
Marks(const Marks& o) : data(new int[o.n]), n(o.n) {
copy(o.data, o.data + n, data);
}
void set(int i, int v) { data[i] = v; }
int get(int i) const { return data[i]; }
};
int main() {
Marks a(3);
a.set(0, 90);
Marks c(1);
c = a; // copy ASSIGNMENT: not written yet
c.set(0, 50);
cout << "a[0] = " << a.get(0) << endl;
cout << "c[0] = " << c.get(0) << endl;
return 0;
}
Output:
Compiler (g++ -Wall):
In destructor ‘Marks::~Marks()’,
inlined from ‘int main()’ at main.cpp:27:1:
main.cpp:10:25: warning: pointer used after ‘void operator delete [](void*)’ [-Wuse-after-free]
10 | ~Marks() { delete[] data; } // give the memory back
| ^~~~
In destructor ‘Marks::~Marks()’,
inlined from ‘int main()’ at main.cpp:27:1:
main.cpp:10:25: note: call to ‘void operator delete [](void*)’ here
a[0] = 50
c[0] = 50
free(): double free detected in tcache 2
c's own array (from Marks c(1)) is leaked, c and a share one array (setting c[0] changed a[0] to 50), and the program ends in a double free again.
Fix: the rule of three
If a class needs its own destructor, it almost certainly needs its own copy constructor and copy assignment operator too.
- Copy constructor
Marks(const Marks& o): makes a new array and copies the marks in (a deep copy). It runs when a new object is made from an existing one:Marks b = a;,Marks b(a);, passing or returning by value. - Copy assignment
Marks& operator=(const Marks& o): runs when an existing object is overwritten:c = a;. It must free its old array, and must survivea = a(self-assignment): without the check (or the copy-first order used here), it could delete its own array before copying from it. Making the new array before deleting the old one also keeps the object valid ifnewthrows.
#include <iostream>
#include <algorithm>
using namespace std;
class Marks { // n students' marks, on the heap
int* data;
int n;
public:
Marks(int size) : data(new int[size]()), n(size) {}
~Marks() { delete[] data; } // give the memory back
Marks(const Marks& o) : data(new int[o.n]), n(o.n) { // copy constructor
copy(o.data, o.data + n, data); // a NEW array, same marks
}
Marks& operator=(const Marks& o) { // copy assignment: c = a
if (this == &o) return *this; // a = a: nothing to do
int* fresh = new int[o.n];
copy(o.data, o.data + o.n, fresh);
delete[] data; // drop our old array
data = fresh;
n = o.n;
return *this;
}
void set(int i, int v) { data[i] = v; }
int get(int i) const { return data[i]; }
};
int main() {
Marks a(3);
a.set(0, 90);
Marks b = a; // copy constructor
b.set(0, 35);
Marks c(1);
c = a; // copy assignment
c.set(0, 50);
cout << "a[0] = " << a.get(0) << endl;
cout << "b[0] = " << b.get(0) << endl;
cout << "c[0] = " << c.get(0) << endl;
return 0;
}
Output:
a[0] = 90
b[0] = 35
c[0] = 50
Three separate arrays, no warning, no double free. A copy costs O(n): every mark is copied.
When each one runs, made visible:
#include <iostream>
#include <string>
using namespace std;
class Noisy {
string name;
public:
Noisy(const string& n) : name(n) { cout << "make " << name << "\n"; }
Noisy(const Noisy& o) : name(o.name + "'") { cout << "copy " << name << "\n"; }
Noisy& operator=(const Noisy& o) { name = o.name + "="; cout << "assign " << name << "\n"; return *this; }
~Noisy() { cout << "destroy " << name << "\n"; }
};
int main() {
Noisy a("a");
Noisy b = a; // copy constructor
Noisy c("c");
c = a; // copy assignment
return 0; // destroyed in reverse order
}
Output:
make a
copy a'
make c
assign a=
destroy a=
destroy a'
destroy a
Objects are destroyed in the reverse order of construction.
The easier way: the rule of zero
Let a member that already manages its memory, a vector or a unique_ptr, own it, and write none of the three:
#include <iostream>
#include <vector>
using namespace std;
class Marks { // the rule of zero: no destructor, no copy code
vector<int> data;
public:
Marks(int size) : data(size, 0) {}
void set(int i, int v) { data[i] = v; }
int get(int i) const { return data[i]; }
};
int main() {
Marks a(3);
a.set(0, 90);
Marks b = a; // vector copies its elements
b.set(0, 35);
Marks c(1);
c = a;
c.set(0, 50);
cout << "a[0] = " << a.get(0) << "\n";
cout << "b[0] = " << b.get(0) << "\n";
cout << "c[0] = " << c.get(0) << "\n";
return 0;
}
Output:
a[0] = 90
b[0] = 35
c[0] = 50
The rule of five (C++11) adds a move constructor and a move assignment operator, which steal the array from a temporary instead of copying it (fast). Writing any of the five usually means you need to think about all five; writing none (rule of zero) is best when you can.
Cost summary
| Program | Result | Cost |
|---|---|---|
0.1 + 0.2 == 0.3 with double |
not equal |
O(1), approximate |
| Fraction without normalising | 12/36, == 1/3 says no |
O(1) |
Fraction normalised with gcd |
1/3, yes |
O(log n) per operation |
IntStack with a string |
compile error | |
Stack<T> (vector inside) |
any type, clear error on empty | push amortised O(1), others O(1) |
Marks with a raw pointer, no copy functions |
a[0] = 35, double free |
|
Marks with the rule of three |
90 · 35 · 50 | a copy is O(n) |
Marks with a vector (rule of zero) |
90 · 35 · 50 | a copy is O(n), no code to write |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
a + b == 0.3 with double |
no error: not equal |
binary floating point is approximate | a Fraction, or compare with a tolerance |
cout << f with no operator<< |
error: no match for 'operator<<' |
cout does not know your class |
ostream& operator<<(ostream&, const Fraction&) |
operator<< returning void |
cout << a << b does not compile |
the next << needs the stream |
return out |
== on fractions not normalised |
no error: 12/36 == 1/3 is false |
same value, different spelling | normalise in the constructor |
| forgetting the sign | 1/-2 and -1/2 compare unequal |
the minus is in a different place | move it to the top |
IntStack for strings |
error: cannot convert 'std::string' to 'int' |
one type only | template <typename T> |
top() on an empty stack |
undefined behaviour | vector::back() on empty |
check and throw out_of_range |
| a destructor but no copy constructor | warning pointer used after ... delete, then free(): double free detected in tcache 2 |
shallow copy | rule of three, or a vector (rule of zero) |
| copy assignment without freeing the old array | memory leak | the old data is overwritten |
delete[] the old array |
| copy assignment that deletes first, without a self-check | a = a reads a deleted array (UB) |
source and target are the same object | if (this == &o) return *this; or copy first |
delete instead of delete[] for new int[n] |
undefined behaviour | array form mismatch | new[] pairs with delete[] |
Mini project: an exact Money class
A Money class for rupees and paise that never uses double: it stores the amount in paise as a long long, so adding and comparing are exact. This is how real payment code avoids floating-point errors. It uses friend functions (free functions declared inside the class that may read its private members), a validating constructor that throws, and setw(2)/setfill('0') to print 5 paise as .05.
#include <iostream>
#include <iomanip>
#include <stdexcept>
using namespace std;
class Money {
long long paise; // the exact amount, in paise
public:
Money(long long rupees, int p) : paise(rupees * 100 + p) {
if (p < 0 || p > 99) throw invalid_argument("paise must be 0..99");
}
explicit Money(long long totalPaise, bool) : paise(totalPaise) {}
friend Money operator+(const Money& a, const Money& b) { return Money(a.paise + b.paise, true); }
friend bool operator==(const Money& a, const Money& b) { return a.paise == b.paise; }
friend bool operator<(const Money& a, const Money& b) { return a.paise < b.paise; }
Money times(int qty) const { return Money(paise * qty, true); }
friend ostream& operator<<(ostream& out, const Money& m) {
long long p = m.paise;
if (p < 0) { out << "-"; p = -p; }
return out << "Rs " << p / 100 << "." << setw(2) << setfill('0') << p % 100 << setfill(' ');
}
};
int main() {
Money chai(12, 50), samosa(15, 0), gst(0, 5);
Money bill = chai.times(3) + samosa.times(2) + gst;
cout << "bill: " << bill << "\n";
cout << (Money(0, 10) + Money(0, 20) == Money(0, 30) ? "0.10 + 0.20 == 0.30: exact\n" : "not equal\n");
cout << (chai < samosa ? "chai is cheaper\n" : "samosa is cheaper\n");
try {
Money bad(1, 150);
cout << bad << "\n";
} catch (const invalid_argument& e) {
cout << "error: " << e.what() << "\n";
}
return 0;
}
Output:
bill: Rs 67.55
0.10 + 0.20 == 0.30: exact
chai is cheaper
error: paise must be 0..99
Practice questions (with solutions)
1. Your turn: make Fraction sortable. Add operator* and operator<, then sort a vector<Fraction>.
Solution
a/b < c/d is the same as a·d < c·b when b and d are positive, which the constructor guarantees. std::sort only needs operator<.
#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
using namespace std;
class Fraction {
public:
long long num, den;
Fraction(long long n, long long d) : num(n), den(d) {
if (den < 0) { num = -num; den = -den; }
long long g = gcd(num, den);
if (g != 0) { num /= g; den /= g; }
}
};
Fraction operator*(const Fraction& a, const Fraction& b) {
return Fraction(a.num * b.num, a.den * b.den);
}
bool operator<(const Fraction& a, const Fraction& b) {
return a.num * b.den < b.num * a.den; // dens > 0, so the sign is kept
}
ostream& operator<<(ostream& out, const Fraction& f) {
return out << f.num << "/" << f.den;
}
int main() {
vector<Fraction> v = {{1, 2}, {1, 3}, {3, 4}, {2, 6}, {-1, 5}};
sort(v.begin(), v.end()); // uses operator<
for (const Fraction& f : v) cout << f << " ";
cout << "\n" << Fraction(1, 2) * Fraction(2, 3) << "\n";
return 0;
}
Output:
-1/5 1/3 1/3 1/2 3/4
1/3
2. A template Queue<T> built from two stacks (first in, first out).
Solution
Push onto in. To read the front, if out is empty, pour everything from in into out (which reverses the order), then use out.top(). Each element is moved at most once, so every operation is amortised O(1).
#include <iostream>
#include <stack>
#include <string>
#include <stdexcept>
using namespace std;
template <typename T>
class Queue { // first in, first out, from two stacks
stack<T> in, out;
void move() { // refill out only when it is empty
if (out.empty())
while (!in.empty()) { out.push(in.top()); in.pop(); }
}
public:
void push(const T& x) { in.push(x); }
void pop() {
move();
if (out.empty()) throw out_of_range("pop() on an empty queue");
out.pop();
}
const T& front() {
move();
if (out.empty()) throw out_of_range("front() on an empty queue");
return out.top();
}
bool empty() const { return in.empty() && out.empty(); }
};
int main() {
Queue<string> tokens;
tokens.push("A1");
tokens.push("A2");
tokens.push("A3");
cout << tokens.front() << "\n";
tokens.pop();
tokens.push("A4");
while (!tokens.empty()) { cout << tokens.front() << " "; tokens.pop(); }
cout << "\n";
return 0;
}
Output:
A1
A2 A3 A4
3. A Matrix class with + and <<. Throw if the sizes differ.
Solution
A vector<vector<long long>> owns the memory (rule of zero). at() has two versions: one returns a reference so you can write x.at(0, 1) = 2, the const one returns a value for reading.
#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;
class Matrix {
int r, c;
vector<vector<long long>> a; // the rule of zero: vector owns the memory
public:
Matrix(int rows, int cols) : r(rows), c(cols), a(rows, vector<long long>(cols, 0)) {}
long long& at(int i, int j) { return a[i][j]; }
long long at(int i, int j) const { return a[i][j]; }
friend Matrix operator+(const Matrix& x, const Matrix& y) {
if (x.r != y.r || x.c != y.c) throw invalid_argument("sizes differ");
Matrix s(x.r, x.c);
for (int i = 0; i < x.r; i++)
for (int j = 0; j < x.c; j++) s.a[i][j] = x.a[i][j] + y.a[i][j];
return s;
}
friend ostream& operator<<(ostream& out, const Matrix& m) {
for (int i = 0; i < m.r; i++) {
for (int j = 0; j < m.c; j++) out << m.a[i][j] << (j + 1 < m.c ? " " : "");
out << "\n";
}
return out;
}
};
int main() {
Matrix x(2, 2), y(2, 2);
x.at(0, 0) = 1; x.at(0, 1) = 2; x.at(1, 0) = 3; x.at(1, 1) = 4;
y.at(0, 0) = 10; y.at(1, 1) = 10;
cout << x + y;
try {
Matrix z(3, 1);
cout << x + z;
} catch (const invalid_argument& e) {
cout << "error: " << e.what() << "\n";
}
return 0;
}
Output:
11 2
3 14
error: sizes differ
4. Rewrite Marks with a vector: the rule of zero.
Solution
Shown above in "The easier way": no destructor, no copy constructor, no copy assignment, and the same output 90 · 35 · 50.
Quick quiz
1. Which line runs the copy constructor? (the episode quiz)
Marks a(3); // line 1
Marks b = a; // line 2
Marks c(1); // line 3
c = a; // line 4
(A) Line 2 only (B) Line 4 only (C) Lines 2 and 4 (D) None of them
Answer
(A) Line 2 only. Line 2 makes a new object from a: copy constructor, even though it has an =. Line 4 overwrites c, which already exists: copy assignment. The Noisy program above prints copy a' for line 2 and assign a= for line 4.
2. What does cout << Fraction(4, -8); print with the normalising constructor?
Answer
-1/2: the sign moves to the top (−4/8), then both are divided by gcd 4.
3. Why must operator<< return ostream& and not ostream?
Answer
Streams cannot be copied (their copy constructor is deleted), and chaining must keep writing to the same cout. Returning a reference returns cout itself.
4. Stack<int> s; s.top(); with the episode's Stack, and no try: what happens?
Answer
The exception is not caught, so the program calls std::terminate and stops with a message like terminate called after throwing an instance of 'std::out_of_range', what(): top() on an empty stack, and exit code 134 (abort). That is still far better than undefined behaviour: it fails loudly, at the right line.
5. Which of these classes needs the rule of three: (A) class P { int x, y; }; (B) class Q { vector<int> v; }; (C) class R { int* buf; ~R() { delete[] buf; } };
Answer
(C). It owns raw memory through a pointer and frees it in its destructor. A and B are fine with the compiler's copies (B: vector copies itself deeply).
Interview questions
- What is operator overloading? Defining what an operator (
+,==,<<,[], ...) means for your own class, by writing a function namedoperator+and so on. - Member or free function for
operator+? A free (orfriend) function, so both sides convert the same way:2 + fandf + 2both work if there is a constructor fromint. - Why is
operator<<never a member of your class? Its left operand is the stream (cout << f); a member's left operand would have to be your class. - Why normalise a Fraction in the constructor? So every object has one canonical form, making
==simple and printing tidy; the class keeps the invariant "lowest terms, positive denominator". - What is a class template? A blueprint with a type parameter (
template <typename T>); the compiler generates a class per type used. - Where do template definitions go? In the header, because the compiler needs the full code to instantiate it for each type.
- What should
top()do on an empty stack? Not undefined behaviour: throw (std::out_of_range), assert, or document it as a precondition (asstd::stackdoes). - What is the rule of three? If a class needs a custom destructor, copy constructor or copy assignment operator, it almost certainly needs all three.
- Shallow vs deep copy? Shallow copies the pointer (two objects share one resource); deep copies the resource itself.
- When does the copy constructor run vs copy assignment? Copy constructor: a new object is created from another (
T b = a;, pass/return by value). Assignment: an existing object is overwritten (b = a;). - Why check self-assignment?
a = awould otherwise freea's array and then copy from the freed memory. - What are the rule of five and the rule of zero? Five: add move constructor and move assignment (C++11). Zero: use members that manage themselves (
vector,string,unique_ptr) and write none. - Why is
0.1 + 0.2 != 0.3?doubleis binary floating point; 0.1 and 0.2 are stored as the nearest binary fractions and the rounding errors add up.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Class design | Writing a small class with a clean, safe interface | Fraction, Stack<T> |
double / floating point |
A binary number with limited precision | 0.1 + 0.2 = 0.30000000000000004 |
| Tolerance | A small allowed difference when comparing doubles | fabs(x - y) < 1e-9 |
| Numerator / denominator | The top / bottom of a fraction | 1/3: 1 and 3 |
| Lowest terms | Top and bottom share no common divisor above 1 | 12/36 → 1/3 |
| gcd | Greatest common divisor: the biggest number that divides both | gcd(12, 36) = 12 |
| lcm | Least common multiple: the smallest number both divide | lcm(4, 6) = 12 |
| Normalise | Convert to one canonical form | the sign on top, lowest terms |
| Invariant | A rule an object always keeps | "den > 0" |
| Operator overloading | Giving an operator a meaning for your class | operator+ |
ostream& |
A reference to an output stream such as cout |
ostream& operator<<(ostream& out, ...) |
const T& |
Pass by const reference: no copy, no change | const Fraction& a |
friend |
A non-member function allowed to read private members | friend ostream& operator<<(...) |
| Stack (LIFO) | Last in, first out | a stack of plates |
| Queue (FIFO) | First in, first out | a token queue |
| Class template | A class with a type parameter | template <typename T> class Stack |
| Instantiation | The compiler generating a real class for one type | Stack<int> |
| Exception | An error reported with throw and handled with catch |
throw out_of_range("...") |
std::out_of_range |
The standard exception for an index or state out of range | <stdexcept> |
try / catch |
Run code and handle an exception it throws | catch (const out_of_range& e) |
e.what() |
The exception's message | top() on an empty stack |
| Amortised O(1) | O(1) on average over many operations | vector::push_back |
| Destructor | Runs automatically when an object dies | ~Marks() |
| Copy constructor | Makes a new object from an existing one | Marks(const Marks& o) |
| Copy assignment operator | Overwrites an existing object with another | Marks& operator=(const Marks& o) |
| Shallow copy | Copies the pointer: two objects share one resource | b.data == a.data |
| Deep copy | Copies the resource itself | a new array with the same marks |
| Double free | Freeing the same memory twice | free(): double free detected in tcache 2 |
| Self-assignment | Assigning an object to itself | a = a; |
| Rule of three | Destructor, copy constructor, copy assignment: all or none | Marks |
| Rule of five | The three plus move constructor and move assignment | C++11 |
| Rule of zero | Let members like vector manage resources; write none |
vector<int> data; |
endl |
Writes a newline and flushes the output at once | lines printed before a crash |
| SIGABRT / exit code 134 | The program was aborted (here by the memory allocator) | double free |
Summary
doubleis approximate; for exact values keep whole numbers: a Fraction (numerator, denominator) or Money in paise.- Operator overloading makes a class feel built in:
operator+,operator==, andostream& operator<<that returns the stream. - Normalise once, in the constructor (sign on top, divide by
gcd), and==becomes a simple field comparison. template <typename T>writes one class for every type; throwstd::out_of_rangeinstead of undefined behaviour on an empty stack.- A class that owns raw memory needs the rule of three: destructor, deep-copy constructor, copy assignment (free the old, handle
a = a). Better: the rule of zero with avector.
Next episode: OOP output questions: virtual vs non-virtual calls, the missing virtual destructor, object slicing, and the order of constructors and destructors.