CareerCup

- 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

Details: //cpluspluslearning-petert.blogspot.co.uk/2017/01/bts-find-longest-consecutive-path_13.html

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);
}

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

Details: cpluspluslearning-petert.blogspot.co.uk/2017/01/dsa-minimum-swap-to-reach-desired.html

There is a definite answer to this question. Because in the worst case it needs 1000 pigs to find out the poisonous bucket and the best case is 1. Therefore instead of looking of a definite answer this question is to find out the minimum of expectation of how many pigs needed to find the poisonous bucket.

A solution is proposed on this, cpluspluslearning-petert.blogspot.co.uk/2016/12/identify-posionous-bucket-with-minimux.html.

And further discuss the general cases and a solution is provided - the total number of buckets and how many attempts are allowed.

The idea is to keep divide the large range into smaller range until the range is not greater than the given mem. Then go through each smaller ranges to find out missing number. Combine the missing numbers of all ranges to form the result. Details: cpluspluslearning-petert.blogspot.co.uk/2016/10/data-structure-and-algorithm-detect.html

A loop and recursive solutions are implemented. And the test is based on the range of 1 million numbers.

Test

void Test_DetectMissingNumbers()
{
    NumberGenerator ns(1000000, 100);
    NumberGenerator::MissingNumberCollection results; 

    results = DetectMissingNumber(ns, 10000);
    assert(results == ns.GetMissingCollection());

    results = DetectMissingNumber(ns, 100000);
    assert(results == ns.GetMissingCollection());

    results = DetectMissingNumber(ns, 1000000);
    assert(results == ns.GetMissingCollection());
}

void Test_DetectMissingNumbers_R()
{
    NumberGenerator ns(1000000, 100);
    NumberGenerator::MissingNumberCollection results; 

    results = DetectMissingNumber_R(ns, 10000);
    assert(results == ns.GetMissingCollection());

    results = DetectMissingNumber_R(ns, 100000);
    assert(results == ns.GetMissingCollection());

    results = DetectMissingNumber_R(ns, 1000000);
    assert(results == ns.GetMissingCollection());
}

void Test_DetectMissingNumbers_Div()
{
    NumberGenerator ns(1000000, 100);
    NumberGenerator::MissingNumberCollection results; 

    results = DetectMissingNumber_Div(ns, 10000);
    assert(results == ns.GetMissingCollection());

    results = DetectMissingNumber_Div(ns, 100000);
    assert(results == ns.GetMissingCollection());

    results = DetectMissingNumber_Div(ns, 1000000);
    assert(results == ns.GetMissingCollection());
}

A solution based on Trie data structure is implemented in C++ and Python.
C++: cpluspluslearning-petert.blogspot.co.uk/2016/09/data-structure-and-algorithm-detect.html
Python: pythonlearning-petert.blogspot.co.uk/2016/09/data-structure-and-algorithm-detect.html

It is to take node-base graph data structure. Take a random vertex as root and populate the traffic of all its children node. At this moment only the root has all children node's traffic populated. The rest nodes have only traffic of parent node not populate. Then the second round is to populate the parent node's traffic. Afterwords find maximal traffic of each node, which is the what we are looking for.

Details: cpluspluslearning-petert.blogspot.co.uk/2016/09/data-structure-and-algorithm-find.html

C++ and Python implementations are provided.

# python unit test
import unittest
from gNodeHelper import gNode
from gNodeHelper import gNodeHelper

class Test_GenerateMaxTraffic(unittest.TestCase):
    def test_A(self):
        node1 = gNode(1, 1)
        node2 = gNode(2, 2)
        node3 = gNode(3, 3)
        node4 = gNode(4, 4)
        node5 = gNode(5, 5)

        node1.AppendNeighbour(node5)
        node5.AppendNeighbours((node1, node2, node3, node4))
        node2.AppendNeighbour(node5)
        node3.AppendNeighbour(node5)
        node4.AppendNeighbour(node5)

        gNodeHelper.GenerateMaxTraffic(node1)

        self.assertEqual(node1.maxTraffic, 14)
        self.assertEqual(node2.maxTraffic, 13)
        self.assertEqual(node3.maxTraffic, 12)
        self.assertEqual(node4.maxTraffic, 11)
        self.assertEqual(node5.maxTraffic, 4)

    def test_B(self):
        node1 = gNode(1, 1)
        node2 = gNode(2, 2)
        node3 = gNode(3, 3)
        node4 = gNode(4, 4)
        node5 = gNode(5, 5)

        node1.AppendNeighbour(node5)
        node5.AppendNeighbours((node1, node2, node3, node4))
        node2.AppendNeighbour(node5)
        node3.AppendNeighbour(node5)
        node4.AppendNeighbour(node5)

        gNodeHelper.GenerateMaxTraffic(node5)

        self.assertEqual(node1.maxTraffic, 14)
        self.assertEqual(node2.maxTraffic, 13)
        self.assertEqual(node3.maxTraffic, 12)
        self.assertEqual(node4.maxTraffic, 11)
        self.assertEqual(node5.maxTraffic, 4)

    def test_C(self):
        node1 = gNode(1, 1)
        node2 = gNode(2, 2)
        node3 = gNode(3, 3)
        node4 = gNode(4, 4)
        node5 = gNode(5, 5)
        node7 = gNode(7, 7)
        node8 = gNode(8, 8)
        node15 = gNode(15, 15)
        node38 = gNode(38, 38)

        node1.AppendNeighbour(node5)
        node5.AppendNeighbours((node1, node2, node3, node4))
        node2.AppendNeighbours((node5, node7, node15))
        node3.AppendNeighbour(node5)
        node4.AppendNeighbour(node5)
        node7.AppendNeighbours((node2, node8))
        node8.AppendNeighbours((node7, node38))
        node15.AppendNeighbour(node2)
        node38.AppendNeighbour(node8)

        gNodeHelper.GenerateMaxTraffic(node1)

        self.assertEqual(node1.maxTraffic, 82)
        self.assertEqual(node2.maxTraffic, 53)
        self.assertEqual(node3.maxTraffic, 80)
        self.assertEqual(node4.maxTraffic, 79)
        self.assertEqual(node5.maxTraffic, 70)
        self.assertEqual(node7.maxTraffic, 46)
        self.assertEqual(node8.maxTraffic, 38)
        self.assertEqual(node15.maxTraffic, 68)
        self.assertEqual(node38.maxTraffic, 45)

    def test_D(self):
        node1 = gNode(1, 1)
        node2 = gNode(2, 2)
        node3 = gNode(3, 3)
        node4 = gNode(4, 4)
        node5 = gNode(5, 5)
        node7 = gNode(7, 7)
        node8 = gNode(8, 8)
        node15 = gNode(15, 15)
        node38 = gNode(38, 38)

        node1.AppendNeighbour(node5)
        node5.AppendNeighbours((node1, node2, node3, node4))
        node2.AppendNeighbours((node5, node7, node15))
        node3.AppendNeighbour(node5)
        node4.AppendNeighbour(node5)
        node7.AppendNeighbours((node2, node8))
        node8.AppendNeighbours((node7, node38))
        node15.AppendNeighbour(node2)
        node38.AppendNeighbour(node8)

        gNodeHelper.GenerateMaxTraffic(node5)

        self.assertEqual(node1.maxTraffic, 82)
        self.assertEqual(node2.maxTraffic, 53)
        self.assertEqual(node3.maxTraffic, 80)
        self.assertEqual(node4.maxTraffic, 79)
        self.assertEqual(node5.maxTraffic, 70)
        self.assertEqual(node7.maxTraffic, 46)
        self.assertEqual(node8.maxTraffic, 38)
        self.assertEqual(node15.maxTraffic, 68)
        self.assertEqual(node38.maxTraffic, 45)

if __name__ == '__main__':
    unittest.main()

// C++ test
void Test_GenerateMaxTraffic()
{
    {
        gNode node1(1, 1);
        gNode node2(2, 2);
        gNode node3(3, 3);
        gNode node4(4, 4);
        gNode node5(5, 5);

        node1.AppendNeighbour(&node5);
        node2.AppendNeighbour(&node5);
        node3.AppendNeighbour(&node5);
        node4.AppendNeighbour(&node5);
        node5.AppendNeighbours({&node1, &node2, &node3, &node4});

        GenerateMaxTraffic(&node1);
  
        assert(node1.maxTraffic == 14);
        assert(node2.maxTraffic == 13);
        assert(node3.maxTraffic == 12);
        assert(node4.maxTraffic == 11);
        assert(node5.maxTraffic == 4);
    }

    {
        gNode node1(1, 1);
        gNode node2(2, 2);
        gNode node3(3, 3);
        gNode node4(4, 4);
        gNode node5(5, 5);
        gNode node7(7, 7);
        gNode node8(8, 8);
        gNode node15(15, 15);
        gNode node38(38, 38);
  
        node1.AppendNeighbour(&node5);
        node2.AppendNeighbours({ &node5, &node7, &node15 });
        node3.AppendNeighbour(&node5);
        node4.AppendNeighbour(&node5);
        node5.AppendNeighbours({ &node1, &node2, &node3, &node4 });
        node7.AppendNeighbours({ &node2, &node8 });
        node8.AppendNeighbours({ &node7, &node38 });
        node15.AppendNeighbour(&node2);
        node38.AppendNeighbour(&node8);

        GenerateMaxTraffic(&node1);

        assert(node1.maxTraffic == 82);
        assert(node2.maxTraffic == 53);
        assert(node3.maxTraffic == 80);
        assert(node4.maxTraffic == 79);
        assert(node5.maxTraffic == 70);
        assert(node7.maxTraffic == 46);
        assert(node8.maxTraffic == 38);
        assert(node15.maxTraffic == 68);
        assert(node38.maxTraffic == 45);
    }

    {
        gNode node1(1, 1);
        gNode node2(2, 2);
        gNode node3(3, 3);
        gNode node4(4, 4);
        gNode node5(5, 5);
        gNode node7(7, 7);
        gNode node8(8, 8);
        gNode node15(15, 15);
        gNode node38(38, 38);

        node1.AppendNeighbour(&node5);
        node2.AppendNeighbours({ &node5, &node7, &node15 });
        node3.AppendNeighbour(&node5);
        node4.AppendNeighbour(&node5);
        node5.AppendNeighbours({ &node1, &node2, &node3, &node4 });
        node7.AppendNeighbours({ &node2, &node8 });
        node8.AppendNeighbours({ &node7, &node38 });
        node15.AppendNeighbour(&node2);
        node38.AppendNeighbour(&node8);

        GenerateMaxTraffic(&node5);

        assert(node1.maxTraffic == 82);
        assert(node2.maxTraffic == 53);
        assert(node3.maxTraffic == 80);
        assert(node4.maxTraffic == 79);
        assert(node5.maxTraffic == 70);
        assert(node7.maxTraffic == 46);
        assert(node8.maxTraffic == 38);
        assert(node15.maxTraffic == 68);
        assert(node38.maxTraffic == 45);
    }
}

The idea is to merge sensors crossed with other into sensor ranges. Keep track of the crosses with rectangle boundaries of sensor rangers. If there does not exist any sensor range with valid left and right cross, then there is a horizontal path. Otherwise not path. For vertical path, checking the top and bottom cross.
If the path exists, then work out the first pair of complement range of sensors range's cross with rectangle boundaries. Return the mid point of the very first ranges of left and right ranges for horizontal path. Return the mid point of the very first ranges of top and bottom ranges for a vertical path.

Details please see: cpluspluslearning-petert.blogspot.co.uk/2016/09/data-structure-and-algorithm-find-path.html
Both Python and C++ implementations are provided.

A O(NlogN) solution is constructed on cpluspluslearning-petert.blogspot.co.uk/2016/08/data-structure-and-algorithm-finx-sub.html

Test

void Test_FindSubArrayWithSumInRange()
{
    PairResultVect result;
    {
        const std::vector<double> input;
        result = FindSubArrayWithSumInRange(input, 0, 1);
        assert(result.empty() == true);
    }
    {
        const std::vector<double> input = { 1.0, 2.0, 3.0, 4.0,
                                            5.0, 6.0, 7.0, 8.0,
                                            9.0, 10.0 };
        result = FindSubArrayWithSumInRange(input, 20, 15);
        assert(result.empty() == true);
        result = FindSubArrayWithSumInRange(input, -10, 0);
        assert(result.empty() == true);
        result = FindSubArrayWithSumInRange(input, 15.0, 20.0);
        assert(result.size() == 8);
    }
    {
        const std::vector<double> input = {-1, 1, -1, 1, -1, 1};
        result = FindSubArrayWithSumInRange(input, -1, 1);
        assert(result.size() == 21);
    }
}

A dynamic solution is implemented.
Given position C1, C2, ..., Cn, which has a coin on it at position (Xi, Yi).
- f(C1, ..., Cn) = max(1 + f(C1, ..., Ci-1, Ci+1, Cn) ), where i with range of [1, n]

Details: cpluspluslearning-petert.blogspot.co.uk/2016/07/dynamic-programming-pick-maximal-coins.html

Test

void TestPickMaximalCoins()
{
    {
        const std::vector<Position> coins;
        assert(PickMaximalCoins_R(coins) == 0);
    }
     {
        const std::vector<Position> coins = { { 5, 5 }, { 1.5, 3.5 }, { 2, 2 }, { 2.0, 4.0 }, 
                                { 4, 4 }, { 5.0, 2.0 }, { 3, 3 }, { 4.0, 1.0 }, { 1, 1 }};
        assert(PickMaximalCoins_R(coins) == 5);
    }
     {
        const std::vector<Position> coins = {
            { 6.1, 2.1 }, { 2.2, 6.2 }, { 5.2, 5.2 }, { 6.2, 2.2 },
            { 2.3, 6.3 }, { 5.3, 5.3 }, { 6.3, 2.3 }, { 5.4, 5.4 },
            { 1.0, 1.0 }, { 2.0, 6.0 }, { 5.0, 5.0 }, { 6.0, 2.0 },
            { 2.1, 6.1 }, { 5.1, 5.1 } };
        assert(PickMaximalCoins_R(coins) == 6);
    }
     {
        const std::vector<Position> coins = {
            { 6.1, 2.1 }, { 2.2, 6.2 }, { 5.2, 5.2 }, { 6.2, 2.2 },
            { 2.3, 6.3 }, { 5.3, 5.3 }, { 6.3, 2.3 }, { 4.0, 5.3 },
            { 5.4, 5.4 }, { 1.0, 1.0 }, { 2.0, 6.0 }, { 5.0, 5.0 },
            { 6.0, 2.0 }, { 2.1, 6.1 }, { 5.1, 5.1 }, { 5.3, 4.0 } };
        assert(PickMaximalCoins_R(coins) == 6);
    }
}

A few solutions are proposed on cpluspluslearning-petert.blogspot.co.uk/2016/06/c-restrict-creation-of-objects.html.
The focus is on the process of creating and deleting objects.

A solution based on graph and breadth-first traverse is present here: cpluspluslearning-petert.blogspot.co.uk/2016/06/data-structure-and-algorithm-find.html

Test code

void TestGetDistances()
{
    {
        const std::vector<std::vector<MuseumItem>> museum =
        {{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN},
         {MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN},
         {MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::OPEN},
         {MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN},
         {MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN} };

        LocAndDistMap distances = GetDistances(museum);
        assert(distances.find(std::make_tuple(0, 0))->second == 4);
        assert(distances.find(std::make_tuple(1, 0))->second == 3);
        assert(distances.find(std::make_tuple(2, 0))->second == 2);
        assert(distances.find(std::make_tuple(3, 0))->second == 3);
        assert(distances.find(std::make_tuple(4, 0))->second == 4);
        assert(distances.find(std::make_tuple(0, 1))->second == 3);
        assert(distances.find(std::make_tuple(1, 1))->second == 2);
        assert(distances.find(std::make_tuple(2, 1))->second == 1);
        assert(distances.find(std::make_tuple(3, 1))->second == 2);
        assert(distances.find(std::make_tuple(4, 1))->second == 3);
        assert(distances.find(std::make_tuple(0, 2))->second == 2);
        assert(distances.find(std::make_tuple(1, 2))->second == 1);
        assert(distances.find(std::make_tuple(2, 2)) == distances.end());
        assert(distances.find(std::make_tuple(3, 2))->second == 1);
        assert(distances.find(std::make_tuple(4, 2))->second == 2);
        assert(distances.find(std::make_tuple(0, 3))->second == 3);
        assert(distances.find(std::make_tuple(1, 3))->second == 2);
        assert(distances.find(std::make_tuple(2, 3))->second == 1);
        assert(distances.find(std::make_tuple(3, 3))->second == 2);
        assert(distances.find(std::make_tuple(4, 3))->second == 3);
        assert(distances.find(std::make_tuple(0, 4))->second == 4);
        assert(distances.find(std::make_tuple(1, 4))->second == 3);
        assert(distances.find(std::make_tuple(2, 4))->second == 2);
        assert(distances.find(std::make_tuple(3, 4))->second == 3);
        assert(distances.find(std::make_tuple(4, 4))->second == 4);
    }

    {
        const std::vector<std::vector<MuseumItem>> museum =
        { { MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN },
        { MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN },
        { MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::OPEN },
        { MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN },
        { MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN } };

        LocAndDistMap distances = GetDistances(museum);
        assert(distances.find(std::make_tuple(0, 0)) == distances.end());
        assert(distances.find(std::make_tuple(1, 0)) == distances.end());
        assert(distances.find(std::make_tuple(2, 0)) == distances.end());
        assert(distances.find(std::make_tuple(3, 0)) == distances.end());
        assert(distances.find(std::make_tuple(4, 0)) == distances.end());
        assert(distances.find(std::make_tuple(0, 1)) == distances.end());
        assert(distances.find(std::make_tuple(1, 1)) == distances.end());
        assert(distances.find(std::make_tuple(2, 1)) == distances.end());
        assert(distances.find(std::make_tuple(3, 1)) == distances.end());
        assert(distances.find(std::make_tuple(4, 1)) == distances.end());
        assert(distances.find(std::make_tuple(0, 2))->second == 2);
        assert(distances.find(std::make_tuple(1, 2))->second == 1);
        assert(distances.find(std::make_tuple(2, 2)) == distances.end());
        assert(distances.find(std::make_tuple(3, 2))->second == 1);
        assert(distances.find(std::make_tuple(4, 2))->second == 2);
        assert(distances.find(std::make_tuple(0, 3))->second == 3);
        assert(distances.find(std::make_tuple(1, 3))->second == 2);
        assert(distances.find(std::make_tuple(2, 3))->second == 1);
        assert(distances.find(std::make_tuple(3, 3))->second == 2);
        assert(distances.find(std::make_tuple(4, 3))->second == 3);
        assert(distances.find(std::make_tuple(0, 4))->second == 4);
        assert(distances.find(std::make_tuple(1, 4))->second == 3);
        assert(distances.find(std::make_tuple(2, 4))->second == 2);
        assert(distances.find(std::make_tuple(3, 4))->second == 3);
        assert(distances.find(std::make_tuple(4, 4))->second == 4);
    }

    {
        const std::vector<std::vector<MuseumItem>> museum =
        { { MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN },
        { MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN },
        { MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::GUARD, MuseumItem::OPEN },
        { MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN },
        { MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN } };

        LocAndDistMap distances = GetDistances(museum);
        assert(distances.find(std::make_tuple(0, 0)) == distances.end());
        assert(distances.find(std::make_tuple(1, 0))->second == 1);
        assert(distances.find(std::make_tuple(2, 0))->second == 1);
        assert(distances.find(std::make_tuple(3, 0)) == distances.end());
        assert(distances.find(std::make_tuple(4, 0))->second == 1);
        assert(distances.find(std::make_tuple(0, 1))->second == 1);
        assert(distances.find(std::make_tuple(1, 1))->second == 2);
        assert(distances.find(std::make_tuple(2, 1))->second == 2);
        assert(distances.find(std::make_tuple(3, 1))->second == 1);
        assert(distances.find(std::make_tuple(4, 1))->second == 2);
        assert(distances.find(std::make_tuple(0, 2)) == distances.end());
        assert(distances.find(std::make_tuple(1, 2)) == distances.end());
        assert(distances.find(std::make_tuple(2, 2))->second == 1);
        assert(distances.find(std::make_tuple(3, 2)) == distances.end());
        assert(distances.find(std::make_tuple(4, 2)) == distances.end());
        assert(distances.find(std::make_tuple(0, 3))->second == 2);
        assert(distances.find(std::make_tuple(1, 3))->second == 1);
        assert(distances.find(std::make_tuple(2, 3)) == distances.end());
        assert(distances.find(std::make_tuple(3, 3))->second == 1);
        assert(distances.find(std::make_tuple(4, 3))->second == 2);
        assert(distances.find(std::make_tuple(0, 4))->second == 3);
        assert(distances.find(std::make_tuple(1, 4))->second == 2);
        assert(distances.find(std::make_tuple(2, 4))->second == 1);
        assert(distances.find(std::make_tuple(3, 4))->second == 2);
        assert(distances.find(std::make_tuple(4, 4))->second == 3);
    }
}

As some of contributors pointed out, the is a typical dynamic problem. The sub-problem is easy to spot as well. The key here is it might have 0, 1 or 2 sub-problems depending on its current value and its subsequent value. For instance string starting with 0, "0......", does not have any sub-problem, "28......" has 1 sub-problem and string "12......" has 2 sub-problems.
Details: cpluspluslearning-petert.blogspot.co.uk/2016/06/dynamic-programming-string-decoder.html

Test

void TestDecoder()
{
    assert(StringDecoder("134a457") < 0);
    assert(StringDecoder("100") < 0);
    assert(StringDecoder("12") == 2);
    assert(StringDecoder("123") == 3);
    assert(StringDecoder("0123456789") < 0);
    assert(StringDecoder("10123") == 3);
    assert(StringDecoder("345") == 1);
    assert(StringDecoder("1123") == 5);
    assert(StringDecoder("5123") == 3);
}

It is a typical dynamic programming question. Use the P and Q together as the key and its minimal case as the value to cache the result. Details: cpluspluslearning-petert.blogspot.co.uk/2016/05/dynamic-programming-min-cost-of.html

Test

#include <cassert>
void TestPrisionCellQ()
{
    const std::vector<size_t> cells = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    {
        const std::vector<size_t> releases = { 1 };
        assert(MinCostOfReleasingCells(cells, releases) == 8);
    }
    {
        const std::vector<size_t> releases = { 8 };
        assert(MinCostOfReleasingCells(cells, releases) == 8);
    }
    {
        const std::vector<size_t> releases = { 1, 6 };
        assert(MinCostOfReleasingCells(cells, releases) == 13);
    }
    {
        const std::vector<size_t> releases = { 1, 3 };
        assert(MinCostOfReleasingCells(cells, releases) == 10);
    }
    {
        const std::vector<size_t> releases = { 1, 3, 8 };
        assert(MinCostOfReleasingCells(cells, releases) == 14);
    }
    {
        const std::vector<size_t> releases = { 1, 3, 5 };
        assert(MinCostOfReleasingCells(cells, releases) == 14);
    }
    {
        const std::vector<size_t> releases = { 3, 4, 5 };
        assert(MinCostOfReleasingCells(cells, releases) == 12);
    }
    {
        const std::vector<size_t> releases = { 3, 4, 5, 8 };
        assert(MinCostOfReleasingCells(cells, releases) == 14);
    }
    {
        const std::vector<size_t> releases = { 0, 3, 4, 5, 8 };
        assert(MinCostOfReleasingCells(cells, releases) == 16);
    }
}

A solution to use Trie to take the character table and a hash map to take its value has been implemented here: cpluspluslearning-petert.blogspot.co.uk/2016/05/compare-exotic-string.html.

Test

void TestExoticStringComparator()
{
    {
        // non-exotic testing
        const std::vector<ExoticChar> charTable = { 
            { "a", 'a' },
            { "b", 'b' },
            { "c", 'c' },
            { "d", 'd' },
            { "e", 'e' },
            { "f", 'f' },
            { "g", 'g' },
            { "h", 'h' },
            { "i", 'i' },
            { "j", 'j' },
            { "k", 'k' },
            { "l", 'l' },
            { "m", 'm' },
            { "n", 'n' },
            { "o", 'o' },
            { "p", 'p' },
            { "q", 'q' },
            { "r", 'r' },
            { "s", 's' },
            { "t", 't' },
            { "u", 'u' },
            { "v", 'v' },
            { "w", 'w' },
            { "x", 'x' },
            { "y", 'y' },
            { "z", 'z' } };
            
        ExoticStringComparator esc(charTable);
        assert(esc.CompareExoticString("lkasdfajsd", "lkasdfajsd") == 0);
        assert(esc.CompareExoticString("lkasdfajsd", "lkasdfahsd") > 0);
        assert(esc.CompareExoticString("lkasdfajsd", "lkasdfaxsd") < 0);
        assert(esc.CompareExoticString("lkasdfajsdz", "lkasdfajsd") > 0);
        assert(esc.CompareExoticString("lkasdfajsd", "lkasdfajsdz") < 0);
    
    }

    {
        // exotic testing
        const std::vector<ExoticChar> charTable = {
            { "a", 'a' },
            { "b", 'b' },
            { "c", 'c' },
            { "d", 'd' },
            { "e", 'e' },
            { "f", 'f' },
            { "g", 'g' },
            { "h", 'h' },
            { "i", 'i' },
            { "j", 'j' },
            { "k", 'k' },
            { "l", 'l' },
            { "m", 'm' },
            { "n", 'n' },
            { "o", 'o' },
            { "p", 'p' },
            { "q", 'q' },
            { "r", 'r' },
            { "s", 's' },
            { "t", 't' },
            { "u", 'u' },
            { "v", 'v' },
            { "w", 'w' },
            { "x", 'x' },
            { "y", 'y' },
            { "z", 'z' },
            { "ae", 'z' + 1 },
            { "oe", 'z' + 2 },
            { "ue", 'a' - 1 },
            { "sch", 'a' - 2 }, };

        ExoticStringComparator esc(charTable);
        assert(esc.CompareExoticString("ae", "oe") < 0);
        assert(esc.CompareExoticString("ae", "ue") > 0);
        assert(esc.CompareExoticString("oe", "sch") > 0);
        assert(esc.CompareExoticString("oe", "ue") > 0);
        assert(esc.CompareExoticString("lkasdfaesd", "lkasdfajsdz") > 0);
        assert(esc.CompareExoticString("lkasdfschaesd", "lkasdfaajsdz") < 0);
        assert(esc.CompareExoticString("lkasdfschaesd", "lkasdfschoesd") < 0);

    }
}

Two approaches are proposed. The basic idea is similar as merging sorted list. Here we have X sorted list.
Details: cpluspluslearning-petert.blogspot.co.uk/2016/04/merge-x-way-sorted-list.html
Test

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}));
    }
}

A dynamic solution plus caching technique is implemented. In the best case it has O((n-m)^2) computation complexity. And it has O(n*m) space complexity. Details: cpluspluslearning-petert.blogspot.co.uk/2016/03/dynamic-programming-find-difference-of.html

Test

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);
    }

}

Use binary search algorithm and keep tracking the lower bound and upper bound as goes deep into the tree. If found in the tree it works just like binary search. Otherwise hitting the bottom of the tree, compare its distance with the lower bound and upper bound. Pick the bound with smaller distance. Details: cpluspluslearning-petert.blogspot.co.uk/2016/03/bst-find-closest-value.html

Two implementations: recursive and non-recursive.

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);
}

Instead of using tree data structure a simple array works as well. The number of each level and its children node is deterministic as long as the pyramid is given. Finding the path with maximal path can be solved with sub-problem of its children node as well. Details: cpluspluslearning-petert.blogspot.co.uk/2016/03/find-path-with-maximal-sum-in-pyramid-ii.html

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 }));
    }
}

Use tree data structure for pyramid. Finding the path with the maximal sum is relatively easy because its sub-problem can be found as its sum to itself plus its left and right children. Details: cpluspluslearning-petert.blogspot.co.uk/2016/03/bts-find-path-with-maximal-sum-in.html

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 }));
    }
}

Just need to flip K continuous zeros in the array. Assume there are N zero in total. Then there are N-K cases. Here is the detail: cpluspluslearning-petert.blogspot.co.uk/2016/02/find-longest-continuous-streak-of-one.html

Test

#include <cassert>
void Test()
{
    {
        const std::vector<char> arr;
        assert(FindLongestContinuousStreakAfterKFlips(arr, 0) == 0);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 10) == 0);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 100) == 0);
    }
    {
        const std::vector<char> arr = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        assert(FindLongestContinuousStreakAfterKFlips(arr, 0) == 0);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 1) == 1);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 2) == 2);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 3) == 3);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 4) == 4);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 5) == 5);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 6) == 6);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 7) == 7);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 8) == 8);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 9) == 9);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 10) == 10);
    }
    {
        const std::vector<char> arr = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
        assert(FindLongestContinuousStreakAfterKFlips(arr, 0) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 1) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 2) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 3) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 4) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 5) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 6) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 7) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 8) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 9) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 10) == 10);
    }
    {
        const std::vector<char> arr = { 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 };
        assert(FindLongestContinuousStreakAfterKFlips(arr, 0) == 4);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 1) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 2) == 14);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 3) == 17);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 4) == 19);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 5) == 19);
    }
    {
        const std::vector<char> arr = { 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1};
        assert(FindLongestContinuousStreakAfterKFlips(arr, 0) == 3);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 1) == 6);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 2) == 8);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 3) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 4) == 12);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 5) == 14);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 6) == 16);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 7) == 16);
    }
}

Crafted a linear solution (to size of tree). The idea is to calculate hash for each node that includes all the information of its sub-tree. Then compare those nodes with same hash code. Details: cpluspluslearning-petert.blogspot.co.uk/2016/01/dynamic-programming-find-if-given-tree_69.html

Test

void TestFindDuplicateSubTree2()
{
    {
        TreeNode<int>* root = nullptr;
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
    }

    {
        const std::vector<int> testInput = { 1, 2 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root);
        auto rightestNode = FindRightestNode(root);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 1);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root);
        auto rightestNode = FindRightestNode(root);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 1);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == true);
        assert(entry1 != nullptr);
        assert(entry2 != nullptr);
        assert(CheckTwoTreesWithSameValues(entry1, subTree1));
        assert(CheckTwoTreesWithSameValues(entry2, subTree2));
        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->left);
        auto rightestNode = FindRightestNode(root->left);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 1);
        assert(*rightestNode->data == 4);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == true);
        assert(entry1 != nullptr);
        assert(entry2 != nullptr);
        assert(CheckTwoTreesWithSameValues(entry1, subTree1));
        assert(CheckTwoTreesWithSameValues(entry2, subTree2));
        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);
        auto rightestNode = FindRightestNode(root->right);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 6);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == true);
        assert(entry1 != nullptr);
        assert(entry2 != nullptr);
        assert(CheckTwoTreesWithSameValues(entry1, subTree1));
        assert(CheckTwoTreesWithSameValues(entry2, subTree2));
        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1 = nullptr;
        TreeNode<int>* entry2 = nullptr;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput1 = { 100, 101, 102 };
        const std::vector<int> subTreeInput2 = { 102, 101, 100 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput1);
        auto subTree2 = ConstructTreeRecursive(subTreeInput2);
        assert(GetTreeSize_R(subTree1) == subTreeInput1.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput2.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);
        auto rightestNode = FindRightestNode(root->right);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 6);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
        assert(entry1 == nullptr);
        assert(entry2 == nullptr);
        
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1 = nullptr;
        TreeNode<int>* entry2 = nullptr;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        TreeNode<int>* subTree1 = new TreeNode<int>(1000);
        subTree1->left = new TreeNode<int>(1001);
        subTree1->left->left = new TreeNode<int>(1002);
        TreeNode<int>* subTree2 = new TreeNode<int>(1000);
        subTree2->right = new TreeNode<int>(1001);
        subTree2->right->right = new TreeNode<int>(1002);
        assert(GetTreeSize_R(subTree1) == 3);
        assert(GetTreeSize_R(subTree2) == 3);
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);
        auto rightestNode = FindRightestNode(root->right);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 6);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
        assert(entry1 == nullptr);
        assert(entry2 == nullptr);

        DeleteTree(&root);
    }
    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1 = nullptr;
        TreeNode<int>* entry2 = nullptr;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        TreeNode<int>* subTree1 = new TreeNode<int>(1000);
        subTree1->left = new TreeNode<int>(1001);
        subTree1->right = new TreeNode<int>(1002);
        TreeNode<int>* subTree2 = new TreeNode<int>(1000);
        subTree2->right = new TreeNode<int>(1001);
        subTree2->right->right = new TreeNode<int>(1002);
        assert(GetTreeSize_R(subTree1) == 3);
        assert(GetTreeSize_R(subTree2) == 3);
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);
        auto rightestNode = FindRightestNode(root->right);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 6);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
        assert(entry1 == nullptr);
        assert(entry2 == nullptr);

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1 = nullptr;
        TreeNode<int>* entry2 = nullptr;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

        TreeNode<int>* subTree1 = new TreeNode<int>(1000);
        subTree1->right = new TreeNode<int>(1002);
        subTree1->right->right = new TreeNode<int>(1001);
        TreeNode<int>* subTree2 = new TreeNode<int>(1000);
        subTree2->right = new TreeNode<int>(1001);
        subTree2->right->right = new TreeNode<int>(1002);
        assert(GetTreeSize_R(subTree1) == 3);
        assert(GetTreeSize_R(subTree2) == 3);
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);
        auto rightestNode = FindRightestNode(root->right);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 6);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
        assert(entry1 == nullptr);
        assert(entry2 == nullptr);

        DeleteTree(&root);
    }
}

Crafted a dynamic solution and it avoids all the problem shown in the approach of in-order solution because it is to compare the tree exactly match. Details: cpluspluslearning-petert.blogspot.co.uk/2016/01/dynamic-programming-find-if-given-tree.html

Test

void TestFindDuplicateSubTree()
{
    {
        TreeNode<int>* root = nullptr;
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
    }

    {
        const std::vector<int> testInput = { 1, 2 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root);
        auto rightestNode = FindRightestNode(root);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 1);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root);
        auto rightestNode = FindRightestNode(root);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 1);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == true);
        assert(entry1 != nullptr);
        assert(entry2 != nullptr);
        assert(CheckTwoTreesWithSameValues(entry1, subTree1));
        assert(CheckTwoTreesWithSameValues(entry2, subTree2));
        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->left);
        auto rightestNode = FindRightestNode(root->left);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 1);
        assert(*rightestNode->data == 4);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == true);
        assert(entry1 != nullptr);
        assert(entry2 != nullptr);
        assert(CheckTwoTreesWithSameValues(entry1, subTree1));
        assert(CheckTwoTreesWithSameValues(entry2, subTree2));
        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);
    }

    {
        const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        auto root = ConstructTreeRecursive(testInput);
        assert(root != nullptr);
        assert(GetTreeSize_R(root) == testInput.size());
        TreeNode<int>* entry1;
        TreeNode<int>* entry2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

        const std::vector<int> subTreeInput = { 100, 101, 102 };
        auto subTree1 = ConstructTreeRecursive(subTreeInput);
        auto subTree2 = ConstructTreeRecursive(subTreeInput);
        assert(GetTreeSize_R(subTree1) == subTreeInput.size());
        assert(GetTreeSize_R(subTree2) == subTreeInput.size());
        assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

        auto leftestNode = FindLeftestNode(root->right);
        auto rightestNode = FindRightestNode(root->right);
        assert(leftestNode != nullptr);
        assert(leftestNode->left == nullptr);
        assert(rightestNode != nullptr);
        assert(rightestNode->right == nullptr);
        assert(*leftestNode->data == 6);
        assert(*rightestNode->data == 10);

        leftestNode->left = subTree1;
        rightestNode->right = subTree2;
        assert(HaveDuplicateSubTree_R(root, entry1, entry2) == true);
        assert(entry1 != nullptr);
        assert(entry2 != nullptr);
        assert(CheckTwoTreesWithSameValues(entry1, subTree1));
        assert(CheckTwoTreesWithSameValues(entry2, subTree2));
        assert(CheckTwoTreesWithSameValues(entry1, entry2));

        DeleteTree(&root);
    }
}

Simple question. The idea is to use a min-priority-heap to track the top of the 3 sequence based on each element. Each time squeeze out one number. And skip counting the top of the min-priority-heap is equal to last value (it means that this value is a common divider of at least of two elements in the given set). Keep doing this until reach Nth.

Details: cpluspluslearning-petert.blogspot.co.uk/2015/12/find-nth-multiple-given-set.html

Test

void TestFindNthMultipleNum()
{
    std::vector<unsigned long> sortedPrimes;
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 1) == 0);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 5) == 0);

    sortedPrimes.push_back(4);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 1) == 4);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 5) == 20);

    sortedPrimes.push_back(6);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 1) == 4);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 2) == 6);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 3) == 8);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 4) == 12);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 5) == 16);
    assert(FindNthMultipleNumGivenSet(sortedPrimes, 6) == 18);
}

Dynamic solution. Iterate form n=1 upwards to reach n.
Details: cpluspluslearning-petert.blogspot.co.uk/2015/12/dynamic-programming-generate.html

Test

#include <cassert>
void TestSetPermutation()
{
    {
        const std::vector<int> input;
        auto result = PermuteSet(input, 0);
        assert(result.empty() == true);
        result = PermuteSet(input, 1);
        assert(result.empty() == true);
    }

    {
        const std::vector<int> input = { 1 };
        auto result = PermuteSet(input, 0);
        assert(result.empty() == true);
        result = PermuteSet(input, 2);
        assert(result.empty() == true);
        result = PermuteSet(input, 1);
        assert(result.size() == 1);
        assert(result[0].at(0) == 1);
    }

    {
        const std::vector<int> input = { 2, 3, 4, 5 };
        auto result = PermuteSet(input, 0);
        assert(result.empty() == true);

        result = PermuteSet(input, 1);
        assert(result.size() == 4);
        assert(result[0].size() == 1);
        assert(result[0].at(0) == 2);
        assert(result[1].size() == 1);
        assert(result[1].at(0) == 3);
        assert(result[2].size() == 1);
        assert(result[2].at(0) == 4);
        assert(result[3].size() == 1);
        assert(result[3].at(0) == 5);

        result = PermuteSet(input, 2);
        assert(result.size() == 16);
        for (auto iter = result.begin(); iter != result.end(); ++iter) {
            assert(iter->size() == 2);
        }
        assert((*result.begin()) == std::vector<int>({2, 2}));
        assert((*result.rbegin()) == std::vector<int>({5, 5}));

        result = PermuteSet(input, 3);
        assert(result.size() == 64);
        for (auto iter = result.begin(); iter != result.end(); ++iter) {
            assert(iter->size() == 3);
        }
        assert((*result.begin()) == std::vector<int>({ 2, 2, 2 }));
        assert((*result.rbegin()) == std::vector<int>({ 5, 5, 5 }));

        result = PermuteSet(input, 4);
        assert(result.size() == 256);
        for (auto iter = result.begin(); iter != result.end(); ++iter) {
            assert(iter->size() == 4);
        }
        assert((*result.begin()) == std::vector<int>({ 2, 2, 2, 2 }));
        assert((*result.rbegin()) == std::vector<int>({ 5, 5, 5, 5 }));

        result = PermuteSet(input, 6);
        assert(result.empty() == true);
    }
}

O(N) computation complexity and O(1) space complexity solution.
Details: cpluspluslearning-petert.blogspot.co.uk/2015/12/find-shortest-sub-string-containing-s1.html

Test

void TestFindTheShortestSubStringContainS1S2S3()
{
    {
        const std::string input("abc0123456789aksdfjasd");
        const std::string s1("0123");
        const std::string s2("3456");
        const std::string s3("");
        std::string result = FindTheShortestSubStringContainS123(input, s1, s2, s3);
        assert(result.empty() == true);
    }

    {
        const std::string input("abc0123456789aksdfjasd");
        const std::string s1("0123456");
        const std::string s2("3456");
        const std::string s3("1234");
        std::string result = FindTheShortestSubStringContainS123(input, s1, s2, s3);
        assert(result == std::string("0123456"));
    }

    {
        const std::string input("abc0123456789aksdfjasd");
        const std::string s1("0123");
        const std::string s2("3456");
        const std::string s3("6789");
        std::string result = FindTheShortestSubStringContainS123(input, s1, s2, s3);
        assert(result == std::string("0123456789"));
    }

    {
        const std::string input("sdfa01234ad23456dfad6789abc0123456789aksdfjasd");
        const std::string s1("0123");
        const std::string s2("3456");
        const std::string s3("6789");
        std::string result = FindTheShortestSubStringContainS123(input, s1, s2, s3);
        assert(result == std::string("0123456789"));
    }

    {
        const std::string input("sdfa01234ad23456dfad6789abc0123456789aksdfjasd0123skd3456kjsd6789jhs");
        const std::string s1("0123");
        const std::string s2("3456");
        const std::string s3("6789");
        std::string result = FindTheShortestSubStringContainS123(input, s1, s2, s3);
        assert(result == std::string("0123456789"));
    }
}

Was an Amazon interview question. Splitting and merging the linked list to achieve this.
Details: cpluspluslearning-petert.blogspot.co.uk/2015/01/data-structure-and-algorithm-linked.html

Test

using LinkedListString = LinkedListElement<std::string>;
void TestLinkedListPalindromWithStringCase1()
{
    LinkedListString* head = nullptr;
    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);
}

void TestLinkedListPalindromWithStringCase2()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("ABCDEFGFEDCBA"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase3()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("AABCDEFGFEDCBBD"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase4()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("ABCDEFFEDCBA"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase5()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("AABCDEFFEDCBAB"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase6()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("GHIJKJIHGFEDCBA"));
    LL_PushFront(&head, std::string("EF"));
    LL_PushFront(&head, std::string("CD"));
    LL_PushFront(&head, std::string("B"));
    LL_PushFront(&head, std::string("A"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase7()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("GHIJKJIHGFEDCBA"));
    LL_PushFront(&head, std::string("EF"));
    LL_PushFront(&head, std::string("CD"));
    LL_PushFront(&head, std::string("B"));
    LL_PushFront(&head, std::string("B"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);

    LL_Delete(&head);
}


void TestLinkedListPalindromWithStringCase8()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("GHIJKJIHGFEDCBA"));
    LL_PushFront(&head, std::string("EF"));
    LL_PushFront(&head, std::string("CD"));
    LL_PushFront(&head, std::string("B"));
    LL_PushFront(&head, std::string("A"));
    LL_PushFront(&head, std::string("A"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase9()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("XYZ"));
    LL_PushFront(&head, std::string("123"));
    LL_PushFront(&head, std::string("MNLOP"));
    LL_PushFront(&head, std::string("789"));
    LL_PushFront(&head, std::string("AABCDEFFEDCBAA"));
    LL_PushFront(&head, std::string("87"));
    LL_PushFront(&head, std::string("9"));
    LL_PushFront(&head, std::string("LNM"));
    LL_PushFront(&head, std::string("PO"));
    LL_PushFront(&head, std::string("321"));
    LL_PushFront(&head, std::string("ZYX"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase10()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("XYZ"));
    LL_PushFront(&head, std::string("123"));
    LL_PushFront(&head, std::string("MNLOP"));
    LL_PushFront(&head, std::string("789"));
    LL_PushFront(&head, std::string("AABCDEFGFEDCBAA"));
    LL_PushFront(&head, std::string("87"));
    LL_PushFront(&head, std::string("9"));
    LL_PushFront(&head, std::string("LNM"));
    LL_PushFront(&head, std::string("PO"));
    LL_PushFront(&head, std::string("321"));
    LL_PushFront(&head, std::string("ZYX"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == true);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase11()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("XYZ"));
    LL_PushFront(&head, std::string("123"));
    LL_PushFront(&head, std::string("MNLOP"));
    LL_PushFront(&head, std::string("789"));
    LL_PushFront(&head, std::string("AABCDEFFEDCBAA"));
    LL_PushFront(&head, std::string("87"));
    LL_PushFront(&head, std::string("9"));
    LL_PushFront(&head, std::string("LNM"));
    LL_PushFront(&head, std::string("PO"));
    LL_PushFront(&head, std::string("321"));
    LL_PushFront(&head, std::string("zYX"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);

    LL_Delete(&head);
}

void TestLinkedListPalindromWithStringCase12()
{
    LinkedListString* head = nullptr;
    LL_PushFront(&head, std::string("XYz"));
    LL_PushFront(&head, std::string("123"));
    LL_PushFront(&head, std::string("MNLOP"));
    LL_PushFront(&head, std::string("789"));
    LL_PushFront(&head, std::string("AABCDEFGFEDCBAA"));
    LL_PushFront(&head, std::string("87"));
    LL_PushFront(&head, std::string("9"));
    LL_PushFront(&head, std::string("LNM"));
    LL_PushFront(&head, std::string("PO"));
    LL_PushFront(&head, std::string("321"));
    LL_PushFront(&head, std::string("ZYX"));

    assert(LinkedListPalindromeDetector::IsPalindrome(head) == false);

    LL_Delete(&head);
}

This is to use technique of splitting/merging the linked list into two and again to one. Directly operate on the linked list rather than copying any of them.

Details: cpluspluslearning-petert.blogspot.co.uk/2015/12/linkedlist-find-longest-palindrome.html

Test

void TestLinkedListLongestPalindrome()
{
    using Result = LinkedListLongestPalindrome<char>::LL_PalindromeResult;
    {
        LinkedListElement<char> *inputLL = nullptr;
        Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
        assert(r.len == 0);
        assert(r.startPtr == nullptr);
    }
    {
        LinkedListElement<char> *inputLL = nullptr;
        LL_PushFront(&inputLL, 'A');
        Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
        assert(r.len == 1);
        assert(r.startPtr->data == 'A');
    }
    {
        LinkedListElement<char> *inputLL = nullptr;
        LL_PushFront(&inputLL, 'B');
        LL_PushFront(&inputLL, 'A');
        Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
        assert(r.len == 1);
        assert(r.startPtr->data == 'A');
    }
    {
        const std::string input("ABCDEFGHIJKLMN");
        LinkedListElement<char> *inputLL = nullptr;
        auto iterREnd = input.rend();
        for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
            LL_PushFront(&inputLL, *iterR);
        }
        Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);
        assert(r.len == 1);
        assert(r.startPtr->data == 'A');
    }
    {
        const std::string input("AAAAAAAAAAAAAAAAAAAAA");
        LinkedListElement<char> *inputLL = nullptr;
        auto iterREnd = input.rend();
        for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
            LL_PushFront(&inputLL, *iterR);
        }
        Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);

        std::string palindrome;
        while (r.len) {
            palindrome.push_back(r.startPtr->data);
            r.startPtr = r.startPtr->next;
            --r.len;
        }
        assert(palindrome == input);
    }
    {
        const std::string input("ABABCDEFGFEDCBAXY");
        LinkedListElement<char> *inputLL = nullptr;
        auto iterREnd = input.rend();
        for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
            LL_PushFront(&inputLL, *iterR);
        }
        Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);

        std::string palindrome;
        while (r.len) {
            palindrome.push_back(r.startPtr->data);
            r.startPtr = r.startPtr->next;
            --r.len;
        }
        assert(palindrome == "ABCDEFGFEDCBA");
    }
    {
        const std::string input("ABABCDEFGFEDCBAXYZUVWXYZ");
        LinkedListElement<char> *inputLL = nullptr;
        auto iterREnd = input.rend();
        for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
            LL_PushFront(&inputLL, *iterR);
        }
        Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);

        std::string palindrome;
        while (r.len) {
            palindrome.push_back(r.startPtr->data);
            r.startPtr = r.startPtr->next;
            --r.len;
        }
        assert(palindrome == "ABCDEFGFEDCBA");
    }
    {
        const std::string input("UVWXYZABABCDEFGFEDCBAXYZ");
        LinkedListElement<char> *inputLL = nullptr;
        auto iterREnd = input.rend();
        for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
            LL_PushFront(&inputLL, *iterR);
        }
        Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);

        std::string palindrome;
        while (r.len) {
            palindrome.push_back(r.startPtr->data);
            r.startPtr = r.startPtr->next;
            --r.len;
        }
        assert(palindrome == "ABCDEFGFEDCBA");
    }
    {
        const std::string input("AB01234567899876543210XY");
        LinkedListElement<char> *inputLL = nullptr;
        auto iterREnd = input.rend();
        for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
            LL_PushFront(&inputLL, *iterR);
        }
        Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);

        std::string palindrome;
        while (r.len) {
            palindrome.push_back(r.startPtr->data);
            r.startPtr = r.startPtr->next;
            --r.len;
        }
        assert(palindrome == "01234567899876543210");
    }
    {
        const std::string input("asfdasdfasAB01234567899876543210XY");
        LinkedListElement<char> *inputLL = nullptr;
        auto iterREnd = input.rend();
        for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
            LL_PushFront(&inputLL, *iterR);
        }
        Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);

        std::string palindrome;
        while (r.len) {
            palindrome.push_back(r.startPtr->data);
            r.startPtr = r.startPtr->next;
            --r.len;
        }
        assert(palindrome == "01234567899876543210");
    }
    {
        const std::string input("AB01234567899876543210XYkljfkajsdkfasd");
        LinkedListElement<char> *inputLL = nullptr;
        auto iterREnd = input.rend();
        for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
            LL_PushFront(&inputLL, *iterR);
        }
        Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);

        std::string palindrome;
        while (r.len) {
            palindrome.push_back(r.startPtr->data);
            r.startPtr = r.startPtr->next;
            --r.len;
        }
        assert(palindrome == "01234567899876543210");
    }
    {
        const std::string input("AB01234567899876543210ABCDDCBAxyx");
        LinkedListElement<char> *inputLL = nullptr;
        auto iterREnd = input.rend();
        for (auto iterR = input.rbegin(); iterR != iterREnd; ++iterR) {
            LL_PushFront(&inputLL, *iterR);
        }
        Result r = LinkedListLongestPalindrome<char>().operator()(inputLL);

        std::string palindrome;
        while (r.len) {
            palindrome.push_back(r.startPtr->data);
            r.startPtr = r.startPtr->next;
            --r.len;
        }
        assert(palindrome == "01234567899876543210");
    }
}

L - A set of linked lists with each prime number with one liked list
MH - A min heap to take the head values of L
Pseudo-code:
- If N is ranged in [1, m+1], return from {1, P1, ..., Pm}
- Otherwise,
- Initialize Nth = 1
- Starting with {P1}, {P2}, ..., {Pm} for L.
- Find the smallest value, Es, of the min heap, MH, that is made of the head of L.
As MH - {P1, P2, ..., Pm} at the start.
- Find the corresponding prime number against which linked list Es comes from, Px and Lx
- Append Es*Px into Lx, Es*Px+1 into Lx+1, ..., Ex*Pm into Lm
- Remove Es from Lx and increment the Nth
- Repeat above 4 steps until Nth reaches N.

Details: cpluspluslearning-petert.blogspot.co.uk/2015/12/find-nth-expressible-number-of-given.html

Test:

void TestFindNthExpressibleNum()
{
    std::vector<unsigned long> sortedPrimes;
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 1) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 5) == 0);

    sortedPrimes.push_back(2);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 1) == 1);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 2) == 2);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 3) == 4);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 4) == 8);

    sortedPrimes.push_back(3);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 1) == 1);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 2) == 2);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 3) == 3);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 4) == 4);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 5) == 6);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 6) == 8);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 7) == 9);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 8) == 12);

    sortedPrimes = {3, 5, 7};
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 0) == 0);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 1) == 1);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 2) == 3);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 3) == 5);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 4) == 7);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 5) == 9);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 6) == 15);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 7) == 21);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 8) == 25);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 9) == 27);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 10) == 35);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 11) == 45);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 12) == 49);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 13) == 63);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 14) == 75);
    assert(FindNthExpressibleNumGivenSet(sortedPrimes, 15) == 81);
}

The idea is to start from the right hand side of array to the left hand side and use insertion sort.
- Initialize a sorted data like std::set as sortedArray
- Initialize a linked list to take the result, result
- Take the element, x, from the array in the reverse order
- Find the number of larger value in sortedArray than x, as n
- Push n into the front of result
- Insert x into sortedArray
- Loop the above 4 steps until exhaust the whole array
- Return result

Implementation: cpluspluslearning-petert.blogspot.co.uk/2015/11/insertion-sort-find-number-of-larger.html

Test

void TestFindTheNumberOfLargerValuesInTheRemainingArray()
{
    {
        std::vector<int> input;
        std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
        assert(output.empty() == true);

        input.push_back(0);
        output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
        assert(output.size() == 1);
        assert(output[0] == 0);
    }

    {
        std::vector<int> input = { 3, 4, 5, 9, 2, 1, 3 };
        const std::vector<int> result = { 3, 2, 1, 0, 1, 1, 0 };
        std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
        assert(result == output);
    }

    {
        std::vector<int> input = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        const std::vector<int> result = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
        std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
        assert(result == output);
    }

    {
        std::vector<int> input = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
        const std::vector<int> result = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
        assert(result == output);
    }
}