Practice Final 2 Solutions

bool isUniqueSolution(Vector<GridLocation> circles) {
    Set<double> distances;
    for (int i = 0; i < circles.size(); i++) {
        for (int j = i + 1; j < circles.size(); j++) {
            double distance = euclidianDistance(circles[i], circles[j]);
            if (distances.contains(distance)) {
                return false;
            }
        distances.add(distance);
        }
    }
    return true;
}

void findUniqueDistancesHelper(const int n, Vector<GridLocation> &circles, Set<Vector<GridLocation>> &solutions, int row, int col) {
    // n is the number of circles we need to place on a grid of n x n locations
    // base cases
    if (!isUniqueSolution(circles)) {
        // not a solution
        return;
    }
    if (circles.size() == n) {
        solutions.add(circles);
        return;
    }
    if (row == n) {
        return;
    }
    int newRow = row;
    int newCol = col + 1;
    if (newCol == n) {
        newRow++;
        newCol = 0;
    }
    // recursive cases
    // don't add a new circle
    findUniqueDistancesHelper(n, circles, solutions, newRow, newCol);

    // add a new circle (choose)
    circles.add({row, col});
    findUniqueDistancesHelper(n, circles, solutions, newRow, newCol);

    // unchoose
    circles.remove(circles.size() - 1);
}

// Section.h

#pragma once
#include "vector.h"
using namespace std;

struct Student {
    string name;
    int suid;
    Vector<string> preferences;
};

class Section {

public:
    Section(int capacity, string time);
    ~Section();
    bool tryAddStudent(Student s);
    Student getStudent(int index);
    void swap(int index1, int index2);

private:
    Student *_students;
    int _capacity;
    int _numEnrolled;
    string _time;
    bool checkStudent(Student s);
    int thisSectionPreference(int index);
};

// Section.cpp

#include "Section.h"

Section::Section(int capacity, string time) {
    _students = new Student[capacity];
    _capacity = capacity;
    _numEnrolled = 0;
    _time = time;
}

Section::~Section() {
    delete[] _students;
}

bool Section::checkStudent(Student s) {
    // Condition 1: section is full 
    if (_numEnrolled == _capacity) return false;

    // Condition 2: this section's time is not in the top 3 of student preferences.
    for (int i = 0; i < s.preferences.size() && i < 3; i++) {
        if (s.preferences[i] == _time) {
            return true;
        }
    }

    return false;
}

int Section::thisSectionPreference(int index) {
    Vector<string> studentPref = _students[index].preferences;
    for (int i = 0; i < studentPref.size(); i++) {
        if (studentPref[i] == _time) {
            return i;
        }
    }
    return -1;
}

bool Section::tryAddStudent(Student s) {
    if (!checkStudent(s)) {
        return false;
    }

    _students[_numEnrolled] = s;

    // Student can be added. Now let's insert in sorted order by preference.
    for (int i = _numEnrolled; i > 0; i--) {
        // Check if student at index i's preference for this section 
        // is less than student at index i - 1's preference for this
        // section.
        if (thisSectionPreference(i) < thisSectionPreference(i - 1)) {
            swap(i, i - 1);
        }
    }

    _numEnrolled++;
    return true;
}

Student Section::getStudent(int index) {
    if (index < 0 || index >= _numEnrolled) {
        error("Out of bounds!");
    }

    return _students[index];
}

ListNode* addToEndOfList(ListNode* node, ListNode*& front, ListNode*& end) {
    if (front == nullptr) {
        front = node;
        end = node;
    } else {
        end->next = node;
        end = node;
    }
    ListNode* next = node->next;
    // make sure that the new node is in fact the end of our list node->next = nullptr;
    node->next = nullptr;
    return next;
}

ListNode* listDivisibleBy(ListNode*& front, int divisor) {
    ListNode* divisibleFront = nullptr;
    ListNode* divisibleEnd = nullptr;
    ListNode* indivisibleFront = nullptr;
    ListNode* indivisibleEnd = nullptr;
    ListNode* current = front;
    while (current != nullptr) {
        if (current->data % divisor == 0) {
            current = addToEndOfList(current, divisibleFront, divisibleEnd);
        } else {
            current = addToEndOfList(current, indivisibleFront, indivisibleEnd);
        }
    }
    front = indivisibleFront;
    return divisibleFront;
}

int diffMaxMinBst(TreeNode *root) {
    // Solution should be O(log n)
    // assumes at least one node in tree
    int min, max;
    // find min
    TreeNode *temp = root;
    while (temp->left != nullptr) {
        temp = temp->left;
    }
    min = temp->data;

    // find max
    temp = root;
    while (temp->right != nullptr) {
        temp = temp->right;
    }
    max = temp->data;

    return max - min;
}

void diffMaxMinNonBstHelper(TreeNode *root, int &min, int &max) {
    // base case
    if (root != nullptr) {
        // pre-order traversal
        if (root->data < min) {
            min = root->data;
        }
        if (root->data > max) {
            max = root->data;
        }
        diffMaxMinNonBstHelper(root->left, min, max);
        diffMaxMinNonBstHelper(root->right, min, max);
    }
}

int diffMaxMinNonBst(TreeNode *root) {
    // Solution should be O(n)
    // assumes at least one node in tree
    int min = root->data;
    int max = root->data;
    diffMaxMinNonBstHelper(root, min, max);
    return max - min;
}

TreeNode *balancedBstFromSortedVec(Vector sortedVec) {
    int vecSize = sortedVec.size();
    // base cases
    if (vecSize == 0) {
        return nullptr;
    }
    return new TreeNode(sortedVec[vecSize / 2], balancedBstFromSortedVec(sortedVec.subList(0, vecSize / 2)), balancedBstFromSortedVec(sortedVec.subList(vecSize / 2 + 1)));
}