12  Midterm Review (CSS 342)

13 Midterm Review (CSS 342)

Week 5, Session 2. CSS 342.

This chapter is a structured re-pass through chapters 1–9, organized as the questions you are most likely to see on a midterm and the wrong answers students give.

13.1 What the midterm covers

Chapter Topic Typical question style
1 Environment, compile, git Multiple choice on flags / commands
2 vector, pair, iterators Trace output of a small program
3 set/map/stack/queue “Which container would you pick for X?”
4 Pointers, heap, leaks Predict output, find the bug
5 Classes, ctor/dtor, .h/.cpp split Write a class given a spec
6 Operator overloading Write operator<< and operator<
7 Rule of Three Identify what is missing; write the missing piece
8 Templates Generalize a function or class
9 Recursion Trace, or write recursive function

13.2 Container selection — rapid fire

Match the requirement to the container. Answers at the end of this section.

  1. Track which integers in [0, n-1] you’ve seen, sorted.
  2. Track which strings you’ve seen, sorted by insertion order.
  3. Word frequency in a 10 MB book.
  4. Always return the largest of a changing set.
  5. Process tasks in FIFO order.
  6. Maintain a sorted set of timestamps with frequent insertions and “next-larger” queries.

Answers: 1: set<int>. 2: vector<string> (order is insertion). 3: unordered_map<string,int>. 4: priority_queue<int>. 5: queue<...>. 6: set<int> (or map).

13.3 Pointer / memory snippets — predict output

13.3.1 Snippet A

int x = 5;
int* p = &x;
*p = 7;
cout << x << endl;

Output: 7. Writing through the pointer modifies the original.

13.3.2 Snippet B

int* arr = new int[3]{10, 20, 30};
delete arr;    // <-- bug

Output: undefined behavior (probable leak of two ints, possible crash). Should be delete[] arr;.

13.3.3 Snippet C

void f(vector<int> v) { v.push_back(99); }

int main() {
  vector<int> v = {1, 2, 3};
  f(v);
  cout << v.size() << endl;
}

Output: 3. v is passed by value, so push_back modifies a copy. To modify the caller’s vector, change to void f(vector<int>& v).

13.4 Rule of Three — what’s missing?

class IntList {
 public:
  IntList(int n) : size_(n), data_(new int[n]) {}
  ~IntList() { delete[] data_; }
  // ... no copy ctor, no operator=
 private:
  int* data_;
  int size_;
};

int main() {
  IntList a(10);
  IntList b = a;      // <-- ???
}

What is wrong? b = a invokes the default copy constructor, which copies the pointer. Both a.data_ and b.data_ point to the same heap memory. On destruction, both call delete[]. Double-free.

Fix: add a copy constructor (deep copy) and operator= (deep copy with self-assignment guard). See chapter 7.

13.5 Operator overloading — write the missing piece

Given:

class Point {
 public:
  Point(int x, int y) : x_(x), y_(y) {}
 private:
  int x_, y_;
  friend ostream& operator<<(ostream&, const Point&);
};

Implement operator<< that prints "(3, 4)".

ostream& operator<<(ostream& os, const Point& p) {
  return os << "(" << p.x_ << ", " << p.y_ << ")";
}

Notice the return type is ostream& — for chaining. The function is non-member because the left operand is ostream. It is friend so it can access private fields.

13.6 Templates — instantiate

Given:

template <typename T>
T maxOf(T a, T b) { return a > b ? a : b; }

What types does each of these instantiate?

  • maxOf(3, 7) → T = int
  • maxOf(3.0, 7.0) → T = double
  • maxOf("foo", "bar") → T = const char* (and not string; surprising!)
  • maxOf(string("foo"), string("bar")) → T = string

The const char* case compares pointers, not strings. This is a classic interview trap. If you want string comparison, cast to string.

13.7 Recursion — trace factorial(5)

factorial(5)
└─ 5 * factorial(4)
        └─ 4 * factorial(3)
                └─ 3 * factorial(2)
                        └─ 2 * factorial(1)
                                └─ 1 * factorial(0)
                                        └─ 1
                                └─ 1
                        └─ 2
                └─ 6
        └─ 24
└─ 120

Five recursive calls, six total. Returns 120.

13.8 Recursion — write sumArray(int* arr, int n)

int sumArray(int* arr, int n) {
  if (n == 0) return 0;
  return arr[n - 1] + sumArray(arr, n - 1);
}

Or equivalently, recursing from the front using an offset.

13.9 Top 5 things to review tonight

  1. Member initializer lists. Box(int w, int h) : width_(w), height_(h) {} not assignment inside the body.
  2. Overflow-safe midpoint. lo + (hi - lo) / 2, always.
  3. * and & in declarations vs. expressions. int* p = &x; declares; *p = 5; dereferences.
  4. The three Rule-of-Three signatures. T(const T&), T& operator=(const T&), ~T().
  5. Range-based for with &. for (auto& x : v) to modify; for (const auto& x : v) to read-only-without-copy.

13.10 Common wrong answers I see every quarter

  • Writing for (int i = 0; i < v.size() - 1; i++) when the vector is empty. v.size() - 1 for an empty vector is SIZE_MAX because size_t is unsigned.
  • Forgetting [] in delete[] for arrays.
  • Comparing string to "foo" thinking it is a pointer compare. (It is not — string::operator== works.)
  • Writing if (set.find(x) == set.end()) {} instead of if (set.count(x) == 0) {}. Both work; the second is cleaner.
  • Forgetting return *this; in operator=.

13.11 Try it

Take any class you wrote during weeks 1–4 and check: does it own heap memory? If yes, does it have all three of (destructor, copy ctor, copy assignment)? If no, fix it now. Compile with -fsanitize=address and run a test program that copies and reassigns.

13.12 What’s next

After the midterm we shift to discrete math (chapters 11, 12), then algorithm analysis (chapter 13). The C++ mechanics part of the course is done — from chapter 13 onward, the language is mostly a vehicle for the algorithms.

You are here Coming up
Midterm review of C++ mechanics Chapter 11: propositional logic