Wednesday, 27 April 2016

Merge X-way Sorted List

1. Problem Description
This is a Google interview question from careercup. Here is the origin thread
'
A list L is too big to fit in memory. L is partially sorted. Partially sorted in a specific way: x-sorted L[i] < L[i+x]. Any element is at most x indices out of position. 

You can look at the condition in a different way too..
L[i] >= L[i-x]

Sort the list L.
- jss_777 March 30, 2016 in United States | Report Duplicate | Flag '.

2. Data Structure and Algorithm
As the input array meets this condition "L[i] < L[i+x]", literally we have x-way of sorted list as,
    - Arr1: L[0] < L[X] < L[2X] < ......
    - Arr2: L[1] < L[X+1] < L[2X+1] < L[3X+1] < ......
    - Arr3: L[2] < L[X+2] < L[2X+2] < L[3X+1] < ......
      ......
    - ArrX: L[X-1] < L[2X-1] < L[3X-1] < L[4X-1] < ......

Merge sorted arrays into a single one. It is not unfamiliar to us, as it is the last step of merging sort. In merging sort two sorted arrays with the size of window is merged into a bigger array (literally size of two window size). Keep sorting and merging of the smaller window and eventually sort and merge into the full size.

Coming back to this problem with X-way sorted array. There are two ways of tackling this Itproblem.

The 1st approach:
It is to use the exactly same idea as merge sort.
    - Merge Arr1 and Arr2 to become a bigger size of new array Arr_A
    - Merge Arr3 and Arr3 to become a bigger size of new array Arr_B
    ......
Now we have X/2 sorted arrays if X is an even number or X/2 + 1 sorted arrays now if X is an odd number. Keep the above process (merge Arr_A and Arr_B, merge Arr_C and Arr_D, ......) until merged into a single array.

The 2nd approach:
It is to merge X-way in one row directly into a single array. Keep taking the heads (the smallest value of Arr1, Arr2, .. ArrX) and find the least value.
    - Initial heads (L[0], L[1], ......, L[X-1]
    - Find the least value, say it is L[i], which is the least value of L (globally)
    - New heads array (L[0], L[1], ..., L[i-1], L[i+X], L[i+1], ..., L[X-1]
    - Find the least value in the new heads array, say it is L[j], which is the 2rd least value of L
       Head arrays will reduce its size if L[j] hit the end of Arr_J
    - Now replace L[j] with L[j+X]  to form the new heads
    - Keep the above two steps until exhaust the whole array

Implementation wise it is to use a min-heap (priority queue in C++) to take the header array. Each time to pop the head, L[i] (which is the least value in the heads array) and push its next, L[i+X] into the queue. This technique has been used in this post as well, Find the Nth Multiple Given a Set. 

3. C++ Implementation
This implementation implements the 2nd approach with two option of data structure of L. One is linked list and another is an array (std::vector).
As the interview question stated that L is very large. The best approach is to do in-place sorting/merging. And this implementation is not an in-place solution.

// ********************************************************************************
// Implementation
// ********************************************************************************
#include "../DetectCircleInLinkedList/DetectCircleInLinkedList/LinkedListElement.h"
#include "../DetectCircleInLinkedList/DetectCircleInLinkedList/LinkedList.h"

#include <queue>
#include <vector>

template <typename T>
struct LLE_Comparator
{
    bool operator() (LinkedListElement<T>* &lhs, LinkedListElement<T>* &rhs) {
        return lhs->data > rhs->data;
    }
};

template<typename T>
LinkedListElement<T>* AdvanceByX(LinkedListElement<T>* start, unsigned int X)
{
    unsigned int step = 0;
    while (start && step < X) {
        start = start->next;
        ++step;
    }

    return start;
}

template <typename T>
void MergeXwaySortedLL(LinkedList<T> &input, const unsigned int X, LinkedList<T> &result)
{
    using MinHeap = std::priority_queue<LinkedListElement<T>*, std::vector<LinkedListElement<T>*>, LLE_Comparator<T>>;

    LinkedListElement<T> **head = input.Release();
    if (!head || !(*head)) {
        return;
    }

    unsigned int count = 0;
    LinkedListElement<T> *temp = *head;
    MinHeap topNodesOfXways;
    // get first X nodes
    while (count < X && temp) {
        topNodesOfXways.push(temp);
        temp = temp->next;
        ++count;
    }

    while (!topNodesOfXways.empty()) {
        temp = topNodesOfXways.top();
        result.PushBack(temp->data);
        temp = AdvanceByX(temp, X);
        topNodesOfXways.pop();
        if (temp) {
            topNodesOfXways.push(temp);
        }
    }
}

template <typename T>
struct ValueIndexPair{
    ValueIndexPair(const T& val, size_t idx)
        : value(val), index(idx)
    {}
    ValueIndexPair()
    {}

    T value;
    size_t index;
};

template <typename T>
struct ArrE_Comparator
{
    bool operator() (ValueIndexPair<T> &lhs, ValueIndexPair<T> &rhs) {
        return lhs.value > rhs.value;
    }
};

template <typename T>
std::vector<T> MergeXwaySortedArr(const std::vector<T> &arr, const unsigned int X)
{
    using MinHeap = std::priority_queue<ValueIndexPair<T>, std::vector<ValueIndexPair<T>>, ArrE_Comparator<T>>;

    const size_t LEN = arr.size();
    if (X > LEN) {
        return std::vector<T>();
    }

    // push first X into heap
    MinHeap minHeap;
    for (unsigned int count = 0; count < X; ++count) {
        minHeap.push(ValueIndexPair<T>(arr[count], count));
    }

    std::vector<T> result;
    result.reserve(LEN);
    while (!minHeap.empty()) {
        ValueIndexPair<T> &temp = minHeap.top();
        result.push_back(temp.value);
        if ((temp.index + X) < LEN) {
            minHeap.push(ValueIndexPair<T>(arr[temp.index + X], temp.index + X));
        }
        minHeap.pop();
    }

    return result;
}


// ********************************************************************************
// Test
// ********************************************************************************
#include <cassert>
#include <array>
void Test_LL()
{
    {
        LinkedList<int> input;
        LinkedList<int> result;
        input.PushBack(1);
        MergeXwaySortedLL(input, 1, result);
        LinkedListElement<int> *head = *(result.Release());
        LinkedListElement<int> *tail = *(result.ReleaseTail());
        assert(head->data == 1);
        assert(tail->data == 1);
    }

    {
        LinkedList<int> input;
        LinkedList<int> result;
        const std::array<int, 16> data = { 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15 };
        for (auto iter = data.begin(); iter != data.end(); ++iter) {
            input.PushBack(*iter);
        }

        MergeXwaySortedLL(input, 4, result);
        LinkedListElement<int> *curNode = *(result.Release());
        unsigned int count = 0;
        while (curNode) {
            assert(curNode->data == count);
            curNode = curNode->next;
            ++count;
        }

        assert(count == 16);
    }
}

void Test_Arr()
{
    {
        const std::vector<int> data = { 1, 3, 2, 4 };
        std::vector<int> result = MergeXwaySortedArr(data, 5);
        assert(result.empty() == true);
        result = MergeXwaySortedArr(data, 2);
        assert(result == std::vector<int>({ 1, 2, 3, 4 }));
    }

    {
        const std::vector<int> data = { 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15 };
        std::vector<int> result = MergeXwaySortedArr(data, 17);
        assert(result.empty() == true);
        result = MergeXwaySortedArr(data, 4);
        assert(result == std::vector<int>({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}));
    }
}

Saturday, 26 March 2016

Dynamic Programming - Find the Difference of Ascending Sequence and Descending Seqeunec

1. Problem Description

Q1) Given an array 'A' of size 'n' and a number 'm' such that 'm <= n'. For all subsets of 'A' of size 'm', return the difference between the number of non-increasing and non-decreasing sub-sequences.

He asked me to write the program on paper in any language.

This is how i approached it.
1) First i gave the brute force solution and explained it to him. He liked it.
2) Then he asked for the complexity of the solution. I gave right ans.
3) Then i told him that it can be optimized by 'xyz' approach.
4) Then he asked me if i can write the solution. I said i will first explain him how it can be solved. Then if he wants me to write the code, he will have to leave me alone for some time. He agreed. I explained.
5) There was a bug in my solution. He gave a test case that exposed it. Then i rectified the bug. He accepted.
6) He said that it. He does not need the full code.
- uday4friendz March 04, 2016 in India for Product Details Page | Report Duplicate | Flag ".

2. Data Structure And Algorithm
There is not really much to talk about the data structure. Simply use array to represent the input sequence. The key point here is the algorithm - namely the complexity. This is a combination problem for given m and n. The total number of possible sequences is C(n, m) - pick up m from n, where C(n, m) = n!/(m! * (n-m)!). Therefore theoretically it has computation complexity of O(N!) - factorial complexity. It should absolutely avoided in implementation.

It is an combination problem and likely dynamic programming is a good candidate to solve it. Here we are only caring about ascending and descending sequences. In order to form a sequence m must be greater than 1 and not greater than n. m's range is [2, n]. In order to know if this sequence is ascending or descending the starting two digits are to decide its ascending/descending order. Suppose that we know the first two digits of the sequence x, y and the index, i, of next available digit in the array. Then the sub-problem can be described as,
    - F(N, x, y, i) , where N = m -2, i <= (n-m+2) 
        * F(N-1, y, arr[i], i+1) if x < y and y < arr[i] (ascending order sequence candidate)
        * F(N-1, y, arr[i], i+1) if x > y and y > arr[i] (descending order)
        * 0, neither an ascending sequence nor a descending sequence
    - F(0, r, s, t) = 1

Again dynamic programming help us to solve the problem but does not help us to reduce the complexity. In this case the caching technique is employed to cache the result to avoid the repeated computation. See the examples in Dynamic Programming - Stock Best Buy and Sell Problem: Google Interview Question and Dynamic programming - Sum K of N dices with S sides. Two caching repositories are needed - one for ascending order sequence and another for descending order sequence. The hash key is pair of (i, N) - the index of the current available number in the array and the length of the remaining of sequence. The cache technique requires O(n*m) space. In the best case it can achieve O((n-m)^2) computation complexity.

3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <exception>
#include <unordered_map>
#include <vector>

class InvalidParamException : public std::exception
{
public:
    InvalidParamException(const std::string & msg)
        : m_msg(msg)
    {}

    const char* what() const {
        return m_msg.c_str();
    }
private:
    const std::string m_msg;
};

struct HashKey
{
    size_t idx;
    size_t remainingSeqLen;

    bool operator==(const HashKey& rhs) const {
        return idx == rhs.idx && remainingSeqLen == rhs.remainingSeqLen;
    }
};

struct HashKeyHashFunc
{
    size_t operator()(const HashKey &key) const {
        return std::hash<size_t>()(key.idx) ^
            std::hash<size_t>()(key.remainingSeqLen);
    }

    bool operator()(const HashKey &lhs, const HashKey &rhs) const {
        return lhs == rhs;
    }
};

using HashMap = std::unordered_map<HashKey, int, HashKeyHashFunc, HashKeyHashFunc>;

template <typename T>
int DetectAscendingOrDescendingSequence(const std::vector<T> &input,
                                        const size_t input_size,
                                        const size_t idx,
                                        const bool isAscending,
                                        size_t m,
                                        HashMap &cacheAscending,
                                        HashMap &cacheDescending)
{
    if (!m) {
        // F(0, r, s, t) return 1
        return 1;
    }

    // Return the cached value if it's a repeated computation
    if (isAscending) {
        auto foundIter = cacheAscending.find(HashKey{ idx, m });
        if (foundIter != cacheAscending.end()) {
            return foundIter->second;
        }
    }
    else {
        auto foundIter = cacheDescending.find(HashKey{ idx, m });
        if (foundIter != cacheDescending.end()) {
            return foundIter->second;
        }
    }

    int numSeq = 0;
    for (size_t i = idx; i <= (input_size - m); ++i) {
        // Continue the sub-problem if sequence's order is maintained
        // Check next available digits if the order is broken
        if ( (isAscending && input[idx - 1] < input[i]) ||
             (!isAscending && input[idx - 1] > input[i])) {
            numSeq += DetectAscendingOrDescendingSequence(input,
                input_size,
                i + 1,
                isAscending,
                m - 1,
                cacheAscending,
                cacheDescending);
        }
    }

    // cache the result
    if (isAscending) {
        cacheAscending.insert(std::make_pair(HashKey{ idx, m }, numSeq));
    }
    else {
        cacheDescending.insert(std::make_pair(HashKey{ idx, m }, numSeq));
    }

    return numSeq;
}

template <typename T>
int GetDiffOfAscendingAndDescedningSequence(const std::vector<T> &input, size_t m)
{
    if (m < 2) {
        throw InvalidParamException("The length of sequence MUST be >= 2.");
    }

    if (input.empty()) {
        throw InvalidParamException("The input array is empty.");
    }

    const size_t INPUT_LEN = input.size();
    if (INPUT_LEN < m) {
        throw InvalidParamException("The length of sequence must be <= the length of input array.");
    }

    int numOfAscending = 0;
    int numOfDescening = 0;
    bool isAscending;
    int temp;
    HashMap CacheAscendingSeq;
    HashMap CacheDescedningSeq;
    for (size_t idx1 = 0; idx1 <= INPUT_LEN - m; ++idx1) {
        for (size_t idx2 = idx1 + 1; idx2 <= (INPUT_LEN - m + 1); ++idx2) {
            // First two digits in the sequence to decide ascending/descending
            isAscending = input[idx1] < input[idx2];
            temp = DetectAscendingOrDescendingSequence(input,
                                                       INPUT_LEN,
                                                       idx2 + 1,
                                                       isAscending,
                                                       m - 2,
                                                       CacheAscendingSeq,
                                                       CacheDescedningSeq);
            if (isAscending) {
                numOfAscending += temp;
            }
            else {
                numOfDescening += temp;
            }
        }
    }

    return numOfAscending - numOfDescening;
}

// ********************************************************************************
// Test
// ********************************************************************************

#include <cassert>
void TestFindDiffOfAscAndDescSeq()
{
    {
        bool exceptionCaught = false;
        try {
            const std::vector<int> input;
            GetDiffOfAscendingAndDescedningSequence(input, 2);
        }
        catch (const InvalidParamException &e) {
            exceptionCaught = true;
        }
        catch (...)
        {
        }
        assert(exceptionCaught == true);

        exceptionCaught = false;
        try {
            const std::vector<int> input = { 1, 2, 3 };
            GetDiffOfAscendingAndDescedningSequence(input, 1);
        }
        catch (const InvalidParamException &e) {
            exceptionCaught = true;
        }
        catch (...)
        {
        }
        assert(exceptionCaught == true);

        exceptionCaught = false;
        try {
            const std::vector<int> input = { 1, 2, 3 };
            GetDiffOfAscendingAndDescedningSequence(input, 4);
        }
        catch (const InvalidParamException &e) {
            exceptionCaught = true;
        }
        catch (...)
        {
        }
        assert(exceptionCaught == true);

        exceptionCaught = false;
        try {
            const std::vector<int> input = { 1, 2, 3 };
            GetDiffOfAscendingAndDescedningSequence(input, 1);
        }
        catch (const InvalidParamException &e) {
            exceptionCaught = true;
        }
        catch (...)
        {
        }
        assert(exceptionCaught == true);
    }
    {
        const std::vector<int> input = { 1, 2, 3, 4, 5, 6, 7, 8 };
        assert(GetDiffOfAscendingAndDescedningSequence(input, 2) == 28);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 3) == 56);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 4) == 70);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 5) == 56);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 6) == 28);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 7) == 8);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 8) == 1);
    }
    {
        const std::vector<int> input = { 8, 7, 6, 5, 4, 3, 2, 1 };
        assert(GetDiffOfAscendingAndDescedningSequence(input, 2) == -28);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 3) == -56);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 4) == -70);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 5) == -56);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 6) == -28);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 7) == -8);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 8) == -1);
    }
    {
        const std::vector<int> input = { 8, 7, 6, 5, 4, 3, 2, 1, 11, 12, 13, 14, 15, 16, 17, 18 };
        assert(GetDiffOfAscendingAndDescedningSequence(input, 2) == 8*8); 
        assert(GetDiffOfAscendingAndDescedningSequence(input, 3) == 8*28); 
        assert(GetDiffOfAscendingAndDescedningSequence(input, 4) == 8*56);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 5) == 8*70);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 6) == 8*56);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 7) == 8*28);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 8) == 8*8);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 9) == 8);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 10) == 0);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 11) == 0);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 12) == 0);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 13) == 0);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 14) == 0);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 15) == 0);
        assert(GetDiffOfAscendingAndDescedningSequence(input, 16) == 0);
    }

}

Monday, 21 March 2016

BST - Find the Closest Value

1. Problem Description
This is an Amazon interview question for software develop engineer from careercup. Here is the original thread,
"
This was the first round. A written test. I was asked to write a complete program that can execute with proper syntax. Also comment on the complexity and add comments to code where necessary. And i had to write it on Paper. Three questions were given and was asked to answer any two. I was given 1hr time for this. 

This was one of the questions
Q) You are given a BST and a number k. Find the node in the tree which has the value closest to k.
- uday4friendz March 04, 2016 in India for Product Details Page | Report Duplicate | Flag 
".

2. Data Structure and Algorithm
This is binary search tree question. The data structure is binary tree and the algorithm is binary search. The idea to find the closest value in the tree is similar to binary search to spot the exact value in the tree. The extra thing need to be done is to keep the lower bound and the upper bound when the search process goes on.

In the binary search algorithm the range of search space is gradually narrowed down as each step goes deep into the tree. Finding the closest value is similar but need to keep tracking the range - the lower and upper bound. In the case of the the value appearing in the tree, this is exactly like binary search. If not, then keep tracking the range - lower/upper bound. When hitting the bottom level (leaf nodes), compare the distance between value and lower bound, and the distance between the value and the upper bound, Pick the bound with the smaller distance.

Pseudo-code:
    1. Start from root, curNode = root,  lowerBound = NULL, upperBound = NULL
    2. Go to step 6, if cureNode is NULL
    3. Return curNode if it has the same value we are searching
    4. upperBound = curNode, if curNode has larger value
        curNode = curNode->left and go to Step 2
    5. lowerBound = curNode, if curNode has smaller value
        curNode = curNode->right and go to Step 2
    6. Return Null if both lowerBound and upperBound are NULL
        Return lowerBound if lowerBound is not NULL and upperBound is NULL
        Return upperBound if lowerBound is NULL and upperBound is not NULL
        Return lowerBound if distance(val, lowerBound) <= distance(val, upperBound)
        Return upperBound otherwise.

3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
template <typename T>
TreeNode<T>* FindClosetNode_R_Internal(TreeNode<T> *root,
                                       const T& val,
                                       TreeNode<T>* lowerBound,
                                       TreeNode<T>* upperBound)
{
    if (!root) {
        if (lowerBound && upperBound) {
            // TODO: To cope other T type, implement a its own "closest" function
            T toLowerBound = abs(val - *lowerBound->data);
            T toUpperBound = abs(*upperBound->data - val);
            return toLowerBound <= toUpperBound ? lowerBound : upperBound;
        }
        else if (lowerBound) {
            return lowerBound;
        }
        else if (upperBound) {
            return upperBound;
        }
        return NULL;
    }

    if (*root->data == val) {
        return root;
    }
    else if (*root->data > val) {
        return FindClosetNode_R_Internal(root->left, val, lowerBound, root);
    }
    else {
        return FindClosetNode_R_Internal(root->right, val, root, upperBound);
    }
}

// Recursive implementation
template <typename T>
TreeNode<T>* FindClosetNode_R(TreeNode<T> *root, const T& val)
{
    return FindClosetNode_R_Internal<T>(root, val, NULL, NULL);
}

// Non-recursive implementation
template <typename T>
TreeNode<T>* FindClosetNode(TreeNode<T> *root, const T& val)
{
    TreeNode<T> *lowerBound = NULL;
    TreeNode<T> *upperBound = NULL;

    TreeNode<T> *curNode = root;
    while (curNode) {
        if (*curNode->data == val) {
            return curNode;
        }
        else if (*curNode->data > val) {
            upperBound = curNode;
            curNode = curNode->left;
        }
        else {
            lowerBound = curNode;
            curNode = curNode->right;
        }
    }

    if (lowerBound && upperBound) {
        // TODO: To cope other T type, implement a its own "closest" function
        T toLowerBound = abs(val - *lowerBound->data);
        T toUpperBound = abs(*upperBound->data - val);
        return toLowerBound <= toUpperBound ? lowerBound : upperBound;
    }
    else if (lowerBound) {
        return lowerBound;
    }
    else if (upperBound) {
        return upperBound;
    }

    return NULL;
}

// ********************************************************************************
// Test
// ********************************************************************************
void TestFindCloesetNode_R()
{
    TreeNode<double> *root = NULL;
    assert(FindClosetNode_R(root, 0.0) == NULL);

    std::vector<double> input = { 1.0 };
    root = ConstructTreeRecursive(input);
    assert(root);
    TreeNode<double> *foundNode = FindClosetNode_R(root, 1.0);
    assert(*foundNode->data == 1.0);
    foundNode = FindClosetNode_R(root, 100.0);
    assert(*foundNode->data == 1.0);
    foundNode = FindClosetNode_R(root, -100.0);
    assert(*foundNode->data == 1.0);
    DeleteTree_BU(&root);

    input = { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0 };
    root = ConstructTreeOnSortedValueBFS(input);
    assert(root);
    foundNode = FindClosetNode_R(root, -100.0);
    assert(*foundNode->data == 1.0);
    foundNode = FindClosetNode_R(root, -1.0);
    assert(*foundNode->data == 1.0);
    foundNode = FindClosetNode_R(root, -1.0);
    assert(*foundNode->data == 1.0);
    foundNode = FindClosetNode_R(root, 1.2);
    assert(*foundNode->data == 1.0);
    foundNode = FindClosetNode_R(root, 1.6);
    assert(*foundNode->data == 2.0);
    foundNode = FindClosetNode_R(root, 2.0);
    assert(*foundNode->data == 2.0);
    foundNode = FindClosetNode_R(root, 2.1);
    assert(*foundNode->data == 2.0);
    foundNode = FindClosetNode_R(root, 2.6);
    assert(*foundNode->data == 3.0);
    foundNode = FindClosetNode_R(root, 3.0);
    assert(*foundNode->data == 3.0);
    foundNode = FindClosetNode_R(root, 3.4);
    assert(*foundNode->data == 3.0);
    foundNode = FindClosetNode_R(root, 3.6);
    assert(*foundNode->data == 4.0);
    foundNode = FindClosetNode_R(root, 4.0);
    assert(*foundNode->data == 4.0);
    foundNode = FindClosetNode_R(root, 4.4);
    assert(*foundNode->data == 4.0);
    foundNode = FindClosetNode_R(root, 4.6);
    assert(*foundNode->data == 5.0);
    foundNode = FindClosetNode_R(root, 5.0);
    assert(*foundNode->data == 5.0);
    foundNode = FindClosetNode_R(root, 5.3);
    assert(*foundNode->data == 5.0);
    foundNode = FindClosetNode_R(root, 5.6);
    assert(*foundNode->data == 6.0);
    foundNode = FindClosetNode_R(root, 6.0);
    assert(*foundNode->data == 6.0);
    foundNode = FindClosetNode_R(root, 6.3);
    assert(*foundNode->data == 6.0);
    foundNode = FindClosetNode_R(root, 6.6);
    assert(*foundNode->data == 7.0);
    foundNode = FindClosetNode_R(root, 7.0);
    assert(*foundNode->data == 7.0);
    foundNode = FindClosetNode_R(root, 7.3);
    assert(*foundNode->data == 7.0);
    foundNode = FindClosetNode_R(root, 7.6);
    assert(*foundNode->data == 8.0);
    foundNode = FindClosetNode_R(root, 8.0);
    assert(*foundNode->data == 8.0);
    foundNode = FindClosetNode_R(root, 8.3);
    assert(*foundNode->data == 8.0);
    foundNode = FindClosetNode_R(root, 8.6);
    assert(*foundNode->data == 9.0);
    foundNode = FindClosetNode_R(root, 9.0);
    assert(*foundNode->data == 9.0);
    foundNode = FindClosetNode_R(root, 9.3);
    assert(*foundNode->data == 9.0);
    foundNode = FindClosetNode_R(root, 9.6);
    assert(*foundNode->data == 10.0);
    foundNode = FindClosetNode_R(root, 10.0);
    assert(*foundNode->data == 10.0);
    foundNode = FindClosetNode_R(root, 10.3);
    assert(*foundNode->data == 10.0);
    foundNode = FindClosetNode_R(root, 10.6);
    assert(*foundNode->data == 11.0);
    foundNode = FindClosetNode_R(root, 11.0);
    assert(*foundNode->data == 11.0);
    foundNode = FindClosetNode_R(root, 11.3);
    assert(*foundNode->data == 11.0);
    foundNode = FindClosetNode_R(root, 11.6);
    assert(*foundNode->data == 12.0);
    foundNode = FindClosetNode_R(root, 12.0);
    assert(*foundNode->data == 12.0);
    foundNode = FindClosetNode_R(root, 12.3);
    assert(*foundNode->data == 12.0);
    foundNode = FindClosetNode_R(root, 12.6);
    assert(*foundNode->data == 13.0);
    foundNode = FindClosetNode_R(root, 13.0);
    assert(*foundNode->data == 13.0);
    foundNode = FindClosetNode_R(root, 13.3);
    assert(*foundNode->data == 13.0);
    foundNode = FindClosetNode_R(root, 13.6);
    assert(*foundNode->data == 14.0);
    foundNode = FindClosetNode_R(root, 14.0);
    assert(*foundNode->data == 14.0);
    foundNode = FindClosetNode_R(root, 14.3);
    assert(*foundNode->data == 14.0);
    foundNode = FindClosetNode_R(root, 14.6);
    assert(*foundNode->data == 15.0);
    foundNode = FindClosetNode_R(root, 15.0);
    assert(*foundNode->data == 15.0);
    foundNode = FindClosetNode_R(root, 15.3);
    assert(*foundNode->data == 15.0);
    foundNode = FindClosetNode_R(root, 15.6);
    assert(*foundNode->data == 16.0);
    foundNode = FindClosetNode_R(root, 16.0);
    assert(*foundNode->data == 16.0);
    foundNode = FindClosetNode_R(root, 16.3);
    assert(*foundNode->data == 16.0);
    foundNode = FindClosetNode_R(root, 100.0);
    assert(*foundNode->data == 16.0);
    DeleteTree_TD(&root);
}

void TestFindCloesetNode()
{
    TreeNode<double> *root = NULL;
    assert(FindClosetNode(root, 0.0) == NULL);

    std::vector<double> input = { 1.0 };
    root = ConstructTreeRecursive(input);
    assert(root);
    TreeNode<double> *foundNode = FindClosetNode(root, 1.0);
    assert(*foundNode->data == 1.0);
    foundNode = FindClosetNode(root, 100.0);
    assert(*foundNode->data == 1.0);
    foundNode = FindClosetNode(root, -100.0);
    assert(*foundNode->data == 1.0);
    DeleteTree_BU(&root);

    input = { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0 };
    root = ConstructTreeOnSortedValueBFS(input);
    assert(root);
    foundNode = FindClosetNode(root, -100.0);
    assert(*foundNode->data == 1.0);
    foundNode = FindClosetNode(root, -1.0);
    assert(*foundNode->data == 1.0);
    foundNode = FindClosetNode(root, -1.0);
    assert(*foundNode->data == 1.0);
    foundNode = FindClosetNode(root, 1.2);
    assert(*foundNode->data == 1.0);
    foundNode = FindClosetNode(root, 1.6);
    assert(*foundNode->data == 2.0);
    foundNode = FindClosetNode(root, 2.0);
    assert(*foundNode->data == 2.0);
    foundNode = FindClosetNode(root, 2.1);
    assert(*foundNode->data == 2.0);
    foundNode = FindClosetNode(root, 2.6);
    assert(*foundNode->data == 3.0);
    foundNode = FindClosetNode(root, 3.0);
    assert(*foundNode->data == 3.0);
    foundNode = FindClosetNode(root, 3.4);
    assert(*foundNode->data == 3.0);
    foundNode = FindClosetNode(root, 3.6);
    assert(*foundNode->data == 4.0);
    foundNode = FindClosetNode(root, 4.0);
    assert(*foundNode->data == 4.0);
    foundNode = FindClosetNode(root, 4.4);
    assert(*foundNode->data == 4.0);
    foundNode = FindClosetNode(root, 4.6);
    assert(*foundNode->data == 5.0);
    foundNode = FindClosetNode(root, 5.0);
    assert(*foundNode->data == 5.0);
    foundNode = FindClosetNode(root, 5.3);
    assert(*foundNode->data == 5.0);
    foundNode = FindClosetNode(root, 5.6);
    assert(*foundNode->data == 6.0);
    foundNode = FindClosetNode(root, 6.0);
    assert(*foundNode->data == 6.0);
    foundNode = FindClosetNode(root, 6.3);
    assert(*foundNode->data == 6.0);
    foundNode = FindClosetNode(root, 6.6);
    assert(*foundNode->data == 7.0);
    foundNode = FindClosetNode(root, 7.0);
    assert(*foundNode->data == 7.0);
    foundNode = FindClosetNode(root, 7.3);
    assert(*foundNode->data == 7.0);
    foundNode = FindClosetNode(root, 7.6);
    assert(*foundNode->data == 8.0);
    foundNode = FindClosetNode(root, 8.0);
    assert(*foundNode->data == 8.0);
    foundNode = FindClosetNode(root, 8.3);
    assert(*foundNode->data == 8.0);
    foundNode = FindClosetNode(root, 8.6);
    assert(*foundNode->data == 9.0);
    foundNode = FindClosetNode(root, 9.0);
    assert(*foundNode->data == 9.0);
    foundNode = FindClosetNode(root, 9.3);
    assert(*foundNode->data == 9.0);
    foundNode = FindClosetNode(root, 9.6);
    assert(*foundNode->data == 10.0);
    foundNode = FindClosetNode(root, 10.0);
    assert(*foundNode->data == 10.0);
    foundNode = FindClosetNode(root, 10.3);
    assert(*foundNode->data == 10.0);
    foundNode = FindClosetNode(root, 10.6);
    assert(*foundNode->data == 11.0);
    foundNode = FindClosetNode(root, 11.0);
    assert(*foundNode->data == 11.0);
    foundNode = FindClosetNode(root, 11.3);
    assert(*foundNode->data == 11.0);
    foundNode = FindClosetNode(root, 11.6);
    assert(*foundNode->data == 12.0);
    foundNode = FindClosetNode(root, 12.0);
    assert(*foundNode->data == 12.0);
    foundNode = FindClosetNode(root, 12.3);
    assert(*foundNode->data == 12.0);
    foundNode = FindClosetNode(root, 12.6);
    assert(*foundNode->data == 13.0);
    foundNode = FindClosetNode(root, 13.0);
    assert(*foundNode->data == 13.0);
    foundNode = FindClosetNode(root, 13.3);
    assert(*foundNode->data == 13.0);
    foundNode = FindClosetNode(root, 13.6);
    assert(*foundNode->data == 14.0);
    foundNode = FindClosetNode(root, 14.0);
    assert(*foundNode->data == 14.0);
    foundNode = FindClosetNode_R(root, 14.3);
    assert(*foundNode->data == 14.0);
    foundNode = FindClosetNode(root, 14.6);
    assert(*foundNode->data == 15.0);
    foundNode = FindClosetNode(root, 15.0);
    assert(*foundNode->data == 15.0);
    foundNode = FindClosetNode(root, 15.3);
    assert(*foundNode->data == 15.0);
    foundNode = FindClosetNode(root, 15.6);
    assert(*foundNode->data == 16.0);
    foundNode = FindClosetNode(root, 16.0);
    assert(*foundNode->data == 16.0);
    foundNode = FindClosetNode(root, 16.3);
    assert(*foundNode->data == 16.0);
    foundNode = FindClosetNode(root, 100.0);
    assert(*foundNode->data == 16.0);
    DeleteTree_TD(&root);
}

Monday, 14 March 2016

Find the Path With Maximal Sum in Pyramid (II)

1. Problem Description
See the problem description on BTS - Find the Path With Maximal Sum in Pyramid.

2. Data Structure and Algorithm
Instead of having a tree structure a native array structure should also do the job, because the each level has deterministic number of nodes
    - Level 0 (root) - 1 node
    - Level 1           - 2 nodes
    - Level 2           - 3 nodes
    - ......

And each node's child can be determined as long as the pyramid is given. Use Node(level, index) to represent a node in pyramid. where
   - level - represents which level this node is in, starting from 0
   - index - represents which location this node is in at this level, staring from 0
   - Root node - Node(0, 0)
   - Level 1 - Node(1, 0) and Node(1, 1)
   - Level 2 - Node(2, 0), Node(2, 1) and Node(2, 2)
   - Level 3 - Node(3, 0), Node(3, 1), Node(3, 2) and Node(3, 3)

In this mapping the children of a node is also deterministic.
    - Node(0, 0)'s children: Node(1, 0) and Node(1, 1)
    - Node(1, 0)'s children: Node(2, 0) and Node(2, 1)
    - Node(1, 1)'s children: Node(2, 1) and Node(2, 2)
    - Node(2, 0)'s children: Node(3, 0) and Node(3, 1)
    - Node(2, 1)'s children: Node(3, 1) and Node(3, 2)
    - Node(2, 3)'s children: Node(3, 2) and Node(3, 3)
    - ......

In summary for each level  and node
    - Level i has i+1 nodes
    - Non-leaf Node(i, j)'s children: Node(i+1, j) and Node(i+1, j+1)
    - Leaf Node(i, j) has no children

Finding the path with maximal sum is easy too because it can be resolved by the same idea of using tree data structure.

3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
template <typename T>
class PyramidArray
{
private:
    // Node representation in array
    struct PyramidArrNode {
        PyramidArrNode(size_t l, size_t n)
            : level(l), node(n)
        {}
       
        size_t GetIndex() const {
            return (level*(level + 1) >> 1) + node;
        }

        // root : level 0
        // level 1 - two nodes (0, 1)
        // level 2 - three nodes(0, 1, 2)
        // ......
        size_t level;
        size_t node;
    };

public:
    PyramidArray()
        : m_Depth(0)
    {}

    PyramidArray(const std::vector<T> &input)
        : PyramidArray()
    {
        ConstructPyramid(input);
    }

    void ConstructPyramid(const std::vector<T> &input) {
        const size_t level = ValidInput(input);
        if (level == 0) {
            throw PyramixException("Construction failure - invalid input");
        }
        m_data = input;
        m_Depth = level;
    }

    double FindMaxSum() const {
        if (m_data.empty()) {
            throw PyramixException("Pyramid not constructed yet");
        }

        return FindMaxSumInternal(PyramidArrNode(0, 0));
    }

    PyramidPath<T> FindMaxSumAndPath() const {
        if (m_data.empty()) {
            throw PyramixException("Pyramid not constructed yet");
        }

        return FindMaxSumAndPathInternal(PyramidArrNode(0, 0));
    }

    size_t GetDepth() const {
        if (m_data.empty()) {
            throw PyramixException("Pyramid not constructed yet");
        }
        return m_Depth;
    }

private:
    // sub-problem
    double FindMaxSumInternal(const PyramidArrNode &node) const {
        // Node(0, 0) -> 0
        // Node(1, 0) -> 1
        // Node(1, 1) -> 2
        // Node(2, 0) -> ((1+2)/2)*2+0 = 3;
        // Node(2, 1) ->
        if (!HaveChildren(node)) {
            return m_data[node.GetIndex()];
        }

        const double leftBranchSum = FindMaxSumInternal(PyramidArrNode(node.level + 1, node.node));
        const double rightBranchSum = FindMaxSumInternal(PyramidArrNode(node.level + 1, node.node + 1));
        return leftBranchSum > rightBranchSum ? leftBranchSum + m_data[node.GetIndex()] :
                                                rightBranchSum + m_data[node.GetIndex()];
    }

    // sub-problem
    PyramidPath<T> FindMaxSumAndPathInternal(const PyramidArrNode &node) const {
        if (!HaveChildren(node)) {
            return PyramidPath<T>(m_data[node.GetIndex()]);
        }
        const PyramidPath<T> leftBranchPath = FindMaxSumAndPathInternal(PyramidArrNode(node.level + 1, node.node));
        const PyramidPath<T> rightBranchPath = FindMaxSumAndPathInternal(PyramidArrNode(node.level + 1, node.node + 1));
        if (leftBranchPath.sum >= rightBranchPath.sum) {
            return PyramidPath<T>(leftBranchPath, m_data[node.GetIndex()]);
        }
        return PyramidPath<T>(rightBranchPath, m_data[node.GetIndex()]);
    }

    bool HaveChildren(const PyramidArrNode &node) const {
        const size_t size = (node.level + 1) * (node.level + 2) >> 1;
        return m_data.size() > size;
    }

    std::vector<T> m_data;
    size_t m_Depth;
};

// ********************************************************************************
// Test
// ********************************************************************************
void TestPyramidArray()
{
    {
        PyramidArray<int> pyramid;
        try {
            pyramid.GetDepth();
            assert(false);
        }
        catch (const PyramixException &e) {
            assert(std::string(e.what()) == "Pyramid not constructed yet");
        }
        try {
            pyramid.FindMaxSum();
            assert(false);
        }
        catch (const PyramixException &e) {
            assert(std::string(e.what()) == "Pyramid not constructed yet");
        }

        try {
            pyramid.FindMaxSumAndPath();
            assert(false);
        }
        catch (const PyramixException &e) {
            assert(std::string(e.what()) == "Pyramid not constructed yet");
        }

        try {
            pyramid.ConstructPyramid({ 1, 2, 3, 4 });
            assert(false);
        }
        catch (const PyramixException &e) {
            assert(std::string(e.what()) == "Construction failure - invalid input");
        }

        try {
            pyramid.FindMaxSum();
            assert(false);
        }
        catch (const PyramixException &e) {
            assert(std::string(e.what()) == "Pyramid not constructed yet");
        }

        try {
            pyramid.FindMaxSumAndPath();
            assert(false);
        }
        catch (const PyramixException &e) {
            assert(std::string(e.what()) == "Pyramid not constructed yet");
        }

        pyramid.ConstructPyramid({ 1, 2, 3 });
        assert(pyramid.GetDepth() == 2);
        assert(pyramid.FindMaxSum() == 4);
        auto path = pyramid.FindMaxSumAndPath();
        assert(path.sum == 4);
        assert(path.path == std::vector<int>({ 1, 3 }));

        pyramid.ConstructPyramid({ 1, 2, 3, 4, 5, 6 });
        assert(pyramid.GetDepth() == 3);
        assert(pyramid.FindMaxSum() == 10);
        path = pyramid.FindMaxSumAndPath();
        assert(path.sum == 10);
        assert(path.path == std::vector<int>({ 1, 3, 6 }));

        pyramid.ConstructPyramid({ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
        assert(pyramid.GetDepth() == 4);
        assert(pyramid.FindMaxSum() == 20);
        path = pyramid.FindMaxSumAndPath();
        assert(path.sum == 20);
        assert(path.path == std::vector<int>({ 1, 3, 6, 10 }));

        pyramid.ConstructPyramid({ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 });
        assert(pyramid.GetDepth() == 5);
        assert(pyramid.FindMaxSum() == 35);
        path = pyramid.FindMaxSumAndPath();
        assert(path.sum == 35);
        assert(path.path == std::vector<int>({ 1, 3, 6, 10, 15 }));
    }
}


BTS - Find the Path With Maximal Sum in Pyramid

1. Problem Description

e.g:
3
/ \
9 4
/ \ / \
1 8 2
/ \ / \ / \
4 5 8 2
answer: <3,9,8,8>, sum = 3+9+8+8=28
- a.asudeh February 18, 2016 in United States | Report Duplicate | Flag ".

2. Data Structure and Algorithm
My first attempt is to use the tree structure. Tree structure seems to be a very direct mapping to pyramid except one difference. The nodes (except the first node and the last node at the same level) have two parents from level 2 ( root - level 0) . There are two obvious ways to bridge this difference. One is to duplicate the nodes and then each has only one parent. The other is to keep as it is - two parents point to the same child.

In my implementation I picked the second option - two parents points the the same child. But this choice has a problem that tree free function does not work any more because of double memory free. As two parents point to the same child, the child is freed from the right branch of its left parent and will be freed the second time in the left branch of its right parent. Therefore in order to avoid the double free the pyramid tree structure has to be freed level by level - BFS. It is implemented in PyramidTree:Destory().

Finding the path with maximal sum becomes relatively easy because of the tree structure. It is a typical dynamic programming. Its sub-problem is that from the top down the sum of the current path plus its left and right branch, F(sum, node).
    - F(0, root)
    - Max(F(root->value, root->left), F(root->value, root->right)
    - ......
See the implementation of PyramidTree::FindMaxSum() and PyramidTree::FindMaxSumAndPath().

3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include "TreeNode.h"

#include <exception>
#include <queue>
#include <string>
#include <vector>

namespace Pyramid
{
template <typename T>
size_t ValidInput(const std::vector<T> &input) {
    if (input.empty()) {
        return 0;
    }

    // 1, 2, 3, 4, 5
    // 1 + 2 + 3 + 4 + 5 = (1+5)*5/2= 15
    // level = sqrt(30) = 5
    // 5 * 6 = 30
    const size_t inputLen = input.size();
    const size_t level = static_cast<size_t>(sqrt(inputLen * 2));
    return level*(level + 1) == 2 * inputLen ? level : 0;
}

template<typename T>
struct PyramidPath
{
    PyramidPath()
    : sum(0.)
    {}

    PyramidPath(const T& val)
        : sum(val)
    {
        path.push_back(val);
    }

    PyramidPath(const PyramidPath &rhs, T val)
        : sum(val + rhs.sum)
    {
        path.reserve(1 + rhs.path.size());
        path.push_back(val);
        path.insert(path.end(), rhs.path.begin(), rhs.path.end());
    }
    std::vector<T> path;
    double sum;
};

class PyramixException : std::exception
{
public:
    PyramixException(const std::string& msg)
        : m_ErrMsg(msg)
    {}

    const char* what() const{
        return m_ErrMsg.c_str();
    }

private:
    std::string m_ErrMsg;
};

template<typename T>
class PyramidTree
{
public:
    PyramidTree()
        : m_root(NULL), m_Depth(0)
    {}

    PyramidTree(const std::vector<T> &input)
        : m_root(NULL), m_Depth(0)
    {
        ConstructPyramid(input);
    }

    ~PyramidTree() {
        Destory();
    }

    void ConstructPyramid(const std::vector<T> &input)
    {
        const size_t level = ValidInput(input);
        if (level == 0) {
            throw PyramixException("Construction failure - invalid input");
        }

        Destory();

        // construct the tree
        m_Depth = level;
        std::queue<TreeNode<T>*> leafNodes;
        auto iter = input.begin();
        while (iter != input.end()) {
            if (leafNodes.empty()) {
                m_root = new TreeNode<T>(*iter);
                leafNodes.push(m_root);
                ++iter;
            }
            else {
                size_t leafNodeSize = leafNodes.size();
                TreeNode<T>* newNode = new TreeNode<T>(*iter);
                leafNodes.push(newNode);
                while (leafNodeSize) {
                    TreeNode<T>* curNode = leafNodes.front();
                    curNode->left = newNode;
                    ++iter;
                    newNode = new TreeNode<T>(*iter);
                    curNode->right = newNode;
                    leafNodes.pop();
                    leafNodes.push(newNode);
                    --leafNodeSize;
                }
                ++iter;
            }
        }
    }

    double FindMaxSum() const {
        if (!m_root) {
            throw PyramixException("Pyramid not constructed yet");
        }

        return FindMaxSumInternal(m_root);
    }

    PyramidPath<T> FindMaxSumAndPath() const {
        if (!m_root) {
            throw PyramixException("Pyramid not constructed yet");
        }

        return FindMaxSumAndPathInternal(m_root);
    }

    size_t GetDepth() const {
        if (!m_root) {
            throw PyramixException("Pyramid not constructed yet");
        }
        return m_Depth;
    }

    void Destory() {
        if (m_root) {
            // delete the tree
            std::queue<TreeNode<T>*> nodesAtSameLevel;
            nodesAtSameLevel.push(m_root);
            TreeNode<T>* curNode = NULL;
            while (!nodesAtSameLevel.empty()) {
                size_t numOfNodesAtSameLevel = nodesAtSameLevel.size();
                curNode = nodesAtSameLevel.front();
                if (curNode->left) {
                    nodesAtSameLevel.push(curNode->left);
                }
                while (numOfNodesAtSameLevel) {
                    curNode = nodesAtSameLevel.front();
                    if (curNode->right) {
                        nodesAtSameLevel.push(curNode->right);
                    }
                    delete curNode;
                    nodesAtSameLevel.pop();
                    --numOfNodesAtSameLevel;
                }

            }
            m_root = NULL;
        }

        m_Depth = 0;
    }

private:
    double FindMaxSumInternal(TreeNode<T> *curNode) const {
        if (!curNode) {
            return 0.;
        }
        // tree sub-problem
        const double leftBranchSum = FindMaxSumInternal(curNode->left) + *curNode->data;
        const double rightBranchSum = FindMaxSumInternal(curNode->right) + *curNode->data;
        return leftBranchSum > rightBranchSum ? leftBranchSum : rightBranchSum;
    }

    PyramidPath<T> FindMaxSumAndPathInternal(TreeNode<T> *curNode) const {
        if (!curNode) {
            return PyramidPath<T>();
        }
        // tree sub-problem
        const PyramidPath<T> leftBranchPath = FindMaxSumAndPathInternal(curNode->left);
        const PyramidPath<T> rightBranchPath = FindMaxSumAndPathInternal(curNode->right);;
        if (leftBranchPath.sum >= rightBranchPath.sum) {
            return PyramidPath<T>(leftBranchPath, *curNode->data);
        }
        return PyramidPath<T>(rightBranchPath, *curNode->data);
    }

    TreeNode<T> * m_root;
    size_t m_Depth;
};

// ********************************************************************************
// Test
// ********************************************************************************
using namespace Pyramid;
void TestPyramidTree()
{
    {
        const std::vector<int> input;
        assert(Pyramid::ValidInput(input) == 0);
        const std::vector<int> input1 = { 1 };
        assert(Pyramid::ValidInput(input1) == 1);
        const std::vector<int> input2 = { 1, 2, 3 };
        assert(Pyramid::ValidInput(input2) == 2);
        const std::vector<int> input3 = { 1, 2, 3, 4, 5, 6 };
        assert(Pyramid::ValidInput(input3) == 3);
        const std::vector<int> input4 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        assert(Pyramid::ValidInput(input4) == 4);
        const std::vector<int> input5 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
        assert(Pyramid::ValidInput(input5) == 5);
    }
    {
        const std::vector<int> input1 = { 1, 0 };
        assert(Pyramid::ValidInput(input1) == 0);
        const std::vector<int> input2 = { 1, 2, 3, 0 };
        assert(Pyramid::ValidInput(input2) == 0);
        const std::vector<int> input3 = { 1, 2, 3, 4, 5, 6, 0 };
        assert(Pyramid::ValidInput(input3) == 0);
        const std::vector<int> input4 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0 };
        assert(Pyramid::ValidInput(input4) == 0);
        const std::vector<int> input5 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0 };
        assert(Pyramid::ValidInput(input5) == 0);
    }

    {
        PyramidTree<int> pyramid;
        try {
            pyramid.GetDepth();
            assert(false);
        }
        catch (const PyramixException &e) {
            assert(std::string(e.what()) == "Pyramid not constructed yet");
        }
        try {
            pyramid.FindMaxSum();
            assert(false);
        }
        catch (const PyramixException &e) {
            assert(std::string(e.what()) == "Pyramid not constructed yet");
        }

        try {
            pyramid.FindMaxSumAndPath();
            assert(false);
        }
        catch (const PyramixException &e) {
            assert(std::string(e.what()) == "Pyramid not constructed yet");
        }

        try {
            pyramid.ConstructPyramid({1, 2, 3, 4});
            assert(false);
        }
        catch (const PyramixException &e) {
            assert(std::string(e.what()) == "Construction failure - invalid input");
        }

        try {
            pyramid.FindMaxSum();
            assert(false);
        }
        catch (const PyramixException &e) {
            assert(std::string(e.what()) == "Pyramid not constructed yet");
        }

        try {
            pyramid.FindMaxSumAndPath();
            assert(false);
        }
        catch (const PyramixException &e) {
            assert(std::string(e.what()) == "Pyramid not constructed yet");
        }

        pyramid.ConstructPyramid({ 1, 2, 3 });
        assert(pyramid.GetDepth() == 2);
        assert(pyramid.FindMaxSum() == 4);
        auto path = pyramid.FindMaxSumAndPath();
        assert(path.sum == 4);
        assert(path.path == std::vector<int>({1, 3}));

        pyramid.ConstructPyramid({ 1, 2, 3, 4, 5, 6 });
        assert(pyramid.GetDepth() == 3);
        assert(pyramid.FindMaxSum() == 10);
        path = pyramid.FindMaxSumAndPath();
        assert(path.sum == 10);
        assert(path.path == std::vector<int>({ 1, 3, 6 }));

        pyramid.ConstructPyramid({ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
        assert(pyramid.GetDepth() == 4);
        assert(pyramid.FindMaxSum() == 20);
        path = pyramid.FindMaxSumAndPath();
        assert(path.sum == 20);
        assert(path.path == std::vector<int>({ 1, 3, 6, 10 }));

        pyramid.ConstructPyramid({ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 });
        assert(pyramid.GetDepth() == 5);
        assert(pyramid.FindMaxSum() == 35);
        path = pyramid.FindMaxSumAndPath();
        assert(path.sum == 35);
        assert(path.path == std::vector<int>({ 1, 3, 6, 10, 15 }));
    }
}