MTH 4300 Midterm 2 Practice Questions

Exam format

Exams in MTH 4300 revolve around 3 classes of questions:

Tracing - evaluating the output of a code snippet
Debugging - given a code snippet, diagnose and fix the errors
Implementation - write code from scratch to solve a problem

A note about partial credit

Clarity is the only way you'll get points. If you don't even understand what it is you're trying to say, then how can I?

Tracing

Consider the following program. Box performs a deep copy of its int value and prints a message from each special member function.

#include <iostream>

class Box {
    int* val;
public:
    Box(int x) : val(new int(x)) {
        std::cout << "new " << *val << std::endl;
    }
    Box(const Box& o) : val(new int(*o.val)) {
        std::cout << "copy " << *val << std::endl;
    }
    Box& operator=(const Box& o) {
        if (this == &o) return *this;
        *val = *o.val;
        std::cout << "assign " << *val << std::endl;
        return *this;
    }
    ~Box() {
        std::cout << "del " << *val << std::endl;
        delete val;
    }
    void set(int x) { *val = x; }
    int  get() const { return *val; }
};

int main() {
    Box a(1);
    Box b = a;
    b.set(99);
    std::cout << a.get() << " " << b.get() << std::endl;

    Box c(2);
    c = a;
    c.set(42);
    std::cout << a.get() << " " << c.get() << std::endl;
    return 0;
}

Write the exact output produced by this program, in order. Pay close attention to when copy construction vs. copy assignment is called, and to the order in which local objects are destroyed.

Consider the following program. Shape, Circle, and Square each print from their constructor and destructor. name() is virtual in Shape but Square does not override it.

#include <iostream>
#include <string>

class Shape {
public:
    Shape() { std::cout << "Shape()" << std::endl; }
    virtual ~Shape() { std::cout << "~Shape()" << std::endl; }
    virtual std::string name() const { return "Shape"; }
    void describe() const {
        std::cout << "I am a " << name() << std::endl;
    }
};

class Circle : public Shape {
public:
    Circle() { std::cout << "Circle()" << std::endl; }
    ~Circle() { std::cout << "~Circle()" << std::endl; }
    std::string name() const override { return "Circle"; }
};

class Square : public Shape {
public:
    Square() { std::cout << "Square()" << std::endl; }
    ~Square() { std::cout << "~Square()" << std::endl; }
};

int main() {
    Shape* s1 = new Circle();
    Shape* s2 = new Square();

    s1->describe();
    s2->describe();

    delete s1;
    delete s2;
    return 0;
}

Write the exact output produced by this program, in order. Be careful about constructor and destructor chaining, and about which name() is dispatched for each object.

Debugging

The following class is intended to be a minimal string wrapper backed by a heap-allocated char buffer. It contains 3 bugs. For each one:

Name the member function that contains the bug.
Explain in one or two sentences what goes wrong.
Write the corrected line or lines of code.

#include <cstring>
#include <cstddef>

class MyString {
    char*       data;
    std::size_t len;

public:
    MyString(const char* s) {
        len  = strlen(s);
        data = new char[len];
        strcpy(data, s);
    }

    MyString(const MyString& other) {
        len  = other.len;
        data = other.data;
    }

    MyString& operator=(const MyString& other) {
        if (this == &other) return *this;
        delete data;
        len  = other.len;
        data = new char[len + 1];
        strcpy(data, other.data);
        return *this;
    }

    ~MyString() { delete[] data; }

    const char* c_str() const { return data; }
    std::size_t size()  const { return len;  }
};

The following function is intended to return the k most frequently occurring words in a list, sorted from most to least frequent. It contains 3 bugs. For each one:

Identify the line or lines where the bug occurs.
Explain in one or two sentences why the result is incorrect.
Write the corrected line or lines of code.

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

std::vector<std::string> topKWords(const std::vector<std::string>& words, int k) {
    std::unordered_map<std::string, int> freq;
    for (const std::string& w : words) {
        freq[w] = 1;
    }

    std::vector<std::pair<int, std::string>> pairs;
    for (const auto& [word, count] : freq) {
        pairs.push_back({count, word});
    }

    std::sort(pairs.begin(), pairs.end());

    std::vector<std::string> result;
    for (int i = 0; i <= k && i < (int)pairs.size(); ++i) {
        result.push_back(pairs[i].second);
    }
    return result;
}

int main() {
    std::vector<std::string> words = {"a", "b", "a", "c", "b", "a"};
    for (const auto& w : topKWords(words, 2)) {
        std::cout << w << "\n";
    }
    // expected: "a" (3×) then "b" (2×)
    return 0;
}

Implementation

Given the following node definition:
struct Node { int val; Node* next; Node(int v, Node* n = nullptr) : val(v), next(n) {} };
Implement the following function:
Node* reverse(Node* head) // 1 -> 2 -> 3 -> 4 -> nullptr becomes 4 -> 3 -> 2 -> 1 -> nullptr // nullptr → nullptr // 1 -> nullptr → 1 -> nullptr
Reverses the singly linked list in-place and returns the new head. Do not allocate any new nodes.
Implement the following function template:
template <typename T> T secondLargest(const std::vector<T>& v) // secondLargest<int>({3, 1, 4, 1, 5, 9, 2, 6}) → 6 // secondLargest<int>({10, 20}) → 10 // secondLargest<double>({3.0, 1.5, 2.5}) → 2.5
Returns the second largest distinct value in v. You may assume v contains at least two distinct elements. No std::sort allowed.
Given the following function signature:
int firstUniqueChar(const std::string& s) // firstUniqueChar("leetcode") → 0 ('l' appears once) // firstUniqueChar("loveleetcode") → 2 ('v' appears once) // firstUniqueChar("aabb") → -1
Returns the index of the first character that appears exactly once, or -1 if no such character exists. Use an std::unordered_map. O(n) expected.
Given the following function signature:
bool isValid(const std::string& s) // isValid("()") → true // isValid("()[]{}") → true // isValid("(]") → false // isValid("([)]") → false // isValid("{[]}") → true // isValid("") → true
Returns true if the bracket sequence in s is valid (every opener is closed in the correct order). Only '(', ')', '[', ']', '{', '}' appear in s. Use a stack.

Command Palette

MTH 4300 Midterm 2 Practice Questions

Tracing

Debugging

Implementation