BTS - Find the Longest Consecutive Path

1. Problem Description
This is a Google interview question for software engineers from careercup. Here is the original thread description,
"
Find longest consecutive path in a binary tree.
1. the path can be decreasing or increasing, i.e [1,2,3,4] and [4,3,2,1] are both valid
2. the path can be child-parent-child, not necessarily a parent-to-child path

similar to this question: http://www.geeksforgeeks.org/longest-consecutive-sequence-binary-tree/
- wtcupup2017 December 10, 2016 in United States | Report Duplicate | Flag 
".

2. Data Structure and Algorithm
Pseudo-code
- Generate child-to-parent consecutive depth map for each node
    * Find the longest ascending sequence if its left child < itself
    * Find the longest descending sequence if its left child > itself
    * Find the longest ascending sequence of its right child < itself
    * Find the longest descending sequence if its right child > itself
    * 0 sequence if any child is null
    * 0 sequence if any child is equal to itself
- Find the node with longest consecutive node in above map
    * Take the longer sequence if both children has same order sequence
    * Sum the sequence if two children has difference order sequence

3. C++ Implementation
Some of utility function and class can be found on (also two similar problems) my two previous posts - BTS - Find the Longest Sequence  and BTS - Find the Deepest Path.

// ********************************************************************************
// Implementation
// ********************************************************************************
template <typename T>
size_t GenerateOrderedDepthMap(TreeNode<T> *root, DepthMap<T> &depth)
{
    if (!root) {
        // special case - NULL pointer
        return 0;
    }
    // depth of this node and save into the map
    size_t leftDepth = GenerateOrderedDepthMap(root->left, depth);
    size_t rightDepth = GenerateOrderedDepthMap(root->right, depth);
    if (leftDepth != 0) {
        // ascending order
        if (*root->data > *root->left->data) {
            auto itFound = depth.find(root->left);
            assert(itFound != depth.end());
            if (itFound->second.depthOfLeft) {
                // ascending order
                if (*root->left->data > *root->left->left->data) {
                    leftDepth = itFound->second.depthOfLeft + 1;
                }
            }
            if (itFound->second.depthOfRight) {
                // ascending order
                if (*root->left->data > *root->left->right->data) {
                    if (leftDepth < itFound->second.depthOfRight + 1) {
                        leftDepth = itFound->second.depthOfRight + 1;
                    }
                }
            }
        }
        else if (*root->data < *root->left->data) {
            // descending order
            auto itFound = depth.find(root->left);
            assert(itFound != depth.end());
            if (itFound->second.depthOfLeft) {
                // descending order
                if (*root->left->data < *root->left->left->data) {
                    leftDepth = itFound->second.depthOfLeft + 1;
                }
            }
            if (itFound->second.depthOfRight) {
                // descending order
                if (*root->left->data < *root->left->right->data) {
                    if (leftDepth < itFound->second.depthOfRight + 1) {
                        leftDepth = itFound->second.depthOfRight + 1;
                    }
                }
            }
        }
        else {
            leftDepth = 0;
        }
    }
    if (rightDepth != 0) {
        // descending order
        if (*root->data > *root->right->data) {
            auto itFound = depth.find(root->right);
            assert(itFound != depth.end());
            if (itFound->second.depthOfLeft) {
                // descending order
                if (*root->right->data > *root->right->left->data) {
                    rightDepth = itFound->second.depthOfLeft + 1;
                }
            }
            if (itFound->second.depthOfRight) {
                // descending order
                if (*root->right->data > *root->right->right->data) {
                    if (rightDepth < itFound->second.depthOfRight + 1) {
                        rightDepth = itFound->second.depthOfRight + 1;
                    }
                }
            }
        }
        else if (*root->data < *root->right->data) {
            // ascending order
            auto itFound = depth.find(root->right);
            assert(itFound != depth.end());
            if (itFound->second.depthOfLeft) {
                // ascending order
                if (*root->right->data < *root->right->left->data) {
                    rightDepth = itFound->second.depthOfLeft + 1;
                }
            }
            if (itFound->second.depthOfRight) {
                // ascending order
                if (*root->right->data < *root->right->right->data) {
                    if (rightDepth < itFound->second.depthOfRight + 1) {
                        rightDepth = itFound->second.depthOfRight + 1;
                    }
                }
            }
        }
        else {
            rightDepth = 0;
        }
    }
    depth.insert(std::make_pair(root, TreeNodeDepth(leftDepth, rightDepth)));
    return 1;
}
enum WhichChildToSearch
{
    INVALID = 0,
    LEFT,
    RIGHT,
    BOTH
};
template <typename T>
std::list<TreeNode<T>*> FindTheOrderedPathFromRoot(TreeNode<T> *root,
                                                   const DepthMap<T> & dm,
                                                   const size_t depth)
{
    std::list<TreeNode<T>*> path;
    if (!root) {
        return path;
    }
    size_t tempDepth = depth;
    auto itFound = dm.find(root);
    while (itFound != dm.cend()) {
        path.push_back(itFound->first);
        if (itFound->second.depthOfLeft == tempDepth) {
            itFound = dm.find(itFound->first->left);
        }
        else if (itFound->second.depthOfRight == tempDepth) {
            itFound = dm.find(itFound->first->right);
        }
        if (tempDepth == 0) {
            break;
        }
        --tempDepth;
    }
    assert(tempDepth == 0);
    return path;
}
template <typename T>
std::list<TreeNode<T>*> FindTheLongestOrderedSeq(TreeNode<T> *root)
{
    DepthMap<T> dm;
    // generate depth map
    GenerateOrderedDepthMap(root, dm);
    auto itEnd = dm.cend();
    TreeNode<T>* nodeFound = NULL;
    size_t maxDepth = 0;
    WhichChildToSearch maxDepthSearch = INVALID;
    size_t tmp;
    WhichChildToSearch search = INVALID;
    // find the longest consecutive order
    for (auto it = dm.cbegin(); it != itEnd; ++it) {
        tmp = 0;
        if (!it->first->left) {
            tmp = it->second.depthOfRight;
            search = RIGHT;
        }
        else if (!it->first->right) {
            tmp = it->second.depthOfLeft;
            search = LEFT;
        }
        else {
            if ((*it->first->left->data < *it->first->data &&
                *it->first->data < *it->first->right->data) ||
                (*it->first->left->data > *it->first->data &&
                    *it->first->data > *it->first->right->data)) {
                tmp = it->second.depthOfLeft + it->second.depthOfRight;
                search = BOTH;
            }
            else {
                if (it->second.depthOfLeft > it->second.depthOfRight) {
                    tmp = it->second.depthOfLeft;
                    search = LEFT;
                }
                else {
                    tmp = it->second.depthOfRight;
                    search = RIGHT;
                }
            }
        }
        if (tmp > maxDepth) {
            maxDepth = tmp;
            maxDepthSearch = search;
            nodeFound = it->first;
        }
    }

    // populate the sequence
    std::list<TreeNode<T>*> path;
    if (nodeFound && maxDepthSearch) {       
        if (maxDepthSearch == LEFT || maxDepthSearch == RIGHT) {
            path = FindTheOrderedPathFromRoot(nodeFound,
                                              dm,
                                              maxDepth);
            if (maxDepthSearch == LEFT) {
                path.reverse();
            }
        }
        else {
            auto itFound = dm.find(nodeFound);
            assert(itFound != dm.cend());
            path = FindTheOrderedPathFromRoot(nodeFound->left,
                                              dm,
                                              itFound->second.depthOfLeft - 1);
            std::list<TreeNode<T>*> rightPath = FindTheOrderedPathFromRoot(
                                                    nodeFound,
                                                    dm,
                                                    itFound->second.depthOfRight);
            path.reverse();
            path.splice(path.end(), rightPath);
        }
        assert(path.size() == maxDepth + 1);
    }
    return path;
}

// ********************************************************************************
// Test
// ********************************************************************************
void TestFindTheLongestOrderedSeq()
{
    std::vector<double> input = { 1.0, 2.0, 3.0, 4.0, 5.0 };
    TreeNode<double> *root = NULL;
    //              3
    //      1               4
    //          2               5
    root = ConstructTreeOnSortedValueBFS(input);
    auto path = FindTheLongestOrderedSeq(root);
    TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0 });
    input = { 6.0, 7.0, 8.0, 9.0 };
    TreeNode<double> *subTree1 = ConstructTreeOnSortedValueDFS(input);
    input = { 10.0, 11.0, 12.0, 13.0 , 14.0 };
    TreeNode<double> *subTree2 = ConstructTreeRecursive(input);
    input = { 15.0, 16.0, 17.0, 18.0 };
    TreeNode<double> *subTree3 = ConstructTreeOnSortedValueDFS(input);
    input = { 19.0, 20.0, 21.0, 22.0 , 23.0 };
    TreeNode<double> *subTree4 = ConstructTreeRecursive(input);
    TreeNode<double> *leftestNode = FindLeftestNode(root);
    assert(leftestNode != NULL);
    leftestNode->left = subTree1;
    //              3
    //         1        4
    //      8     2        5
    //    6   9
    //  7
    path = FindTheLongestOrderedSeq(root);
    TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0 });
    TreeNode<double> *rightestNode = FindRightestNode(root);
    assert(rightestNode != NULL);
    rightestNode->left = subTree2;
    //              3
    //         1        4
    //      8     2         5
    //    6   9          12
    //  7            10      13
    //                  11      14
    path = FindTheLongestOrderedSeq(root);
    TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });
    TreeNode<double> *firstLeftRighestNode = FindRightestNode(root->left);
    assert(firstLeftRighestNode != NULL);
    firstLeftRighestNode->right = subTree3;
    //                    3
    //         1              4
    //      8     2                   5
    //    6   9     17          12
    //  7         15   18   10       13
    //               16            11      14
    path = FindTheLongestOrderedSeq(root);
    TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });
    TreeNode<double> *firstRightLeftestNodeOfS2 = FindRightestNode(subTree2->left);
    assert(firstRightLeftestNodeOfS2 != NULL);
    firstRightLeftestNodeOfS2->left = subTree4;
    //                    3
    //         1              4
    //      8     2                   5
    //    6   9     17          12
    //  7         15   18   10       13
    //               16           11      14
    //                         21
    //                    19     22
    //                       20       23
    path = FindTheLongestOrderedSeq(root);
    TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });
    TreeNode<double> *rightestNodeOfS2 = FindRightestNode(subTree2);
    assert(rightestNodeOfS2 != NULL);
    for (size_t i = 0; i < 8; ++i) {
        rightestNodeOfS2->right = new TreeNode<double>(100.0 + i);
        rightestNodeOfS2 = rightestNodeOfS2->right;
    }
    //                    3
    //         1              4
    //      8     2                   5
    //    6   9     17          12
    //  7         15   18   10     13
    //              16           11      14
    //                        21              100
    //                    19     22            101
    //                      20       23          102
    //                                                  103
    //                                                     104
    //                                                        105
    //                                                          106
    //                                                            107
    // clean up
    path = FindTheLongestOrderedSeq(root);
    TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0, 100.0,
        101.0, 102.0, 103.0, 104.0, 105.0, 106.0, 107.0});
    // clean up
    DeleteTree_TD(&root);
}

DSA - Minimal Swaps to Reach Desired Position

1. Problem Description
This is a Google interview question for software engineer from careercup. Here is the original thread, "
An interesting question asked in Google’s phone interview : suppose a row of parking lot with n spots, one of them is empty and n-1 spots are occupied with cars. Only one operation is allowed: move one car from its position to the empty spot. Given a initial order of cars and a final order, output steps needed to convert initial order to final oder with that operation.

Follow up: Minimize steps needed.

ex:

{1 2 3 -1 4 5}
move car 1 to empty spot(denoted as -1) will make it {-1,2,3,1,4,5}
push 1 to the output list because you move car 1 to the empty spot

suppose you have a initial order {1 2 3 -1 4 5} and a final order {5,1,-1,3,2,4}, you need to transfer {1 2 3 -1 4 5} to {5,1,-1,3,2,4}, push each car moved into a output list.
- wtcupup2017 December 28, 2016 in United States | Report Duplicate | Flag  ".

2. Data Structure and Algorithm
Let's start from the simple cases. "-1" represents the empty space and "A, B, C, ......" represents the location of cars.
    - One car
        Desired position:
            (-1, A)
        Initial position:
            1. (A, -1) - 1 swap
    - Two cars
        Desired position:
            (-1, A, B)
        Initial position:
            1. (A, B, -1)
                - all 3 out of position, then 2 swaps
            2. (B, A, -1)
                - A is at the same position, then become "One car" case and need 1 swap
            3. (A, -1, B)
                - B is at the same position, then become "One car" case and need 1 swap
            4. (B, -1, A)
                - all 3 out of position, then 2 swaps
            5. (-1, B, A)
                - -1 is at the same position
                - swapping -1 with B becomes Case 4
                - 1 + 2 = 3 swaps
    - Three cars
        Desired position:
            (-1, A, B, C)
        Initial position:
            1. (A, B, C, -1)
                - all 4 out of position - 3 swaps
            2. (A, C, B, -1)
                - all 4 out of position - 3 swaps
            3. (B, A, C, -1)
                - A is at the same position and become "Two cars" case - 2 swaps
            4. (B, C, A, -1)
                - all 4 out of position - 3 swaps

            5. (C, A, B, -1)
                - Both A and B are at the same position, become "One car" case - 1 swap
            6. (C, B, A, -1)
                - all 4 out of position - 3 swaps

            7. (A, B, -1, C)
                - C is at the same position and become "Two cars" case - 2 swap
            8. (A, C, -1, B)
                - all 4 out of position - 3 swaps

            9. (B, A, -1, C)
                - A and C are at the same position and become "One car" case - 1 swap
            10. (B, C, -1, A)
                - all 4 out of position - 3 swaps

            11. (C, A, -1, B)
                - A is at the same position and become "Two cars" case - 2 swaps
            12. (C, B, -1, A)
                - all 4 out of position - 3 swaps

            13. (A, -1, B, C)
                - B and C are at the same position and become "One car" case - 1 swap
            14. (A, -1, C, B)
                - all 4 out of position - 3 swaps

            15. (B, -1, A, C)
                - C is at the same position and become "Two cars" case - 2 swap
            16. (B, -1, C, A)
                - all 4 out of position - 3 swaps

            17. (C, -1, A, B)
                - all 4 out of position - 3 swaps

            18. (C, -1, B, A)
                - B is a the same position then become "Two cars" case - 2 swaps
            19. (-1, A, C, B)
                - A is at the same position, then becomes "Two car" case 5
                - 3 swaps
            20. (-1, B, A, C)
                - C is at the same position, then becomes "Two car" case 5
                - 3 swaps
            21. (-1, B, C, A)
                - Swapping -1 and B becomes case 16
                - 1 + 3 = 4 swaps
            22. (-1, C, A, B)
                - Swapping -1 and C becomes case 17
                - 1 + 3 = 4 swaps
            23. (-1, C, B, A)
                - B is at the same position, then becomes "Two car" case 5
                - 3 swaps

Here is the conclusion to make:
1.If cars and empty space are not at the same position, then N cars needs N swaps to reach the desired position.
2. If empty space is at the same position but all cars are not, then N cars needs N+1 swaps to reach the desired position.
3. If there are cars at the same position, then remove them and reduce N to M. And take the case as of in 1 or 2.

Pseudo-code:
1. Remove all the cars at the same position between initial position and desired position
2. N as the all cars and M as after removing the cars at the same positions
    - return M if -1 is not at the same position
    - return M + 1 if -1 is at the same position.