Recursive problems for interviews

interview_recursive_warmups.cpp

/*  Warmup Questions */

/*  Warmup 1: array Length recursive
    Write a function that takes in the start of the array and the end,
    and returns the length of the array
    See test for examples
    */
int arrLenRec(int* start, int* end)
{

}

bool arrLenRec_TEST()
{
    int arr[] = { 1, 2, 3, 4,  5 };
    int expected = 5;
    int actualVal = arrLenRec(arr, arr + 5);
    return expected == actualVal;
}

/*  Warmup 2: array Sum recursive
    Write a function that takes in the start of the array and the end,
    and returns the Sum of the array
    See test for examples
    */
int arrSumRec(int* start, int* end)
{

}

bool arrSumRec_TEST()
{
    int arr[] = { -1, 100, 3, 4,  -5 };
    int expected = 101;
    int actualVal = arrSumRec(arr, arr + 5);
    return expected == actualVal;
}

/*  Warmup 3: array Max recursive
    Write a function that takes in the start of the array and the end,
    and returns the Max of the array
    See test for examples
    */
int arrMaxRec(int* start, int* end)
{

}

bool arrMaxRec_TEST()
{
    int arr[] = { -1, 100, 3, 4,  -5 };
    int expected = 100;
    int actualVal = arrMaxRec(arr, arr + 5);
    return expected == actualVal;
}

/*------------------8 Aug 2019-----------------*/

// level traversal of a tree

//     3
//    /  \
//   9   20
//  /   /  \
// 10   15   7
//     /  \
//    15   7
// return [[3], [9, 20], [10, 15, 7]

/*
int treeLvl = 0;
push 3 level 0
push 9 level 1
push 20 level 1
push 10 level 2
push 15 level 2
push 7 level 2
push 15 level 3
push 7 level 3
*/

#include <vector>
using std::vector;

class NodeLvl {
private:
    TreeNode* node;
    int lvl;
public:
    NodeLvl(TreeNode* node_in, int lvl_in) : node(node_in), lvl(lvl_in) {}
};

vector<vector<int>> levelOrderTraversal(TreeNode* root) {
    constexpr int ROOT_LEVEL = 0;
    vector<vector<int>> levels;
    
    // check if root is null
    if (!root) {
        return levels;
    }

    queue<NodeLvl> nodes;
    nodes.push(NodeLvl(root, ROOT_LEVEL)); // root is level 0

    // loop until finish all nodes
    while (!nodes.empty()) {
        // check if levels[nodes.front().level]exists
        int currentLvl = nodes.front().lvl;
        // initialize to prevent segfault
        if (levels.size() <= currentLvl) {
            vector<int> level;
            levels.push_back(level);
        }
        // push this node into the vector
        levels[currentLvl].push_back(nodes.front()->val);
        // save returned reference as reference (performance)
        auto top = nodes.front();
        // push the left and right
        if (top->left) {
            nodes.push(NodeLvl(top->left, currentLvl + 1));
        }
        if (top->right) {
            nodes.push(NodeLvl(top->right, currentLvl + 1));
        }
        nodes.pop();
    }
    return levels;
}


vector<vector<int>> levelOrderTraversal(TreeNode* root)
{
// create solution vector<vector<int>>
        vector<vector<int>> levels;
        // base case: if root is null, return 
        if (!root) {
            return levels;
        }
        // create map to indicate level capacity
        map<int,int> levelCapacity;
        // breadth-first search: add a node and then its neighbors before removing it
        // initialize queue with the root node
        queue<TreeNode*> nodes;
        nodes.push(root);
        // tracks index of the vector the node will be pushed into
        int vecIndex = 0;
        // loop continues until all nodes in queue have been processed
        while (!nodes.empty()) { 
            // check if the map has been initialized for this level
            if (levelCapacity[vecIndex] == 0) {
                levelCapacity[vecIndex] = pow(2, vecIndex);
            }
            // check if this node should be pushed into this level
            // (is this level full?)
            if (levels[vecIndex].size() >= levelCapacity[vecIndex]) {
                ++vecIndex;
            }
            levels[vecIndex].push_back(nodes.front()->val);
            // add the front node's neighbors
            if (nodes.front()->left) {
                nodes.push(nodes.front()->left);
            }
            if (nodes.front()->right) {
                nodes.push(nodes.front()->right);
            }
            // pop the front node from the queue
            nodes.pop();
        }
        return levels;
    }
}

#include <cassert>
using namespace std;
int main()
{
    assert(arrLenRec_TEST());
    assert(arrSumRec_TEST());
    assert(arrMaxRec_TEST());
}