Practice Final 6 Solutions

void printAccordionWords(string soFar, int consecDistMax, int totalDistMax,
                         Lexicon& lexy) {
    // If we have used more than the allowed total width, this is a fail.
    if (totalDistMax < 0) {
        return;
    }

    // This variable is not necessary. Possibly a controversial choice.
    // I did this just to save myself some typing and enhance the readability
    // of some of the lines below.
    int len = soFar.length();

    // Check whether distance between two most recent characters exceeds limit
    // (only if we have at least two characters in the string so far).
    if (len >= 2) {
        if (abs(soFar[len - 1] - soFar[len - 2]) > consecDistMax) {
            return;
        }
    }

    // If the current string is not a prefix to anything in the lexicon, there's
    // no reason to keep going down this branch. Prune, backtrack, and move on.
    if (!lexy.containsPrefix(soFar)) {
        return;
    }

    // Aha! We found one. Be careful not to return, though. This might be the
    // prefix to other solutions.
    if (lexy.contains(soFar)) {
        cout << soFar << endl;
    }

    for (char ch = 'a'; ch <= 'z'; ch++) {
        // If there are no previous characters, then this new one has no
        // impact on the totalDistMax; the distance from the previous char to
        // the new one we're throwing down is effectively zero.
        int thisDist = 0;

        // We only need 1 or more character here (contrast with the 2 or more
        // needed above) because we are just looking for the difference between
        // the single previous character and the one we're about to add to the
        // string.
        if (len >= 1) {
            thisDist = abs(ch - soFar[len-1]);
        }

        printAccordionWords(soFar + ch, consecDistMax, totalDistMax - thisDist, lexy);
    }
}

// Prints all English words (made up of lowercase alpha chars only) wherein
// every pair of consecutive characters is no more than consecDistMax letters
// apart in the alphabet and the sum of all distances no more than totalDistMax.
void printAccordionWords(int consecDistMax, int totalDistMax, Lexicon& lexy) {
    printAccordionWords("", consecDistMax, totalDistMax, lexy);
}

SearchSack::SearchSack() {
    // The main goal here is to initialize any private member variables we're
    // using to keep track of the current mode / ratio of insertion operations
    // to search operations. There are many other possibilities for the kinds
    // of variables we could use here.

    // Note that _addCount is not strictly necessary. Since we don't allow
    // deletions, we could simply use _v.size() in place of _addCount. That
    // is not an ideal approach, though, because if we decided to expand the
    // functionality of the data structure to allow for deletions some day,
    // _v.size() would suddenly become an unreliable proxy for _addCount.
    // Keeping track of _addCount separately would future-proof our code to some
    // degree.

    _searchCount = 0;
    _addCount = 0;
}

void SearchSack::add(int elt) {
    // Function description indicates we should increment this before checking
    // whether we're in insertion-heavy or search-heavy mode.
    _addCount++;

    // Problem specification says we're only in search-heavy mode if number
    // of searches exceeds insertions. If they're equal, we're in insertion-
    // heavy mode. (This is also noted explicitly toward the top of the first
    // page of the problem.)
    if (_addCount >= _searchCount) {
        unsortedAdd(elt);
    }
    else {
        sortedAdd(elt);
    }
}

bool SearchSack::contains(int elt) {
    // Function description indicates we should increment this before checking
    // whether we're in insertion-heavy or search-heavy mode.
    _searchCount++;

    // Check whether we JUST surpassed the addCount. If so, that would indicate
    // we just switched from insertion-heavy to search-heavy mode. There are
    // other ways to achieve this, such as keeping track of the current mode
    // in a separate variable.
    if (_searchCount == _addCount + 1) {
        _v.sort();
    }

    // Strictly greater-than. See note about this in add() function above.
    if (_searchCount > _addCount) {
        return binarySearch(elt) != -1;
    }
    else {
        return linearSearch(elt) != -1;
    }
}

void SearchSack::sortedAdd(int elt) {
    _v.insert(getInsertionIndex(elt), elt);
}

void SearchSack::unsortedAdd(int elt) {
    // Note that _v.insert(_v.size(), elt) would also work here.
    _v.add(elt);
}

// If you wrote your own insertion function rather than relying on the one
// built into the Vector class, it might look something like this:
void SearchSack::sortedAdd(int elt) {
    int index = getInsertionIndex(elt);

    if (_v.size() == 0) {
        _v.add(elt);
        return;
    }

    // The following line is unsafe if we don't have at least one element in
    // the vector already -- which isn't guaranteed while we're in search mode,
    // because someone could call contains() before even inserting an element.
    // Hence the special case above that returns if the vector was empty.
    _v.add(_v[_v.size() - 1]);

    // We don't have to start at i = _v.size() - 1 below, since we just copied
    // that element over into that position. If we placed some other sort of
    // placeholder value at the end of the vector, however, we would indeed
    // need to start at i = _v.size() - 1 here.
    for (int i = _v.size() - 2; i > index; i++) {
        _v[i] = _v[i-1];
    }

    _v[index] = elt;
}

void forestFire(Node *root) {
    if (root == nullptr) {
        return;
    }

    forestFire(root->left);
    forestFire(root->right);

    // This needs to come after the recursive calls.
    delete root;
}

// Must be pass by reference. Otherwise, cannot nullify the calling function's
// pointer to this root if it gets deleted.
void propagate(Node*& root, int product) {
    if (root == nullptr) {
        return;
    }

    root->data *= product;

    if (root->data == 0) {
        // If this node's new value is 0, then all its descendent nodes will
        // have a value of 0 as well, so we can delete this whole subtree.
        // Alternatively, we could make recurisve calls to the propagate()
        // function and delete the root after we return from those calls.
        forestFire(root);

        // Alternatively, make forestFire() pass-by-reference, and set
        // root = nullptr in that function after deleting root.
        root = nullptr;

        return;
    }

    // Don't attempt to peek ahead and multiply here. That would be
    // unnecessarily complex (have to check for nullptrs) and violate
    // the spirit or the meaning of these recursive calls.
    propagate(root->left, root->data);
    propagate(root->right, root->data);
}

void propagate(Node*& root) {
    propagate(root, 1);
}

void propagate(Node*& root, int product) {
    if (root == nullptr) {
        return;
    }

    // Propagate forward and only check for 0 as we back out. This eliminates
    // the need for a forestFire() function.
    propagate(root->left, product * root->data);
    propagate(root->right, product * root->data);

    root->data *= product;

    if (root->data == 0) {
        delete root;
        root = nullptr;
    }
}

void propagate(Node*& root) {
    propagate(root, 1);
}

// The key insight here is that we can just throw node pointers into a HashSet.
// For each node we encounter, we can check whether or not we have seen it
// before in O(1) time (average/expected runtime).
bool hasCycle(Node *head) {
    HashSet<Node *> allNodes;

    for (Node *current = head; current != nullptr; current = current->next) {
        // Check whether we have seen this node pointer before or not. If so,
        // we have a cycle.
        if (allNodes.contains(current)) {
            return true;
        }

        // Keep track of all the node pointers we've seen.
        allNodes.add(current);
    }

    // If we get here, we must have hit a nullptr, so there was no cycle.
    return false;
}