C++ - Restrict Creation of Objects

1. Problem Description
This is a Microsoft interview question from careercup. Here is the description of the original thread,
"

how to restrict creation of object inside the function fun 

although destructor and constructor is private??
#include <iostream>

class ABC
{
private :
~ABC()
{

}

ABC()
{
std::cout <<"ABC";
}


public:
static void fun()
{


ABC t;

}



};
int main()
{
ABC::fun();

}

- jkl June 19, 2016 in India | Report Duplicate | Flag ".

2. Scope
This is a very vague question. Here I am going to concentrate on the process of the object creation and the object deletion. The first stage is compiler has to know all the data types of the class before creating an object out of it. It includes all its own member variables and the data members of its base class(es). The second stage is the order of object creation and object deletion. It starts from the member variables of its base classes to the constructor(s) of the base class then in the order of hierarchy of inheritance to its own member variables and therefore its own constructor. The object deletion is the exactly the opposite way of creation. The solutions will be focusing on the chain of these two stages.

3. Template
This solution is on the first stage. The types of the class has to be resolved before object creation. Any ambiguity will stop creating objects.

template <typename T>
class Foo
{
    Foo() {
        std::cout << "Foo()" << std::endl;
    }
    ~Foo() {
        std::cout << "~Foo()" << std::endl;
    }
public:
    static void Bar() {
        Foo f;
    }
};

Templatized this class stops creating objects because "Foo f;" does not provide any information for compiler to deduce template type and generate the instance of class.

4. Member Variables 

As the code only provides default constructor, any member variables that cannot be initialized/created via its default constructor will stop creating Foo object. This means that all types of its member variables including the member variables of its base class(es) have to provide default constructors.

class Foo
{
    int &m_Val;
    Foo() {
        std::cout << "Foo()" << std::endl;
    }
    ~Foo() {
        std::cout << "~Foo()" << std::endl;
    }
public:
    static void Bar() {
        Foo f;
    }
};

Reference type does not provide default constructor and it has to be initialized via existing variables in the initialization list of constructor. m_Val will stop creating Foo objects.

class Abc

{

public:

    Abc(int x)

    {}

};

class Foo 

{

    Abc m_Abc;

    Foo() {

        std::cout << "Foo()" << std::endl;

    }

    ~Foo() {

        std::cout << "~Foo()" << std::endl;

    }

public:

    static void Bar() {

        Foo f;

    }

};

The same reason m_Abc can't be initialized because class Abc does not provide a default constructor. The fix will have to provide a default constructor of Abc or initialize m_Abc in Foo's initialization list.

Any member variables like above m_Abc appearing in Foo's base class which has no default constructor implementation will propagate the creation failure to Foo object.

5. Access Control

Here it refers to the constructor and destructor access control of its base class, which have to be accessible in object creation and deletion of derived class. In Foo::Bar() function it can access Foo's constructor and destructor because Bar() is a member function of Foo even though Foo's constructor and destructor are declared private. But if Foo has base class(es), hiding the access of either constructor or destructor of its base class(es) will stop Foo object creation.

class Interface

{

    Interface();

    ~Interface();

};

class Foo : public Interface

{

    Foo() {

        std::cout << "Foo()" << std::endl;

    }

    ~Foo() {

        std::cout << "~Foo()" << std::endl;

    }

public:

    static void Bar() {

        Foo f;

    }

};

Declaring either constructor or destructor of Interface will stop creating Foo objects, because Foo cannot access its bases classes private section.

6. Constructor Signature Mismatch

If there is no default constructor is implemented in base classes, then the constructor of base class(es) has to be specifically appearing in initialization list in order to be called. Otherwise it breaks the object creation process. Simply compiler does not how to initialize member variables or status in generally of its base class(es).

class Abc

{

public:

    Abc(int x)

    {}

};

class Foo : public Abc

{

    Foo() {

        std::cout << "Foo()" << std::endl;

    }

    ~Foo() {

        std::cout << "~Foo()" << std::endl;

    }

public:

    static void Bar() {

        Foo f;

    }

};

The fix is to call Abc's constructor in the initialization list of Foo.

7. Abstract Classes

The object of absctract classes cannot be created because compiler has no where to populate the virtual table. Any derived class that does not implement all abstract virtual function will remain as abstract classes and therefore cannot create objects out of it.

 

class Foo

{

    Foo() {

        std::cout << "Foo()" << std::endl;

    }

    ~Foo() {

        std::cout << "~Foo()" << std::endl;

    }

public:

    static void Bar() {

        Foo f;

    }

    virtual void PrintSelf() = 0;

};

Foo has an abstract virtual function PrintSelf() and therefore cannot create objects out it.

class Interface

{

    virtual int GetVersion() = 0;

};

class Foo : public Interface

{

    Foo() {

        std::cout << "Foo()" << std::endl;

    }

    ~Foo() {

        std::cout << "~Foo()" << std::endl;

    }

public:

    static void Bar() {

        Foo f;

    }

};

Foo inherits from an abstract class Interface but does not implement the abstract virtual function. Therefore it remains as an abstract function and cannot create objects out of it.

Data Structure and Algorithm - Find the Shortest Path in Grid

1. Problem Description
This is a Facebook interview question for Android developer from careercup. Here is the original thread,
"

A museum was represented by a square matrix that was filled with O, G, and W where O represented open space G represented guards, and W represented walls. Write a function that accepts the square matrix and returns another square matrix where all of the O's in the matrix are replaced with the number of how many spaces they are away from a guard, without being able to go through any walls.

- fire May 17, 2016 in United States | Report Duplicate | Flag 
".

2. Data Structure and Algorithm
Mapping of the museum:
Given a museum there are 3 things to represent, open ground, guard and wall. The key here is to use wise data structure to represent museum in memory. In a common-sense scenario there are a few guards and plenty of open guards. Instead of a full size of grid to model museum two hash sets are to represent guards and walls.
    - Location: row and column
    - A hash set of locations to represent guards's position in museum
    - A hash set of locations to represent wall's position in museum
    - A hash map of locations as key and distance to guard as value to represent open group to guard
    - Any open group not appearing in above hash map means isolated to guards

Algorithm:
Each guard has children nodes in the grid of possible directions to reach them (in the case of implementation in this post 4 directions - left, right, up and down). Therefore it is not hard to link to graph problem. Each node is linked to 4 neighbors (left, right , up and down). Each iteration expand one step from guards. Terminate expanding if reaches wall/guard/open-ground-already-visited and take the result (location + breadth-of-traverse) if reaches an open ground. In this case it is breath-first traverse the museum, which guarantees that the shortest path from open ground to its reachable guards.

3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <list>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
enum class MuseumItem
{
    WALL = 0,
    OPEN,
    GUARD
};

struct LocHashFunc
{
    size_t operator()(const std::tuple<size_t, size_t> &loc) const {
        size_t row, col;
        std::tie<size_t, size_t>(row, col) = loc;
        return std::hash<size_t>()(row) ^ std::hash<size_t>()(col);
    }

    bool operator()(const std::tuple<size_t, size_t> &lhs,
                    const std::tuple<size_t, size_t> &rhs) const {
        return lhs == rhs;
    }
};

using LocationMap = std::unordered_set<std::tuple<size_t, size_t>, LocHashFunc, LocHashFunc>;
using LocAndDistMap = std::unordered_map<std::tuple<size_t, size_t>, int, LocHashFunc, LocHashFunc>;

bool ParserMuseumMap(const std::vector<std::vector<MuseumItem>> &museum,
                     LocationMap &guards,
                     LocationMap &walls)
{
    // for this implementation, the mesum must be square
    const size_t ROWS = museum.size();
    if (ROWS == 0) {
        return false;
    }

    const size_t COLS = museum[0].size();
    auto itEnd = museum.end();
    size_t row = 0, col = 0;
    for (auto it = museum.begin(); it != itEnd; ++it, ++row) {
        if (it->size() != COLS) {
            return false; // enforce square map
        }

        auto itRowEnd = it->end();
        col = 0;
        for (auto itRow = it->begin(); itRow != itRowEnd; ++itRow, ++col) {
            switch (*itRow) {
            case MuseumItem::WALL:
                walls.insert(std::make_tuple(row, col));
                break;
            case MuseumItem::OPEN:
                break;
            case MuseumItem::GUARD:
                guards.insert(std::make_tuple(row, col));
                break;
            default:
                return false;
            }
        }
    }
    return true;
}

void ExpandSeach(const std::tuple<size_t, size_t> &loc,
                 const LocationMap &guards,
                 const LocationMap &walls,
                 const size_t distance,
                 LocAndDistMap & distances,
                 std::list < std::tuple<size_t, size_t> > &toVisits)
{
    if (walls.find(loc) != walls.end()) {
        return;
    }

    if (guards.find(loc) != guards.end()) {
        return;
    }

    if (distances.find(loc) == distances.end()) {
        distances.insert(std::make_pair(loc, distance));
        toVisits.push_back(loc);
    }
}

const LocAndDistMap GetDistances(const size_t ROWS,
                                 const size_t COLS,
                                 const LocationMap &guards,
                                 const LocationMap &walls)
{
    LocAndDistMap distances;
    std::list<std::tuple<size_t, size_t>> toVisits(guards.begin(), guards.end());
    toVisits.push_back(std::tuple<size_t, size_t>{-1, -1});
    LocationMap visited;
    size_t dist = 1;
    size_t row, col;
    size_t distance = 1;
    while (!toVisits.empty()) {
        std::tie<size_t, size_t>(row, col) = toVisits.front();
        if (row == -1 && col == -1) {
            ++distance;
            toVisits.pop_front();
            if (toVisits.empty()) {
                break;
            }
            toVisits.push_back(std::make_tuple(-1, -1));
        }
        else {
            if (row > 0) {
                auto loc = std::make_tuple( row - 1, col );
                ExpandSeach(loc, guards, walls, distance, distances, toVisits);
            }
            if (row != (ROWS - 1)) {
                auto loc = std::make_tuple(row + 1, col);
                ExpandSeach(loc, guards, walls, distance, distances, toVisits);
            }
            if (col > 0) {
                auto loc = std::make_tuple(row, col - 1);
                ExpandSeach(loc, guards, walls, distance, distances, toVisits);
            }
            if (col != (COLS - 1)) {
                auto loc = std::make_tuple(row, col + 1);
                ExpandSeach(loc, guards, walls, distance, distances, toVisits);
            }
            toVisits.pop_front();
        }
    }

    return distances;
}

const LocAndDistMap GetDistances(const std::vector<std::vector<MuseumItem>> &museum)
{
    LocationMap guards;
    LocationMap walls;
    if (!ParserMuseumMap(museum, guards, walls)) {
        return LocAndDistMap();
    }

    const size_t ROWS = museum.size();
    const size_t COLS = museum[0].size();
    return GetDistances(ROWS, COLS, guards, walls);
}

// ********************************************************************************

// Test

// ********************************************************************************

#include <cassert>

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

    }

}

Dynamic Programming - String Decoder

1. Problem Description
This is a Facebook interview question for software engineers from careercup. Here is the original thread,
"

You are given a string "abc" which is encoded like "123" where alphabets are mapped like a => 1 to z => 26. Now find out how many string can be formed by reverse engineering encode string "123". 

For ex. given string "123" we can form 3 string "abc"(1,2,3), "lc" (i.e 12,3), "aw"(1,23).

for string "1234" we have following possible combinations, I might be missing some of them but you get the idea

{12, 3, 4}
{1, 23, 4}
{1, 2, 3, 4}

- sachin323 May 16, 2016 in United States | Report Duplicate | Flag ".

2. Data Structure and Algorithm
Some contributors mentioned on the thread that this is a dynamic problem. In fact the sub-problem is also reasonably obvious to spot. Given an input of number string, for instance "567123432234543789", assume that at position i of this string. Any single number can always be mapped into letters (a-z), ranges from [1, 26], therefore one sub-problem will be finding the decoding of the rest string from i+1 to the end. The second sub-problem may or may not exist, depending on the value at i and its subsequent value in i+1. If they are ranging from [10, 26], representing [j, z], then the second sub-problem exists - find the decoding of i+2 to the rest of string. If they are ranging out of [10, 26], then does not exist a second sub-problem.
For instance "36......",  at position "3" only has one sub-problem of "6......"; "2415......" at position "2" has two sub problems "425......" and "15......".

A special number in the number string is "0", because "0" does not represent any letter, [a, z]. Any problem starting with "0" does not have any sub-problems and it can be terminated because it has not valid decoding.
For instance any input number string starting with "0......", does not have any valid decoding to represent any letter string.

As usual, cache technique is used in my dynamic-programming solution. It takes the sub-problem, the number string, as the key and take how many ways of decoding as value.

3. C++ Implementation
The return value of function "StringDecoder(" will be either greater than 0 or less than 0. A return value greater than 0 indicates how many ways of decoding. And a negative return value indicates failure to find an decoding.
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <string>
#include <unordered_map>

bool ValidStringNumber(const std::string &plainText)
{
    if (plainText.empty()) {
        return false;
    }
    {
        auto itEnd = plainText.end();
        for (auto it = plainText.begin(); it != itEnd; ++it) {
            if (*it > '9' || *it < '0') {
                return false;
            }
        }
    }

    return true;
}

using StringDecoderMap = std::unordered_map<std::string, ptrdiff_t>;

ptrdiff_t StringDecoder_R(const std::string &number,
                          const std::string::const_iterator curIt,
                          StringDecoderMap& cache)
{
    if (curIt == number.end()) {
        return 1;
    }
    if (*curIt == '0') {
        return -1;
    }
    auto itNext = curIt + 1;
    if (itNext == number.end()) {
        return 1;
    }

    const std::string key(curIt, number.end());
    auto itFound = cache.find(key);
    if (itFound != cache.end()) {
        return itFound->second;
    }

    ptrdiff_t decodes = -1;;
    ptrdiff_t tempCount = StringDecoder_R(number, itNext, cache);
    if (tempCount >= 0) {
        decodes = tempCount;
    }

    const std::string twoChars(curIt, curIt + 2);
    if (atoi(twoChars.c_str()) <= 26) {
        tempCount = StringDecoder_R(number, ++itNext, cache);
        if (tempCount >= 0) {
            if (decodes > 0) {
                decodes += tempCount;
            }
            else {
                decodes = tempCount;
            }
        }
    }

    cache.insert(std::make_pair(key, decodes));
    return decodes;
}

ptrdiff_t StringDecoder(const std::string &number)
{
    if (!ValidStringNumber(number)) {
        return -1;
    }

    StringDecoderMap cacheMap;
    return StringDecoder_R(number, number.begin(), cacheMap);
}

// ********************************************************************************
// Testing
// ********************************************************************************
#include <cassert>
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);

}

Dynamic Programming - Min Cost of Releasing Prisoners

1. Problem Description
This is an Amazon interview question for software developer from careercup. Here is the original thead,
"

/*
Prison cell question
In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbors." A wall with a window separates adjacent cells, and neighbors can communicate through that window.
All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbors find out, and each communicates this to his other neighbor. That prisoner passes it on to his other neighbor, and so on until they reach a prisoner with no other neighbor (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.
Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.
Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.

Task: find the minimum amount of gold we need to bribe the prisoners so that the chosen prisoners can be released without causing cell destruction.
Input example:
8 cells, 1 prisoner has to be released. The prisoner to be released is the 3rd one.
|1|2|3|4|5|6|7|8|
7 gold coins
another example:
20 cells, 3 prisoners to be released: 3, 6 and 14
|1|2| |4|5| |7|8|9|10|11|12|13| |15|16|17|18|19|20|
release prisoner 3: 19 gold coins
release prisoner 6: 16 gold coins
release prisoner 14: 13 gold coins

release 14: 19 gold coins
release 6: 12 gold coins
release 3: 4 gold coins

input:
number of cells
prisoners that need to be released
output:
least number of gold coins we need to give
*/

- xankar May 12, 2016 in United States | Report Duplicate | Flag 
".

2. Data Structure and Algorithm
Given P prison cells [1, 2, ..., p] and Q cells [x, y, ..., q], bear in mind that Q is a a subset of P. And P and Q are in the ascending order. Assume that i in Q is released. Then the cost will be
    P - 1 + minCost([1, ..., i -1], [x, ...q1]) + minCost([i+1, ..., p, [q2, ..., q], where
        q1 and q2 are the neighbor cells in Q.

This problem is a minimization problem. The above tells that how to compute the cost of any cell in Q. Go through Q, [x, y, ..., q] and keep track the minimal value,
    minCost(P - 1 + minCost([1,..., i-1], [x, ...q1]) + minCost([i+1, ..., p], [q2, ...,q])), where
         i belongs to [x, y, ..., q]

The above tells us that this can solved by dynamic problem. The problem can be solved by two sub-problems. Take any prisoner i out, then prisoners and cells on the left hand side of i become a sub-problem and those on the right hand side of i become another sub-problem.

 Again caching techniques are used in the solution, take the combination of {P, Q} as the hash key and the min cost as the value.

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

struct PrisonCellKey
{
    PrisonCellKey(const std::vector<size_t> &c,
                  const std::vector<size_t> &r)
        : cells(c)
        , releases(r)
    {}
    std::vector<size_t> cells;
    std::vector<size_t> releases;

    bool operator==(const PrisonCellKey& rhs) const {
        return cells == rhs.cells && releases == rhs.releases;
    }
};

size_t SizetVectorHash(const std::vector<size_t> &input)
{
    size_t hash = 0;
    for (auto it = input.begin(); it != input.end(); ++it) {
        hash = hash^std::hash<size_t>()(*it);
    }

    return hash;
}

struct PrisionCellHashFunc
{
    const static size_t PrimeOfCells = 2909;
    const static size_t PrimeOfReleases = 4021;

    size_t operator()(const PrisonCellKey &key) const {
        size_t cellsHash = SizetVectorHash(key.cells);
        size_t releasesHash = SizetVectorHash(key.releases);

        return std::hash<size_t>()(
            cellsHash*PrimeOfCells + releasesHash*PrimeOfReleases);
    }

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

};

using PrisonCellHashMap = std::unordered_map<PrisonCellKey, size_t, PrisionCellHashFunc, PrisionCellHashFunc>;

size_t MinCostOfReleasingCells_R(const std::vector<size_t> &cells,
                               const std::vector<size_t> &toRelease,
                               PrisonCellHashMap &cache)
{
    const size_t NRelease = toRelease.size();
    if (NRelease == 0) {
        return 0;
    }
    else if (NRelease == 1) {
        return cells.size() - 1;
    }

    const PrisonCellKey key(cells, toRelease);
    auto it = cache.find(key);
    if (it != cache.end()) {
        return it->second;
    }
    const size_t NCells = cells.size();
    auto itEnd = toRelease.end();
    size_t minCost = -1;
    size_t tempCost;
    for (auto it = toRelease.begin(); it != itEnd; ++it) {
        tempCost = NCells - 1;
        {
            auto tmpIt = cells.begin();
            std::advance(tmpIt, *it);
            std::vector<size_t> LeftCells(cells.begin(), tmpIt);
            std::vector<size_t> LeftToRelease(toRelease.begin(), it);
            tempCost += MinCostOfReleasingCells_R(LeftCells, LeftToRelease, cache);
        }
        {
            std::vector<size_t> RightCells;
            for (int i = *it + 1; i < NCells; ++i) {
                RightCells.push_back(i - *it - 1);
            }
            std::vector<size_t> RightToRelease;
            for (auto tmpIt = it + 1; tmpIt != toRelease.end(); ++tmpIt) {
                RightToRelease.push_back(*tmpIt - *it - 1);
            }
            tempCost += MinCostOfReleasingCells_R(RightCells, RightToRelease, cache);
        }
        if (tempCost < minCost) {
            minCost = tempCost;
        }
    }

    cache.insert(std::make_pair(key, minCost));

    return minCost;
}

size_t MinCostOfReleasingCells(const std::vector<size_t> &cells,
                               const std::vector<size_t> &toRelease)
{
    PrisonCellHashMap cache;
    return MinCostOfReleasingCells_R(cells, toRelease, cache);
}

// ********************************************************************************

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

    }

}

Compare Exotic String

1. Problem Description
This is a Google interview question for software engineer from careercup. Here is the description from the original thread,
"

Provide a function that allow to compare two strings lexicography, having in mind that these words may contain digraphs (two letters together represents a single one i.e in Spanish ch is a single character ). 

This in order to be able to sort a list of words.

- urodba April 07, 2016 in United States | Report Duplicate | Flag ".

2. Data Structure and Algorithm
The idea follows
    - Build all possible characters into a Trie structure
    - Build a hash map for each valid entry in Trie, for exmaple
        * The pointer in Trie as the key and has a integer as value
        * Character "a" as 65 (in ASCII table)
        * Character "cz" as 100 (any number to represent its value comparing to other characters)
    - Search a valid entry from the starting of the string in the Trie until failed to find or reach the end
        * Find the longest valid entry in Trie
        * Compare two valid entries in two given strings
            ~ Return a positive value if lhs > rhs
            ~ Return a negative value if lhs < rhs
            ~ Return 0 if equal

Initially I was thinking to use a hash map instead of Trie to build up the character table. But the disadvantage of hash map is that have to continue searching for the valid entry in the character table up the maximal key size. For example if a valid entry can be made up to 10 English character, then have to search 10 times (equal to the maximal key size) to enumerate all the possibility. In the case of just one valid entry is 10 characters long ("abcdefghij") in the character table. Still need to search 10 times even starting with "x".
A character table of Trie structure does not have this problem. And in computation wise Trie search needs only one pointer checking and should outpaces harsh map, which needs to compute hash code then pointer checking.

3. C++ Implementation
The Trie structure used in this implemented can be found in Data Structure and Algorithm - Trie, Data Structure and Algorithm - Trie and Palindrome (Google Interview Question) and Trie - Live Stream Words Detector.

// ********************************************************************************
// Implementation
// ********************************************************************************

// header
#include "DictionaryTrie.h"

#include <exception>
#include <string>
#include <unordered_map>
#include <vector>

struct ExoticChar
{
    ExoticChar(const std::string &ec, const int v)
        : eChar(ec), val(v)
    {}

    ExoticChar& operator=(const ExoticChar &rhs) {
        this->eChar = rhs.eChar;
        this->val = rhs.val;
        return *this;
    }

    std::string eChar;
    int val;
};

class EscException : public std::exception
{
public:
    EscException(const std::string &msg)
        : m_Msg(msg)
    {}

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

private:
    const std::string m_Msg;
};

class ExoticStringComparator
{
public:
    ExoticStringComparator(const std::vector<ExoticChar> &staticTable);
    ~ExoticStringComparator();

    int CompareExoticString(const std::string &lhs, const std::string &rhs) const;
private:
    DictionaryTrie* m_StaticMapRoot;
    std::unordered_map<DictionaryTrie*, int> m_KeyValMap;
};

// cpp

#include "ExoticStringComparator.h"

ExoticStringComparator::ExoticStringComparator(const std::vector<ExoticChar> &staticTable)

    : m_StaticMapRoot(NULL)

{

    if (staticTable.empty()) {

        throw EscException("ExoticStringComparator creation - empty table");

    }

    m_StaticMapRoot = new DictionaryTrie();

    DictionaryTrie *tempPtr;

    for (auto it = staticTable.begin(); it != staticTable.end(); ++it) {

        tempPtr = AddWord(m_StaticMapRoot, it->eChar.c_str());

        if (tempPtr) {

            m_KeyValMap.insert(std::make_pair(tempPtr, it->val));

        }

    }

}

ExoticStringComparator::~ExoticStringComparator()

{

    DestoryDictionaryTrie(m_StaticMapRoot);

    m_StaticMapRoot = NULL;

}

int ExoticStringComparator::CompareExoticString(const std::string &lhs, const std::string &rhs) const

{

    auto lhsTempIt = lhs.begin();

    auto rhsTempIt = rhs.begin();

    int result = 0;

    DictionaryTrie *lhsTemp, *lhsCur;

    DictionaryTrie *rhsTemp, *rhsCur;

    //while (lhsCurIt != lhs.end() && rhsCurIt != rhs.end()) {

    while (lhsTempIt != lhs.end() && rhsTempIt != rhs.end()) {

        lhsTemp = m_StaticMapRoot;

        while (lhsTemp = FindPath(lhsTemp, *lhsTempIt)) {

            if (lhsTemp->str) {

                lhsCur = lhsTemp;

            }

            ++lhsTempIt;

            if (lhsTempIt == lhs.end()) {

                break;

            }

        }

        rhsTemp = m_StaticMapRoot;

        while (rhsTemp = FindPath(rhsTemp, *rhsTempIt)) {

            if (rhsTemp->str) {

                rhsCur = rhsTemp;

            }

            ++rhsTempIt;

            if (rhsTempIt == rhs.end()) {

                break;

            }

        }

        auto lhsValIt = m_KeyValMap.find(lhsCur);

        auto rhsValIt = m_KeyValMap.find(rhsCur);

        if (lhsValIt == m_KeyValMap.end() || rhsValIt == m_KeyValMap.end()) {

            throw EscException("CompareExoticString: invalid map");

        }

        result = lhsValIt->second - rhsValIt->second;

        if (result != 0) {

            return result;

        }

    }

    if (lhsTempIt != lhs.end()) {

        return 1;

    }

    else if (rhsTempIt != rhs.end()) {

        return -1;

    }

    return result;

}

// ********************************************************************************
// 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);

    }
}

Merge X-way Sorted List

1. Problem Description
This is a Google interview question from careercup. Here is the origin thread
'

A list L is too big to fit in memory. L is partially sorted. Partially sorted in a specific way: x-sorted L[i] < L[i+x]. Any element is at most x indices out of position. 

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

Sort the list L.

- jss_777 March 30, 2016 in United States | Report Duplicate | Flag '.

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

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

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

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

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

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

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

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

#include <queue>
#include <vector>

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

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

    return start;
}

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

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

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

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

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

    T value;
    size_t index;
};

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

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

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

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

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

    return result;
}

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

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

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

        assert(count == 16);
    }
}

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

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

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

1. Problem Description

This is an Amazon interview question for software develop engineer at the 2nd round face-to-face from careercup. Here is the original thread,

"

This was the 2nd round. Face to face. DS and Algo 

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

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

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

- uday4friendz March 04, 2016 in India for Product Details Page | Report Duplicate | Flag ".

2. Data Structure And Algorithm

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

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

    - F(N, x, y, i) , where N = m -2, i <= (n-m+2) 

        * F(N-1, y, arr[i], i+1) if x < y and y < arr[i] (ascending order sequence candidate)

        * F(N-1, y, arr[i], i+1) if x > y and y > arr[i] (descending order)

        * 0, neither an ascending sequence nor a descending sequence

    - F(0, r, s, t) = 1

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

3. C++ Implementation

// ********************************************************************************

// Implementation

// ********************************************************************************

#include <exception>

#include <unordered_map>

#include <vector>

class InvalidParamException : public std::exception

{

public:

    InvalidParamException(const std::string & msg)

        : m_msg(msg)

    {}

    const char* what() const {

        return m_msg.c_str();

    }

private:

    const std::string m_msg;

};

struct HashKey

{

    size_t idx;

    size_t remainingSeqLen;

    bool operator==(const HashKey& rhs) const {

        return idx == rhs.idx && remainingSeqLen == rhs.remainingSeqLen;

    }

};

struct HashKeyHashFunc

{

    size_t operator()(const HashKey &key) const {

        return std::hash<size_t>()(key.idx) ^

            std::hash<size_t>()(key.remainingSeqLen);

    }

    bool operator()(const HashKey &lhs, const HashKey &rhs) const {

        return lhs == rhs;

    }

};

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

template <typename T>

int DetectAscendingOrDescendingSequence(const std::vector<T> &input,

                                        const size_t input_size,

                                        const size_t idx,

                                        const bool isAscending,

                                        size_t m,

                                        HashMap &cacheAscending,

                                        HashMap &cacheDescending)

{

    if (!m) {

        // F(0, r, s, t) return 1

        return 1;

    }

    // Return the cached value if it's a repeated computation

    if (isAscending) {

        auto foundIter = cacheAscending.find(HashKey{ idx, m });

        if (foundIter != cacheAscending.end()) {

            return foundIter->second;

        }

    }

    else {

        auto foundIter = cacheDescending.find(HashKey{ idx, m });

        if (foundIter != cacheDescending.end()) {

            return foundIter->second;

        }

    }

    int numSeq = 0;

    for (size_t i = idx; i <= (input_size - m); ++i) {

        // Continue the sub-problem if sequence's order is maintained

        // Check next available digits if the order is broken

        if ( (isAscending && input[idx - 1] < input[i]) ||

             (!isAscending && input[idx - 1] > input[i])) {

            numSeq += DetectAscendingOrDescendingSequence(input,

                input_size,

                i + 1,

                isAscending,

                m - 1,

                cacheAscending,

                cacheDescending);

        }

    }

    // cache the result

    if (isAscending) {

        cacheAscending.insert(std::make_pair(HashKey{ idx, m }, numSeq));

    }

    else {

        cacheDescending.insert(std::make_pair(HashKey{ idx, m }, numSeq));

    }

    return numSeq;

}

template <typename T>

int GetDiffOfAscendingAndDescedningSequence(const std::vector<T> &input, size_t m)

{

    if (m < 2) {

        throw InvalidParamException("The length of sequence MUST be >= 2.");

    }

    if (input.empty()) {

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

    }

    const size_t INPUT_LEN = input.size();

    if (INPUT_LEN < m) {

        throw InvalidParamException("The length of sequence must be <= the length of input array.");

    }

    int numOfAscending = 0;

    int numOfDescening = 0;

    bool isAscending;

    int temp;

    HashMap CacheAscendingSeq;

    HashMap CacheDescedningSeq;

    for (size_t idx1 = 0; idx1 <= INPUT_LEN - m; ++idx1) {

        for (size_t idx2 = idx1 + 1; idx2 <= (INPUT_LEN - m + 1); ++idx2) {

            // First two digits in the sequence to decide ascending/descending

            isAscending = input[idx1] < input[idx2];

            temp = DetectAscendingOrDescendingSequence(input,

                                                       INPUT_LEN,

                                                       idx2 + 1,

                                                       isAscending,

                                                       m - 2,

                                                       CacheAscendingSeq,

                                                       CacheDescedningSeq);

            if (isAscending) {

                numOfAscending += temp;

            }

            else {

                numOfDescening += temp;

            }

        }

    }

    return numOfAscending - numOfDescening;

}

// ********************************************************************************

// Test

// ********************************************************************************

#include <cassert>

void TestFindDiffOfAscAndDescSeq()

{

    {

        bool exceptionCaught = false;

        try {

            const std::vector<int> input;

            GetDiffOfAscendingAndDescedningSequence(input, 2);

        }

        catch (const InvalidParamException &e) {

            exceptionCaught = true;

        }

        catch (...)

        {

        }

        assert(exceptionCaught == true);

        exceptionCaught = false;

        try {

            const std::vector<int> input = { 1, 2, 3 };

            GetDiffOfAscendingAndDescedningSequence(input, 1);

        }

        catch (const InvalidParamException &e) {

            exceptionCaught = true;

        }

        catch (...)

        {

        }

        assert(exceptionCaught == true);

        exceptionCaught = false;

        try {

            const std::vector<int> input = { 1, 2, 3 };

            GetDiffOfAscendingAndDescedningSequence(input, 4);

        }

        catch (const InvalidParamException &e) {

            exceptionCaught = true;

        }

        catch (...)

        {

        }

        assert(exceptionCaught == true);

        exceptionCaught = false;

        try {

            const std::vector<int> input = { 1, 2, 3 };

            GetDiffOfAscendingAndDescedningSequence(input, 1);

        }

        catch (const InvalidParamException &e) {

            exceptionCaught = true;

        }

        catch (...)

        {

        }

        assert(exceptionCaught == true);

    }

    {

        const std::vector<int> input = { 1, 2, 3, 4, 5, 6, 7, 8 };

        assert(GetDiffOfAscendingAndDescedningSequence(input, 2) == 28);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 3) == 56);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 4) == 70);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 5) == 56);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 6) == 28);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 7) == 8);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 8) == 1);

    }

    {

        const std::vector<int> input = { 8, 7, 6, 5, 4, 3, 2, 1 };

        assert(GetDiffOfAscendingAndDescedningSequence(input, 2) == -28);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 3) == -56);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 4) == -70);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 5) == -56);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 6) == -28);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 7) == -8);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 8) == -1);

    }

    {

        const std::vector<int> input = { 8, 7, 6, 5, 4, 3, 2, 1, 11, 12, 13, 14, 15, 16, 17, 18 };

        assert(GetDiffOfAscendingAndDescedningSequence(input, 2) == 8*8); 

        assert(GetDiffOfAscendingAndDescedningSequence(input, 3) == 8*28); 

        assert(GetDiffOfAscendingAndDescedningSequence(input, 4) == 8*56);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 5) == 8*70);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 6) == 8*56);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 7) == 8*28);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 8) == 8*8);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 9) == 8);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 10) == 0);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 11) == 0);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 12) == 0);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 13) == 0);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 14) == 0);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 15) == 0);

        assert(GetDiffOfAscendingAndDescedningSequence(input, 16) == 0);

    }

}