Sunday, 18 September 2016

Data Structure and Algorithm - Find the Maximal Traffic between Cities

1. Problem Description:
This is a Google interview question for software engineer/developer from careercup. Here is the original thread,
"
You are given a graph with no cycles, each node representing different cities and there are stadiums for baseball games in all cities.

Each node contains a value representing the population of the city, and a list of neighbors. (feel free to extend data structure)

Every time there is a baseball game at a city, everyone from all the different cities will go to the city with the baseball game.

Return the maximum traffic between a city and its neighbours when there is a game at that city, for all cities. (Does not have to be sorted)

The total run-time after returning everything should be O(n).

Examples:
Input:
1   2
 \ /
  5
 / \
4   3
Output:
1 14
2 13
3 12
4 11
5 4

Input:
         38
         /
        8
        /
      7
     /
1   2
 \ / \
  5   15
 / \
4   3
Output:
1 82
2 53
3 80
4 79
5 70
7 46
15 68
8 38
38 45
- djway August 10, 2016 in United States | Report Duplicate | Flag 
".

2. Data Structure and Algorithm
It is a graph problem. The data structure is that each vertex has a hash map with adjacent neighbor ID as key and its traffic as the value.

Pseudo-code:
    - Take any node as root (in Figure 1 vertex 5 as root)
    - First round:populate traffic of children nodes
        * Return the traffic of its own if it is a leaf node
        * Otherwise return the sum of traffic of itself and all its sub-graph
           For instance Node 5's child Node 2
                        Node 2 has two children
                             Node 7 has total traffic 53
                             Node 15 has total traffic 15
                        Then in Node 5, its child Node 2:
                             All children nodes of Node 2 have traffic: 53 + 15 = 68
                             Node 2 traffic in Node 5: 68 + 2 (Node 2's traffic) = 70
           (Values are populated as black ink in Figure 1)
    - Second round: populate the traffic of parent node
        * Root Node - vertex 5, has all children node traffic populated)
        * Value = Sum of traffic of all children nodes of it parent node
                         + traffic of its parent node
                         - traffic of itself to its parent
           For instance: Node 2 and its parent Node 5
                         All the traffic of children of Node 5: 70 + 1+ 3 + 4 = 78
                         Traffic of parent Node 5: 5
                         Traffic of Node 2 to parent Node 5: 70
                         Then update Node 2's parent Node 5: 78 + 5 - 70 = 13
                         ( As populated in blue ink and underlined in Figure 1)
    - Third round: populate the max traffic in its neighbors for each vertex.
        (As populated in red ink in Figure 1)

Figure 1: Data Structure and Algorithm

I have implemented this solution in two languages. The C++ implementation is provided in the next section and a Python implementation is on my Python post.

3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <algorithm>
#include <limits>
#include <memory>
#include <unordered_map>

struct gNode
{
    using NeighbourNodes = std::unordered_map<gNode*, size_t>;
    gNode(size_t i, size_t t)
        : id(i)
        , traffic(t)
    {}

    void AppendNeighbour(gNode* neighbour)
    {
        neighbours.insert(std::make_pair(neighbour, 0));
    }

    void AppendNeighbours(const std::vector < gNode* > ns)
    {
auto itEnd = ns.cend();
for (auto it = ns.cbegin(); it != itEnd; ++it) {
            AppendNeighbour(*it);
}
    }

    size_t id;
    size_t traffic;
    NeighbourNodes neighbours;
    size_t maxTraffic = 0;
    size_t sumOfNeighboursTraffic = 0;
};

size_t CalculateNeighboursTraffic(gNode* root, const gNode* parent)
{
    if (!root) {
        return 0;
    }

    if (root->neighbours.size() == 1 && parent) {
        return root->traffic;
    }

    auto itEnd = root->neighbours.end();
    size_t traffic = 0;
    for (auto it = root->neighbours.begin(); it != itEnd; ++it) {
        if (!parent || it->first->id != parent->id) {
            it->second = CalculateNeighboursTraffic(it->first, root);
            traffic += it->second;
        }
    }
    return traffic + root->traffic;
}

void CalculateParentTraffic(gNode *root, const gNode *parent)
{
    if (!root) {
        return;
    }
    if (parent) {
        const auto itFound = parent->neighbours.find(root);
        assert(itFound != parent->neighbours.end());
        auto rootItFound = root->neighbours.find(const_cast<gNode*>(parent));
        assert(rootItFound != root->neighbours.end());
        rootItFound->second = parent->sumOfNeighboursTraffic
                                              + parent->traffic - itFound->second;
    }

    auto itEnd = root->neighbours.cend();
    for (auto it = root->neighbours.cbegin(); it != itEnd; ++it) {
        root->sumOfNeighboursTraffic += it->second;
    }

    for (auto it = root->neighbours.begin(); it != itEnd; ++it) {
        if (!parent || it->first != parent) {
           CalculateParentTraffic(it->first, root);
        }
    }
}

void PopulateMaxTraffic(gNode *root, const gNode *parent)
{
    if (!root) {
        return;
    }

    const auto itEnd = root->neighbours.cend();
    for (auto it = root->neighbours.cbegin(); it != itEnd; ++it) {
        if (root->maxTraffic < it->second) {
            root->maxTraffic = it->second;
        }
    }

    for (auto it = root->neighbours.begin(); it != itEnd; ++it) {
        if (!parent || it->first != parent) {
            PopulateMaxTraffic(it->first, root);
        }
    }
}

void GenerateMaxTraffic(gNode* node)
{
    CalculateNeighboursTraffic(node, 0);

    CalculateParentTraffic(node, 0);

    PopulateMaxTraffic(node, 0);
}

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


Wednesday, 10 August 2016

Data Structure and Algorithm - Find Sub-array with Sum in Given Range

1. Problem Description
This is a Google interview question for software engineers from careercup. Here is the original description from the thread,
"
Write a function that takes as input an array of integers A, and two integers low and high.

Your function has to output pairs of indices: {(i,j), ...}

Where each pair of indices denotes that the subarray of A[i...j] has a sum in the range low <= sum <= high.

Apparently there are algorithms better than O(N^2).
- / July 31, 2016 in United States | Report Duplicate | Flag 
".

2. Data Structure and Algorithm
Given a list of input, then the all the sums of sub-arrays staring from the first element can be constructed. Sort sums and find the sub-arrays with sum in range of lower and upper bounds. From now on the idea is not to construct the sums array of starting from the second element and so on. Because it can be deduced from the sum array from the first element.
Given lower bound LB, upper bound UB and an input array a1, a2, ..., an, assume that the sum array of the first element is s1, s2, s3, ..., sn, then the sum array of the second element is s2-a1, s3- a1, ..., sn - a1 then find LB and UB in sorted array of s2-a1, s3-a2, ..., sn-a1. Instead of constructing the new sum array of (s2-a1, s3-a1, ..., sn-a1) and searching LB and UB, search the updated bounds of LB+a1 and UB+a1 in sorted array of s2, s3, ..., sn.
In this way the sum array is only need to construct once and all the rest of searches are binary for each element in the input array.

Pseudo-code:
Given an input array A - a1, a2, ..., an, upper bound LB and upper bound UB,   
    1. Initialize the sums of sub-arrays starting with a1 as S with the following structure
        - Sum of subarray from a1 to aj, where j in [1, n], and the ending index (endIdx)
        - (s1, endIdx1) = (a1, 1)
        - (s2, endIdx2) = (a1 + a2, 2)
        - (s3, endIdx3) = (a1 + a2 + a3, 3)
        ......
        - (sn, endIdxn) = (a1 + a2 + ...... + an, n)
    2. Sort S as SortedS with the following less comparator (in std::set)
        - Return true, if si < sj
        - Return true, if si == sj and i < j
        - Return false otherwise
        , where si is the LHS and sj is the RHS
    3. Loop from start to end in A with startIdx = 0
        - Find lower bound of (LB, 0) in SortedS as lbIt
        - Find upper bound of (UB, n+1) in SortedS as ubIt
        - For each element resultIt in [lbIt, ubIt),
            * Save pair (startIdx, resultIt->endIdx)
        - LB = LB + A[startIdx]
        - UB = UB + A[startIdx]
        - Rememove S[startIdx] from SortedS

Complexity:
    - O(NlogN) computation complexity
    - O(N) space complexity

3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <set>
#include <tuple>
#include <vector>
struct SumAndEndIndex{
    SumAndEndIndex()
        : sum(0.0)
        , index(0)
    {}
    SumAndEndIndex(const double s, const size_t i)
        : sum(s)
        , index(i)
    {}
    double sum;
    size_t index;
};
struct SumAndEndIndexCmpLess
{
    bool operator()(const SumAndEndIndex *lhs,
                    const SumAndEndIndex *rhs) const
    {
        return lhs->sum < rhs->sum ||
            (lhs->sum == rhs->sum && lhs->index < rhs->index);
    }
};
using SumAndEndIndexVec = std::vector<SumAndEndIndex>;
using SumAndEndIndexSet = std::set<const SumAndEndIndex*, SumAndEndIndexCmpLess>;
void CreateSumAndEndIndexVec(const std::vector<double> &input,
                             SumAndEndIndexVec &seiv)
{
    if (input.empty()) {
        SumAndEndIndexVec().swap(seiv);
        return;
    }
    SumAndEndIndexVec tempVec;
    tempVec.reserve(input.size());
    auto itEnd = input.cend();
    double sum = 0;
    size_t index = 0;
    for (auto it = input.cbegin(); it != itEnd; ++it, ++index) {
        sum = sum + *it;
        tempVec.push_back(SumAndEndIndex(sum, index));
    }
    tempVec.swap(seiv);
}
using PairResultVect = std::vector<std::tuple<size_t, size_t>>;
PairResultVect FindSubArrayWithSumInRange(const std::vector<double> &input,
                                          const double lowerBound,
                                          const double upperBound,
                                          const SumAndEndIndexVec &sumAndIndexVec,
                                          SumAndEndIndexSet &sortedSumAndIndices)
{
    PairResultVect result;
    auto itEnd = input.cend();
    SumAndEndIndex seiLB(lowerBound, 0);
    SumAndEndIndex seiUB(upperBound, input.size());
    size_t startIndex = 0;
    auto itVec = sumAndIndexVec.cbegin();
    for (auto it = input.cbegin(); it != itEnd; ++it, ++startIndex, ++itVec) {
        auto lbIt = sortedSumAndIndices.lower_bound(&seiLB);
        auto ubIt = sortedSumAndIndices.upper_bound(&seiUB);
        for (auto foundIt = lbIt; foundIt != ubIt; ++foundIt) {
            result.push_back(std::make_tuple(startIndex, (*foundIt)->index));
        }
        seiLB.sum += *it;
        seiUB.sum += *it;
        sortedSumAndIndices.erase(&(*itVec));
    }
    return result;
}
PairResultVect FindSubArrayWithSumInRange(const std::vector<double> &input,
                                          const double lowerBound,
                                          const double upperBound)
{
    if (input.empty() || lowerBound > upperBound) {
        return PairResultVect();
    }
    SumAndEndIndexVec sumAndIndexVec;
    CreateSumAndEndIndexVec(input, sumAndIndexVec);
    SumAndEndIndexSet sortedSumAndIndices;
    auto itEnd = sumAndIndexVec.cend();
    for (auto it = sumAndIndexVec.cbegin(); it != itEnd; ++it) {
        sortedSumAndIndices.insert(&(*it));
    }
    return FindSubArrayWithSumInRange(input,
                                      lowerBound,
                                      upperBound,
                                      sumAndIndexVec,
                                      sortedSumAndIndices);
}

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

Sunday, 31 July 2016

Dynamic Programming - Pick Maximal Coins

1. Problem Description
This is a Facebook interview question for software developers from careercup. Here is the original thread,
"
There are N coins with coordinates (x, y) where x >0 and y >0
You start at (0, 0) and you can only do steps of form (dx, dy) where dx >0 and dy > 0
Print the maximum number of coins that you can collect.

Clarification: you can do as many moves as you wish, the point is to collect maximum number of coins. If you are located at position (a, b) you may jump to position (a+dx, b+dy) for all dx > 0 and dy > 0

@krbchd: Your algorithm may output incorrect values. Suppose there are points (5, 7), (5, 8), (5, 9) for y coordinates LIS will output 7, 8, 9, however since these points are on the same x axis, you can choose only one of them.
- emb April 02, 2016 in United States | Report Duplicate | Flag  ".

2. Sub-problem
It is a optimization problem to find the maximal possible coins that a path can collect coins. 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]

As the problem stated that the path has to be in strictly ascending order. Path P (Ca, Cb, ..., Cm) has to meet the pre-condition of (Xa, Ya) < (Xb, Yb) < ... < (Xm, Ym), where operator "<" means that Xa < Xb and Ya < Yb for instance.
Therefore f(C1, ..., Ci-1, Ci+1, Cn) can be limited to coins that are greater than Ci,
    - f(C1, ..., Ci-1, Ci+1, Cn) = f(CollectionOfConis > Ci).
    - f(C1, ..., Cn) = max(1 + f(CollectionOfCoins > Ci) where i with range of [1, n]

Again caching technique is used in this case as the searching along the paths, the result is cached to avoid the duplicate calculation.

3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <unordered_map>
#include <vector>
struct Position
{
    Position()
        : x(0.0)
        , y(0.0)
    {}
    Position(double _x, double _y)
        : x(_x)
        , y(_y)
    {}
    double x;
    double y;
    bool operator >(const Position &rhs) const {
        return x > rhs.x && y > rhs.y;
    }
    bool operator <(const Position &rhs) const {
        return x < rhs.x && y < rhs.y;
    }
    bool operator ==(const Position &rhs) const {
        return x == rhs.x && y == rhs.y;
    }
};

struct PositionHashFunc
{
    size_t operator()(const Position &p) {
        return std::hash<double>()(p.x) ^ std::hash<double>()(p.y);
    }
    bool operator ()(const Position &lhs, const Position &rhs) const {
        return lhs == rhs;
    }
};

std::vector<size_t> FindLargerPositions(const std::vector<Position> &input,
                                        const Position &pivotal)
{
    auto itEnd = input.end();
    size_t index = 0;
    std::vector<size_t> result;
    result.reserve(input.size());
    for (auto it = input.begin(); it != itEnd; ++it, ++index) {
        if (it->operator>(pivotal)) {
            result.push_back(index);
        }
    }
    return result;
}

std::vector<size_t> FindLargerPositions(const std::vector<Position> &input,
                                        const std::vector<size_t> &searchIn,
                                        const Position &pivotal)
{
    std::vector<size_t> result;
    result.reserve(searchIn.size());
    auto itEnd = searchIn.end();
    for (auto it = searchIn.begin(); it != itEnd; ++it) {
        auto&& tempPos = input[*it];
        if (tempPos.operator>(pivotal)) {
            result.emplace_back(*it);
        }
    }
    return result;
}

using HashMap = std::unordered_map<Position, size_t, PositionHashFunc, PositionHashFunc>;

size_t PickMaximalCoins_R(const std::vector<Position> &coins,
                          const std::vector<size_t> &subProbelm,
                          const Position &pivotal,
                          HashMap &hash)
{
    if (subProbelm.empty()) {
        return 0;
    }
    auto it = hash.find(pivotal);
    if (it != hash.end()) {
        return it->second;
    }
    size_t maximal = 0;
    auto itEnd = subProbelm.end();
    for (auto it = subProbelm.begin(); it != itEnd; ++it) {
        auto& position = coins[*it];
        const std::vector<size_t> subproblem = FindLargerPositions(coins, subProbelm, position);
        const size_t temp = 1 + PickMaximalCoins_R(coins, subproblem, position, hash);
        if (maximal < temp) {
            maximal = temp;
        }
    }
    hash[pivotal] = maximal;
    return maximal;
}

size_t PickMaximalCoins_R(const std::vector<Position> &coins)
{
    if (coins.empty()) {
        return 0;
    }
    HashMap hm;
    size_t maximal = 0;
    auto itEnd = coins.end();
    for (auto it = coins.begin(); it != itEnd; ++it) {
        const std::vector<size_t> subProblem = FindLargerPositions(coins, *it);
        const size_t temp = 1 + PickMaximalCoins_R(coins, subProblem, *it, hm);
        if (maximal < temp) {
            maximal = temp;
        }
    }
    return maximal;
}

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

Wednesday, 22 June 2016

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.

Thursday, 16 June 2016

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

Thursday, 2 June 2016

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