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

}