Final Exam Review Session Problems

Set<Node*> trimAbove(Node* root, int level) {
    /* Base Case: If the root is null, there's nothing to do. */
    if (root == nullptr) return { };
    
    /* Base Case: If level is 0, then the root node is the only node at
     * level 0 in the tree.
     */
    if (level == 0) return { root };
    
    /* Recursive Case: Delete this node, and possibly trim below us too.
     * To ensure we don't lose track of the children, store pointers to
     * the children before deleting the root.
     */
    Node* left  = root->left;
    Node* right = root->right;
    delete root;
    
    return trimAbove(left, level - 1) + trimAbove(right, level - 1);
}

/* Trims all nodes above targetLevel. currLevel denotes our current level in
 * the tree.
 */
Set<Node*> trimRec(Node* root, int targetLevel, int currLevel) {
    /* Base Case: If the root is null, there's nothing to do. */
    if (root == nullptr) return { };
    
    /* Base Case: If we hit the target level, then hand back the node. */
    if (targetLevel == currLevel) return { root };
    
    /* Recursive Case: Recursively process the left and right subtree. Having
     * done so, clean up the current node.
     */
    auto left  = trimRec(node->left,  targetLevel, currLevel + 1);
    auto right = trimRec(node->right, targetLevel, currLevel + 1);
    
    delete root;
    return left + right;
}

Set<Node*> trimAbove(Node* root, int level) {
    return trimRec(root, level, 0);
}

Set<Node*> trimRec(const Set<Node*>& currLayer, int layer) {
    /* Base Case: Hit the bottom layer? Return what we have. */
    if (layer == 0) {
        return currLayer;
    }
    
    /* Recursive Case: This layer needs to be deleted, and we need to form
     * the layer below us.
     */
    Set<Node*> nextLayer;
    for (Node* node: currLayer) {
        /* Add the children, then clean up this node. */
        if (node->left  != nullptr) nextLayer += node->left;
        if (node->right != nullptr) nextLayer += node->right;
        delete node;
    }
    
    /* Recursively clean up below this point. */
    return trimRec(nextLayer, layer - 1);
}

Set<Node*> trimAbove(Node* root, int layer) {
    /* Edge case: If the root is null, there's nothing to do. */
    if (root == nullptr) return { };
    
    /* Otherwise, recursively wipe the top layer and the ones beneath
     * it.
     */
    return trimRec({ root });
}

/* Can we chain the remaining dominoes together, given that the last domino's
 * exposed number of pips is 'last'.
 */
bool canChainRec(Vector<Domino>& dominoes, int last) {
    /* Base Case: No dominoes left? Then we're done! */
    if (dominoes.isEmpty()) {
        return true;
    }

    /* Otherwise, some domino comes next. Try all options. */
    for (int i = 0; i < dominoes.size(); i++) {
        Domino d = dominoes[i];

        /* If the number of pips on the front of the domino matches the number
         * of pips on the end of the previous domino, we can extend the chain,
         * and the number of pips on the side we didn't use becomes the new
         * number of pips to match.
         */
        auto front = dominoes.subList(0, i);
        auto prev = dominoes.subList(i + 1);
        auto combined = front + prev;

        if ((d.first == last  && canChainRec(combined, d.second)) ||
            (d.second == last && canChainRec(combined, d.first))) {
            return true;
        }
    }

    /* We tried everything and nothing worked. Give up. */
    return false;
}

/* Checks if the dominoes can be chained together. */
bool canChainDominoes(Vector<Domino>& dominoes) {
    /* If there are no dominoes, then we can chain all zero of them
     * together into a length-zero chain.
     */
    if (dominoes.isEmpty()) {
        return true;
    }

    /* Otherwise, some domino comes first. Try each domino, in both
     * orientations, to see whether we can form a chain.
     */
    for (int i = 0; i < dominoes.size(); i++) {
        Domino d = dominoes[i];

        /* If the number of pips on the front of the domino matches the number
         * of pips on the end of the previous domino, we can extend the chain,
         * and the number of pips on the side we didn't use becomes the new
         * number of pips to match.
         */
        auto front = dominoes.subList(0, i);
        auto prev = dominoes.subList(i + 1);
        auto combined = front + prev;

        if (canChainRec(combined, d.second) ||
            canChainRec(combined, d.first)) {
            return true;
        }
    }
    return false;
}

class BackupVector {
public:
    BackupVector();
    ~BackupVector();

    /* Appends a new value to the vector. */
    void append(int toAdd);

    /* Returns the value at the given index. Calls error() if the index is
     * out of bounds.
     */
    int get(int index) const;

    /* Size of the vector, and whether it's empty. */
    int  size() const;
    bool isEmpty() const;

private:
    /* The two arrays. */
    int* small;
    int* large;
    
    /* The rest is up to you! */
    int logicalSize;   // Number of stored elements
    int allocatedSize; // Of the large array

    /* Cleans up the previous small array and makes a new large array. */
    void grow();
};

#include "BackupVector.h"
using namespace std;

/* Initial size of the large array. (The small array is not allocated until
 * the large array is full.)
 */
const int kInitialSize = 2;

BackupVector::BackupVector() {
    /* We begin with just a large array and no small array. */
    small = nullptr;
    large = new int[kInitialSize];
    
    logicalSize = 0;              // Logically, no elements are stored
    allocatedSize = kInitialSize; // Size of the large array
}

/* Need to clean up both the large and small array. */
BackupVector::~BackupVector() {
    delete[] large;
    
    /* There might not be a small array. However, C++ guarantees that calling
     * delete[] on a null pointer has no effect.
     */
    delete[] small;
}

void BackupVector::append(int toAdd) {
    /* Get more space if we need it. */
    if (logicalSize == allocatedSize) {
        grow();
    }

    /* Write the element to the large array. */
    large[logicalSize] = toAdd;
    
    /* Now, move an element from the small array to the large array. */
    if (small != nullptr) {
        large[allocatedSize - logicalSize - 1] = small[allocatedSize - logicalSize - 1];
    }
    logicalSize++;
}

int BackupVector::get(int index) const {
    /* Bounds-checking. */
    if (index < 0 || index >= size()) error("Out of range.");

    /* If there's no small array, we definitely look in the large array. */
    if (small == nullptr) return large[index];
    
    /* Otherwise, where to look depends on whether we're in the first or
     * second half of the array.
     *
     * In case you haven't seen this before, the syntax
     *
     *    test? ifTrue : ifFalse
     *
     * means "see if test is true. If it is, evaluate to ifTrue. If it's not,
     * evaluate to ifFalse."
     */
    return (index < allocatedSize / 2? small : large)[index];
}

int BackupVector::size() const {
    return logicalSize;
}

bool BackupVector::isEmpty() const {
    return size() == 0;
}

void BackupVector::grow() {
    /* Clean up the previous small array. If there isn't one, then small is
     * nullptr, and delete[]-ing nullptr has no effect.
     */
    delete[] small;
    
    /* The small array is now what used to be the large array. */
    small = large;

    /* Get some more space to work with. */
    allocatedSize *= 2;
    large = new int[allocatedSize];
}

class Deque {
public:
    Deque();
    ~Deque();

    /* Seems like all containers have the next two functions. :-) */
    bool isEmpty() const;
    int  size() const;

    /* Adds a value to the front or the back of the deque. */
    void pushFront(int value);
    void pushBack(int value);

    /* Looks at, but does not remove, the first/last element of the deque. */
    int peekFront() const;
    int peekBack() const;

    /* Returns and removes the first or last element of the deque. */
    int popFront();
    int popBack();

private:
    struct Cell {
        int value;
        Cell* next;
        Cell* prev;
    };
    Cell* _head;
    Cell* _tail;
    int  _ numElems; // Cache for efficiency; makes size() run in time O(1).

    /* Creates a new cell initialized to a given value, but whose next and prev
     * pointers are uninitialized. This cell is intended to be used inside the
     * linked list, and therefore the size field is adjusted appropriately.
     */
    Cell* makeCell(int value);

    /* Destroys the given cell, which is presumed to be in the linked list. */
    void destroy(Cell* toRemove);
};

#include "error.h" // Because bad things happen.

Deque::Deque() {
    /* Set up the empty dummied, doubly-linked list. */
    _head = new Cell;
    _tail = new Cell;
    _head->next = _tail;
    _tail->prev = _head;
    _head->prev = _tail->next = nullptr;

    _numElems = 0;
}

Deque::~Deque() {
    /* Delete all cells in the list, including the head and tail. */
    while (_head != nullptr) {
        Cell* next = _head->next;
        delete _head;
        _head = next;
    }
}

/* Because we’ve cached the size, we don’t need to scan through the list when
 * we want to determine how many elements there are.
 */
int Deque::size() const {
    return _numElems;
}

/* Good programming exercise: suppose that we didn’t cache the number of elements
 * in the list and that size() had to scan over the entire list in time O(n). How
 * would you implement isEmpty() given that we have a head and tail pointer?
 */
bool Deque::isEmpty() const {
    return size() == 0;
}

/* Our helper function that makes a cell. We could have alternatively defined a
 * constructor on the Cell type (yes, you can do that!), but I chose to do things
 * this way to show off Yet Another Memorable Piece of C++ Syntax. Since the
 * Cell type is nested inside Deque, the return type of this function has to be
 * Deque::Cell*, indicating that Cell is defined inside of Deque.
 */
Deque::Cell* Deque::makeCell(int value) {
    Cell* result = new Cell;
    result->value = value;

    _numElems++;
    return result;
}

/* pushFront is essentially insertAfter with the head pointer. */
void Deque::pushFront(int value) {
    Cell* cell = makeCell(value);
    cell->prev = _head;
    cell->next = _head->next;
    cell->prev->next = cell;
    cell->next->prev = cell;
}

/* pushBack is essentially insertBefore with the tail pointer. */
void Deque::pushBack(int value) {
    Cell* cell = makeCell(value);
    cell->next = _tail;
    cell->prev = tail->prev;
    cell->prev->next = cell;
    cell->next->prev = cell;
}

/* To look at the front or back, we have to skip over the head or tail nodes,
 * since they’re dummies and don’t actually have any data in them.
 */
int Deque::peekFront() const {
    if (isEmpty()) error("This is why we can’t have nice things.");
    return _head->next->value;
}

int Deque::peekBack() const {
    if (isEmpty()) error("This is why we can’t have nice things.");
    return _tail->prev->value;
}

/* The destroy operation is essentially our remove function from earlier.
 * Notice that we do not need to use the full name Deque::Cell here because Cell
 * is an argument to a member function that’s part of the Deque type.
 */
void Deque::destroy(Cell* toRemove) {
    toRemove->next->prev = toRemove->prev;
    toRemove->prev->next = toRemove->next;

    /* At this point it’s spliced out of the list. */
    delete toRemove;
    _numElems--;
}

/* popFront and popBack are essentially just wrapped splice-outs. */
int Deque::popFront() {
    int result = peekFront();
    destroy(_head->next);
    return result;
}

int Deque::popBack() {
    int result = peekBack();
    destroy(_tail->prev);
    return result;
}

struct Range {
    Node* first;
    Node* last;
};

Range flatten(Node* root) {
    /* If the tree is empty, it's already flattened. */
    if (root == nullptr) return { nullptr, nullptr };

    /* Flatten the left and right subtrees. */
    Range left  = flatten(root->left);
    Range right = flatten(root->right);

    /* Glue things together. */
    root->left = left.last;
    if (left.last != nullptr) left.last->right = root;

    root->right = right.first;
    if (right.first != nullptr) right.first->left = root;

    /* Return the full range. */
    return {
        left.first == nullptr? root : left.first,
        right.last == nullptr? root : right.last
    };
}

Node* toList(Node* root) {
    return flatten(root).first;
}