Practice Final 2 Solutions

bool canSpell(string word, Vector<string>& cubes) {
    if (word.empty()) {
        return true;
    }
    for (int i = 0; i < cubes.size(); i++) {
        string cube = cubes[i];
        if (cube.find(word[0]) != string::npos) {
            cubes.remove(i);
            if (canSpell(word.substr(1), cubes)) {
                return true;
            }
            cubes.insert(i, cube);
        }
    }
    return false;
}

// private member variables in .h
bool* _range;
int _min, _max, _count;

// member function implementation in .cpp
RangeSet::RangeSet(int minValue, int maxValue) {
    if (minValue > maxValue) error("Invalid range!");
    _range = new bool[maxValue - minValue + 1](); // init elements to false
    _min = minValue;
    _max = maxValue;
    _count = 0;
}

RangeSet::~RangeSet() {
    delete[] _range;
}

bool RangeSet::add(int value) {
    int index = getIndex(value);
    if (index == -1 || _range[index]) {
        return false;
    }
    _range[index] = true;
    _count++;
    return true;
}

int RangeSet::getIndex(int value) const {
    if (value < _min || value > _max) {
        return -1;
    }
    return value - _min;
}

int RangeSet::count() const {
    return _count;
}

void separate(ListNode* front, PriorityQueue<ListNode*>& runs) {
    while (front != nullptr) {
        ListNode* rest = splitRun(front);
        runs.enqueue(front, front->value);  // surprisingly, can even enqueue before split
        front = rest;
    }
}

ListNode *kWayMerge(PriorityQueue<ListNode*>& runs) {
    ListNode *output = nullptr, *outputTail = nullptr;

    while (!runs.isEmpty()) {
        ListNode* cur = runs.dequeue(); // cur is smallest of remaining runs
        if (output == nullptr) {
            output = cur;               // cur is first node to go of output
        } else {
            outputTail->next = cur;     // append cur to existing output
        }
        outputTail = cur;               // cur is now tail of output
        ListNode* remainder = cur->next;
        if (remainder != nullptr) {     // re-enqueue remainder if any
            runs.enqueue(remainder, remainder->value);
        }
    }
    return output;
}

void dismantle(BSTNode* t, Vector<int>& v) {
    if (t != nullptr) {
        dismantle(t->left, v);
        v.add(t->value);    // in-order add
        dismantle(t->right, v);
        delete t;           // post-order delete
    }
}

BSTNode *rebuild(Vector<int>& v) {
    return rebuildHelper(v, 0, v.size() - 1);
}

// start and stop indexes are _inclusive_ in this solution
BSTNode *rebuildHelper(Vector<int>& v, int start, int stop) {
    if (start > stop) return nullptr;
    int mid = (start + stop)/2;
    BSTNode* t = new BSTNode;
    t->value = v[mid];
    t->left = rebuildHelper(v, start, mid - 1);
    t->right = rebuildHelper(v, mid + 1, stop);
    return t;
}