More Practice Problems (Post-Midterm)

void printSumsOf(int n) {
    /* Handle edge cases. */
    if (n < 0) error("Can't make less than nothing from more than nothing.");
    printSumsRec(n, {});
}

/* Print all ways to sum up to n, given that we've already broken off the numbers
 * given in soFar.
 */
void printSumsRec(int n, Vector<int> soFar) {
    /* Base case: Once n is zero, we need no more numbers. */
    if (n == 0) {
        printAsSum(soFar);
    } else {
        /* The next number can be anything between 1 and n, inclusive. */
        for (int i = 1; i <= n; i++) {
            printSumsRec(n - i, soFar + i);
        }
    }
}

/* Prints a Vector<int> nicely as a sum. */
void printAsSum(Vector<int>& sum) {
    /* The empty sum prints as zero. */
    if (sum.isEmpty()) {
        cout << 0 << endl;
    } else {
        /* Print out each term, with plus signs interspersed. */
        for (int i = 0; i < sum.size(); i++) {
            cout << sum[i];
            if (i + 1 != sum.size()) cout << " + ";
        }
        cout << endl;
    }
}

void listKOrderings(Set<string> choices, int k) {
    /* Quick edge case check: if we want more items than there are options, there
    * are no orderings we can use.
    */
    if (k < choices.size()) {
        listOrderingHelper(choices, k, {});
    }
}
void listOrderingHelper(Set<string> choices, int k, Vector<string> soFar) {
    /* Base case: If no more terms are needed, print what we have. */
    if (k == 0) {
        cout << soFar << endl;
    }
    /* Recursive case: What comes next? Try all options. */
    else {
        for (string choice: choices) {
            listOrderingHelper(choices - choice, k - 1, soFar + choice);
        }
    }
}

void printMultCompoundWords(Lexicon& dict) {
    for (string word : dict) {
        if (isMultCompoundWord(word, dict)) {
            cout << word << endl;
        }
    }
}

bool isMultCompoundWord(string word, Lexicon& dict) {
    /* In an unusual twist, our base case is folded into the recursive step. We
    * will try all possible splits into two pieces, and if one of them happens
    * to be a pair of words, we stop.
    */
 
    /* Try all ways of splitting things. */
    for (int i = 1; i < word.length(); i++) {
        /* Only split if the first part is a word. */
        if (dict.contains(word.substr(0, i))) {
            string remaining = word.substr(i);
            /* We're done if the remainder is either a word or a compound word. */
            if (dict.contains(remaining) || isMultCompoundWord(remaining, dict)) {
                return true;
            }
        }
    }
    /* Nothing works; give up. */
    return false;
}

/* Returns the reciprocal of this fraction. If the fraction is zero, this
 * operation is not defined, and the function calls error().
 */
Fraction reciprocal();

Fraction Fraction::reciprocal() {
    if (numerator() == 0) {
        error("I can't divide by zero. (Maybe you can, though?)");
    }

    return Fraction(denominator(), numerator());
}

/* Divides this fraction by the fraction given in the parameter. If that
 * fraction is zero, calls error().
 */
void divide(Fraction rhs);

void Fraction::divide(Fraction rhs) {
    multiply(rhs.reciprocal());
}

class BigNum {
public:
    BigNum(int value = 0); // Default to zero unless specified otherwise.
    ~BigNum();

    std::string toString() const; // Get a string representation
    void add(const BigNum& value);
private:
    int* digits; // Stored in reverse order
    int allocatedSize; // In # of digits
    int numDigits; // In # of digits.
    void reserve(int space); // Ensure we have space to hold numDigits digits
    int numDigitsOf(int value) const; // How many digits are in value?
};

BigNum::BigNum(int value) {
    /* Set up an initial array of elements. */
    digits = new int[kDefaultSize]; // Some reasonable default
    allocatedSize = kDefaultSize;

    /* Count how many digits are in our number. 0 is an edge case, so we'll make
    * this work by reducing the number of digits down to the last one.
    */
    numDigits = numDigitsOf(value);

    if(numDigits >= allocatedSize) error("Input too big!");

    /* Copy the number into the array, one digit at a time. */
    for (int i = 0; i < numDigits; i++) {
        digits[i] = value % 10;
        value /= 10;
    }
}

int BigNum::numDigitsOf(int value) const {
    /* Pro C++ tip: Since this function doesn't read or write any member
    * variables, this should either be a free function or a static member
    * function. We didn't discuss those sorts of concerns in CS106B, though.
    */
    int result = 1; // All numbers have at least one digit.

    /* We've already counted one digit. Now count the rest. */
    while (value >= 10) {
        result++;
        value /= 10;
    }
    return result;
}

BigNum::~BigNum() {
    delete[] digits;
}

string BigNum::toString() const {
    /* Because characters are stored in reverse order, we have to scan them
    * backwards to make our number.
    */
    string result;
    for (int i = numDigits - 1; i >= 0; i--) {
        result += to_string(digits[i]);
    }
    return result;
}

void BigNum::add(const BigNum& value) {
    /* First, ensure we have space to hold the result. Adding two numbers produces
    * a result whose size is at most one digit bigger than either input number.
    */
    int digitsToVisit = max(numDigits, value.numDigits);
    reserve(1 + digitsToVisit);

    /* Use the grade school algorithm to add the numbers. */
    int carry = 0;
    for (int i = 0; i < digitsToVisit; i++) {

        int sum;
        if (i < numDigits && i < value.numDigits) sum = digits[i] + value.digits[i] + carry;
        else if (i < numDigits) sum = digits[i] + carry;
        else sum = value.digits[i] + carry;

        /* Write the one's place. */
        digits[i] = sum % 10;
        /* Store the carry. */
        carry = sum / 10;
    }

    /* We need at least as many digits as before, plus one if there is a final
    * carry.
    */
    numDigits = digitsToVisit;
    if (carry != 0) {
        numDigits ++;
    }
    if (carry == 1) digits[digitsToVisit] = 1;
}

/* Reserving space uses the regular "double in size" trick. */
void BigNum::reserve(int space) {
    /* If we have the space, then we don't need to do anything. */
    if (space <= allocatedSize) return;

    /* Double and copy. We deliberately don't just grow to the size requested,
    * since that may not be efficient.
    */
    allocatedSize *= 2;
    int* newDigits = new int[allocatedSize];
    for (int i = 0; i < numDigits; i++) {
        newDigits[i] = digits[i];
    }
    delete[] digits;
    digits = newDigits;
}

#pragma once

class RingBufferQueue {
public:
	// Same as before!
private:
	// Same as before! Except with the following new variable:
    // NEW
    void grow();        // Resize if we need more space  
};

// Same as before! Except with the following new method:

// NEW
void RingBufferQueue::grow() {
    /* Get twice as much space as we used to have. */
    int* newElems = new int[allocatedSize * 2];
    
    /* Copy the elements over. Start at the position given by the head, and
     * use modular arithmetic to walk forward, wrapping around if necessary.
     */
    for (int i = 0; i < size(); i++) {
        newElems[i] = elems[(head + i) % allocatedSize];
    }
    
    /* Replace the old array. */
    delete[] elems;
    elems = newElems;
    
    /* Our copy operation pushed everything to the front of the ring buffer
     * array. Update the head to look there as well.
     */
    head = 0;
    
    /* Remember that we just increased our size. */
    allocatedSize *= 2;
}

RingBufferQueue.h

#pragma once

#include <iostream>
using namespace std;
class RingBufferQueue {
public:
    RingBufferQueue();
    ~RingBufferQueue();
    bool isEmpty() const;
    bool isFull() const;
    int size() const;
    void enqueue(int elem);
    int dequeue();
    int peek() const;
private:
    int* _elements;
    int _capacity;
    int _size;
    int _head;
    friend ostream& operator <<(ostream& out, const RingBufferQueue& queue);
    void enlarge();
};

RingBufferQueue.cpp

#include "RingBufferQueue.h"

static int kDefaultCapacity = 5;
RingBufferQueue::RingBufferQueue() {
    _capacity = kDefaultCapacity;
    _elements = new int[_capacity];
    _head = 0;
    _size = 0;
}
RingBufferQueue::~RingBufferQueue() {
    delete[] _elements;
}
void RingBufferQueue::enqueue(int elem) {
    if (isFull()) {
        enlarge();
    }
    int tail = (_head + _size) % _capacity;
    _elements[tail] = elem;
    _size++;
}
int RingBufferQueue::dequeue() {
    int front = peek();
    _head = (_head + 1) % _capacity;
    _size--;
    return front;
}
int RingBufferQueue::peek() const {
    if (isEmpty()) {
        error("Can't peek at an empty queue!");
    }
    return _elements[_head];
}
bool RingBufferQueue::isEmpty() const {
    return _size == 0;
}
bool RingBufferQueue::isFull() const {
    return _size == _capacity;
}
int RingBufferQueue::size() const {
    return _size;
}
void RingBufferQueue::enlarge() {
    int *larger = new int[_capacity * 2];
    for (int i = 0; i < _size; i++) {
        larger[i] = _elements[(_head + i) % _capacity];
    }
    delete[] _elements;
    _elements = larger;
    _capacity *= 2;
    _head = 0;
}
ostream& operator <<(ostream& out, const RingBufferQueue& queue) {
    out << "{";
    if (!queue.isEmpty()) {
        // We can access the inner ‘_elements’ member variables because
        // this operator is declared as a friend of the RingBufferQueue class
        out << queue._elements[queue._head];
        for (int i = 1; i < queue.size(); i++) {
            int index = (queue._head + i) % queue._capacity;
            out << ", " << queue._elements[index];
        }
    }
    out << "}";
    return out;
}

void insert(StringNode*& front, int index, string value) {
    if (index == 0) {
        front = new StringNode(value, front);
    } else {
        StringNode* temp = front;
        for (int i = 0; i < index - 1; i++) {
            temp = temp->next;
        }
        temp->next = new StringNode(value, temp->next);
    }
}

bool valueWithinThreshold (double value, double target, double threshold) {
    return value >= target - threshold && value <= target + threshold;
}

void removeAllThreshold(DoubleNode*& front, double value, double threshold) {
    if (front == nullptr)
        return;

    DoubleNode* current = front->next;
    DoubleNode* prev = front;
    while (current != nullptr) {
        DoubleNode* next = current->next;
        if (valueWithinThreshold(current->data, value, threshold)) {
            delete current;
            prev->next = next;
        } else {
            prev = current; 
        }
        current = next;
    }

    // edge case for when front's value is also within threshold.
    if (valueWithinThreshold(front->data, value, threshold)) {
        DoubleNode* next = front->next;
        delete front;
        front = next;
    }
}

void doubleList(Node*& front) {
    if (front != nullptr) {
        Node *half2 = new Node(front->data, nullptr);
        Node *back = half2;
        Node *current = front;
        while (current->next != nullptr) {
            current = current->next;
            back->next = new Node(current->data, nullptr);
            back = back->next;
        }
        current->next = half2;
    }
}

Node *temp = list->next->next;
temp->next = list->next;
list->next->next = list;
list->next->next->next = nullptr;
list = temp;

list->next->next->next = list;
list = list->next->next;
Node *list2 = list->next->next;
list->next->next = nullptr;

/* Iterative version */
int sumOfElementsIn(Node* list) {
    int result = 0;
    for (Node* curr = list; curr != nullptr; curr = curr->next) {
        result += curr->data;
    }
    return result;
}

/* Recursive version. */
int sumOfElementsIn(Node* list) {
    /* The sum of the elements in an empty list is zero. */
    if (list == nullptr) return 0;

    /* The sum of the elements in a nonempty list is the sum of the elements in
    * the first node plus the sum of the remaining elements.
    */
    return list->data + sumOfElementsIn(list->next);
}

/* Iterative version */
Node* lastElementOf(Node* list) {
    if (list == nullptr) error("Empty lists have no last element.");
    
    /* Loop forward until the current node next pointer is null. That’s the
    * point where the list ends.
    */
    
    Node* result = list;
    while (result->next != nullptr) {
        result = result->next;
    }
    return result;
}

/* Recursive version. */
Node* lastElementOf(Node* list) {
    /* Base Case 1: The empty list has no last element. */
    if (list == nullptr) error("Nothing can come from nothing.");
    
    /* Base Case 2: The only element of a one-element list is the last element. */
    
    if (list->next == nullptr) return list;
    
    /* Recursive Case: There’s at least two nodes in this list. The last element
    * of the overall list is the last element of the list you get when you drop
    * off the first element.
    */
    return lastElementOf(list->next);
}

int listLength(ListNode* list) {
    int count = 0;
    /* Cute little for loop trick to visit everything in a linked list. This loop
    * is great if you are not making any changes to the list, but if the list is
    * either being rewired or being deallocated, this loop won't work.
    */
    for (ListNode* curr = list; curr != nullptr; curr = curr->next) {
        count++;
    }
    return count;
}

ListNode* kthToLastSimple(ListNode* list, int k) {
    /* Find length of the list */
    int len = listLength(list);
    
    /* If the list is too small, just return nullptr. */
    if (len < k) return nullptr;
 
    /* Move len - k + 1 steps into the list */
    ListNode* curr = list;
    for (int i = 0; i < len - k; i++) {
        curr = curr->next;
    }
    return curr;
}

ListNode* kthToLast(ListNode* list, int k) {
    /* Set up two pointers, one leader and one follower. */
    ListNode* leader = list;
    ListNode* follower = list;

    for (int i = 0; i < k; i++) {
        if (leader == nullptr) return nullptr;
        leader = leader->next;
    }

    /* Keep walking the leader and follower forward. As soon as the leader walks
    * off the follower is in the right spot.
    */
    while (true) {
        if (leader == nullptr) return follower;
        leader = leader->next;
        follower = follower->next;
    }
}

void listInsertionSort(ListNode*& list) { // Question to ponder: why by reference?
    ListNode* sortedList = nullptr;
    ListNode* curr = list;
    while (curr != nullptr) {
        /* Need to store the pointer to the next cell in the list, since after
        * we do the insert operation we'll lose track of where the next cell
        * is.
        */
        ListNode* next = curr->next;
        sortedInsert(curr, sortedList);
        curr = next;
    }
    list = sortedList;
}
/* Adds the given node into a sorted, singly-linked list. */
void sortedInsert(ListNode* toIns, ListNode*& list) {
    /* See if we go at the beginning. */
    if (list == nullptr || toIns->value < list->value) {
        toIns->next = list;
        list = toIns;
    } else {
        /* Find the spot right before where we go, since that's the pointer we
        * need to rewire.
        */
        ListNode* curr = list;
        ListNode* prev = nullptr;
        while (curr != nullptr && curr->value < toIns->value) {
            prev = curr;
            curr = curr->next;
        }
        /* Splice us in. */
        toIns->next = curr;
        prev->next = toIns;
    }
}

int height(TreeNode * node) {
    if (node == nullptr) {
        return -1;
    } else {
        return 1 + max(height(node->left), height(node->right));
    }
}

TreeNode* biggestNodeIn(TreeNode* root) {
    if (root == nullptr) error("Nothing to see here, folks.");
    /* Base case: If the root of the tree has no right child, then the root node
    * holds the largest value because everything else is smaller than it.
    */
    if (root->right == nullptr) return root;
    
    /* Otherwise, the largest value in the tree is bigger than the root, so it’s
    * in the right subtree.
    */
    return biggestNodeIn(root->right);
}

TreeNode* biggestNodeIn(TreeNode* root) {
    if (root == nullptr) {
        error("Nothing to see here, folks.");
    }
    while (root->right != nullptr) {
        root = root->right;
    }
    return root;
}

TreeNode* secondBiggestNodeIn(TreeNode* root) {
    if (root == nullptr) {
        error("Nothing to see here, folks.");
    }

    TreeNode* prev = nullptr;
    TreeNode* curr = root;
    while (curr->right != nullptr) {
        prev = curr;
        curr = curr->right;
    }

    if (curr->left == nullptr) {
        return prev;
    } else {
        return biggestNodeIn(curr->left);
    }
}

bool isBSTRec(TreeNode* root, TreeNode* lowerBound, TreeNode* upperBound) {
    /* Base case: The empty tree is always valid.*/
    if (root == nullptr) return true;
 
    /* Otherwise, make sure this value is in the proper range. */
    if (lowerBound != nullptr && root->data <= lowerBound->data) return false;
    if (upperBound != nullptr && root->data >= upperBound->data) return false;
 
    /* Okay! We're in range. So now we just need to confirm that the left and
    * right subtrees are good as well. Notice how the range changes based on the
    * introduction of this node.
    */
    return isBSTRec(root->left, lowerBound, root)
           && isBSTRec(root->right, root, upperBound);
}

bool isBST(TreeNode* root) {
    return isBSTRec(root, nullptr, nullptr);
}

bool areEqual(TreeNode* one, TreeNode* two) {
    /* Base Case: If either tree is empty, they had both better be empty. */
    if (one == nullptr || two == nullptr) {
        return one == two; // At least one is null
    }
 
    /* We now know both trees are nonempty. Confirm the root values match and
    * that the subtrees agree.
    */
    return one->data == two->data 
           && areEqual(one->left, two->left) 
           && areEqual(one->right, two->right);
}

int countLeftNodes(TreeNode *node) {
    if (node == nullptr) {
        return 0;
    } else if (node->left == nullptr) {
        return countLeftNodes(node->right);
    } else {
        return 1 + countLeftNodes(node->left) + countLeftNodes(node->right);
    }
}

bool isBalanced(TreeNode *node) {
    /* From the problem statement, an empty tree is balanced */
    if (node == nullptr) {
        return true;
    } else {
    /* From the problem statement, "a tree is balanced if its left and right subtrees are balanced trees whose heights differ by at most 1". The key thing to note is that this is taken right from the problem statement! (even if you didn't understand the question well, we tell you the formula to find whether a tree is balanced or not!) */
        return isBalanced(node->left) && isBalanced(node->right) && 
                abs(height(node->left) - height(node->right)) <= 1;
    }
}

void removeLeaves(TreeNode*& node) { 
    if (node != nullptr) { 
        if (node->left == nullptr && node->right == nullptr) { 
            delete node; 
            node = nullptr; // you can do this since node is passed by reference! 
        } else { 
            removeLeaves(node->left); 
            removeLeaves(node->right); 
        } 
    } 
}