Final 3 Practice Solutions

bool canPair(Vector<string> students, int maxOk) {
    if (maxOk < 0) {
        return false;
    }
    if (students.isEmpty()) {
        return true;
    }

    for (int i = 1; i < students.size(); i++) {
            // choose: match student[0] with student[i]
            // if score returns 0, usedOk is "true" which is int value 1
        int usedOk = (score(students[0], students[i]) == 0);
            // copy of vector without pair just matched
        Vector<string> rest = students.subList(1, i - 1) + students.subList(i + 1);
        if (canPair(rest, maxOk - usedOk)) {
            return true;
        }
    }
    return false;
}

private:
    string *_recents;
    int _capacity;
    int _totalCalls;
CallHistory::CallHistory(int capacity) {
    _capacity   = capacity;
    _recents    = new string[_capacity];
    _totalCalls = 0; 
}

CallHistory::~CallHistory() {
    delete[] _recents;
}

void CallHistory::add(string caller) {
    _recents[_totalCalls % _capacity] = caller;
    _totalCalls++;
}

string CallHistory::getRecent(int n) {
    // Invalid n would be negative, greater than allowed capacity, 
    // or within unitialized range (i.e. only 3 calls in history
    // with capacity 5, try to access 4)
    if (n < 0 || n >= _capacity || n >= _totalCalls) {
        error("Requested recent is out of range!");
    }
    return _recents[(_totalCalls - 1 - n) % _capacity];
}

int CallHistory::getTotalCalls() {
    return _totalCalls;
}

void transform(ListNode*& front) {
    ListNode *prev = nullptr;
    ListNode *cur = front;

    while (cur != nullptr) {
        if (cur->data < front->data) { // if move cur
            prev->next = cur->next;    // splice out 
            cur->next = front;         // push on front
            front = cur;
            cur = prev->next;          // advance cur, NOT prev
        } else {             // else not move cur
            prev = cur;      // advance BOTH cur and prev
            cur = cur->next;
        }
    }
}

void tighten(Node*& t) {
    if (t != nullptr) {
        tighten(t->left);
        tighten(t->right);

        Node *onlyChild = nullptr;
        if (t->left != nullptr && t->right == nullptr) {
            onlyChild = t->left;
        } else if (t->right != nullptr && t->left == nullptr) {
            onlyChild =  t->right;
        }
        if (onlyChild != nullptr) {  // this is improper node
            delete t;     // deallocate and replace with child
            t = onlyChild;
        }
    }
}