Data Structure and Algorithm - Detect Word Permutation

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

A list of words is given and a bigger string given how can we find whether the string is a permutation of the smaller strings.
eg- s= badactorgoodacting dict[]={'actor','bad','act','good'] FALSE
eg- s= badactorgoodacting dict[]={'actor','bad','acting','good'] TRUE
The smaller words themselves don't need to be permuted. The question is whether we can find a ordering of the smaller strings such that if concatenated in that order it gives the larger string
One more constraint - some words from dict[] may also be left over unused

- novicedhunnu September 15, 2016 in India | Report Duplicate | Flag 
".

2. Data Structure and Algorithm
The solution is based on Trie data structure and algorithm. Details refer to my C++ post - Data Structure and Algorithm - Trie.

Pseudo-code:
    1. Save all word into Trie strucutre
    2. Initialize an empty queue/stack (breadth/depth-first search)
    3. Push starting index 0 into queue/stack (search from start of input string in Trie)
    4. Do until queue/stack is empty
        * Take the top value of queue/stack as idx and pop it out
        * Search input string starting from idx in Trie strucuture
            - Push ending index of any valid word starting from idx into queue/stack
            - Return TRUE, if 
                ~ reaching the end of input and 
                ~ having a valid word - [idx, endOfInputString)  in Trie
    5. Return FALSE otherwise

I have implemented this solution in both C++ and Python. The C++ implementation is provided in next section and the Python solution can be found on my Python post, Data Structure and Algorithm - Detect Word Permutation. Trie is a node-based data structure and algorithm. Therefore a recursive and non-recursive solution are implemented.

3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
// PermutationDetector.h
#pragma once

#include <queue>
#include <string>
#include <vector>

struct DictionaryTrie;

class PermutationDetector
{
public:
    PermutationDetector();
    PermutationDetector(const std::vector<std::string> &words);
    ~PermutationDetector();

    void ConstructDict(const std::vector<std::string> &words, const bool appendMode);

    // recursive implementation
    bool IsPermutation_R(const std::string &word) const;
    // non-recursive implementation
    bool IsPermutation(const std::string &word) const;
private:
    bool IsPermutation_R(const std::string &word, std::queue<size_t> &nextSearch) const;
    DictionaryTrie *m_DictRoot;

};

// PermutationDetector.cpp
#include "PermutationDetector.h"
#include "DictionaryTrie.h"

#include <queue>

#include <cassert>

PermutationDetector::PermutationDetector()
    : m_DictRoot(nullptr)
{
}

PermutationDetector::PermutationDetector(const std::vector<std::string> &words)
    : m_DictRoot(nullptr)
{
    ConstructDict(words, false);
}

PermutationDetector::~PermutationDetector()
{
    if (m_DictRoot) {
        DestoryDictionaryTrie(m_DictRoot);
        m_DictRoot = nullptr;
    }
}

void PermutationDetector::ConstructDict(const std::vector<std::string> &words,
                                        const bool appendMode)
{
    if (!appendMode && m_DictRoot) {
        DestoryDictionaryTrie(m_DictRoot);
        m_DictRoot = nullptr;
    }
    if (!m_DictRoot) {
        m_DictRoot = new DictionaryTrie();
    }

    assert(m_DictRoot != nullptr);

    auto&& itEnd = words.rend();
    for (auto&& it = words.rbegin(); it != itEnd; ++it) {
        AddWord(m_DictRoot, it->c_str());
    }
}

bool PermutationDetector::IsPermutation_R(const std::string &word,
                                        std::queue<size_t> &nextSearch) const
{
    if (nextSearch.empty()) {
        return false;
    }

    const size_t startSearchIndex = nextSearch.front();
    const char *startSearchPtr = word.c_str() + startSearchIndex;
    nextSearch.pop();

    DictionaryTrie *tempPtr = m_DictRoot;
    size_t searchedLen = 1;
    while (*startSearchPtr != '\0' && tempPtr) {
        tempPtr = tempPtr->children[*startSearchPtr - 'a'];
        if (tempPtr && tempPtr->str) {
            // found a valid word/permutation and candidate for next search
            nextSearch.push(startSearchIndex + searchedLen);
        }
        ++searchedLen;
        ++startSearchPtr;
    }

    if (*startSearchPtr == '\0' && tempPtr && tempPtr->str) {
        return true;
    }

    // tail recursion
    return IsPermutation_R(word, nextSearch);
}

bool PermutationDetector::IsPermutation_R(const std::string &word) const
{
    if (word.empty()) {
        return false;
    }

    // switch queue/stack for breadth/depth-first search
    std::queue<size_t> nextSearch;
    nextSearch.push(0);
    return IsPermutation_R(word, nextSearch);
}

bool PermutationDetector::IsPermutation(const std::string &word) const
{
    if (word.empty()) {
        return false;
    }

    // switch queue/stack for breadth/depth-first search
    std::queue<size_t> nextSearch;
    nextSearch.push(0);
    while (!nextSearch.empty()) {
        size_t startSearchIndex = nextSearch.front();
        nextSearch.pop();
        const char *searchStartPtr = word.c_str() + startSearchIndex;
        DictionaryTrie *tempPtr = m_DictRoot;
        ++startSearchIndex;
        while (*searchStartPtr != '\0' && tempPtr) {
            tempPtr = tempPtr->children[*searchStartPtr - 'a'];
            if (tempPtr && tempPtr->str) {
                // found a valid word/permutation and candidate for next search
                nextSearch.push(startSearchIndex);
            }
            ++startSearchIndex;
            ++searchStartPtr;
        }
     
        if (*searchStartPtr == '\0' && tempPtr && tempPtr->str) {
            return true;
        }
    }

    return false;
}

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

// Test

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

void Test_PermutationDetector()

{

    PermutationDetector detector({"actor", "bad", "act", "good"});

    assert(detector.IsPermutation("badactorgoodacting") == false);

    assert(detector.IsPermutation_R("badactorgoodacting") == false);

    detector.ConstructDict({"actor", "bad", "acting", "good"}, false);

    assert(detector.IsPermutation("badactorgoodacting") == true);

    assert(detector.IsPermutation_R("badactorgoodacting") == true);

}

Data Structure and Algorithm - Find Path between Sensors

1. Problem Description
This is a Google interview question for software develop engineer from careercup. Here is the original thread,
"
Given a rectangle with top-left(a,b) and bottom-right(c,d) coordinates. Also given some coordinates (m,n) of sensors inside the rectangle. All sensors can sense in a circular region of radius r about their centre (m,n). Total N sensors are given. A player has to reach from left side of rectangle to its right side (i.e. he can start his journey from any point whose y coordinate is b and x coordinate is a<=x<=c. He has to end his journey to any point whose y coordinate is d and x coordinate is a<=x<=c).

Write an algorithm to find path (possibly shortest but not necessary) from start to end as described above.

Note: all coordinates are real numbers

(a,b)
|----------------------------------------------|
|.............................................................|end
|.............................................................|
|start......................................................|
|.............................................................|
|----------------------------------------------|(c,d)

Edit: You have to avoid sensors.
Also u can move in any direction any time.
- ankit3600 June 14, 2016 in India | Report Duplicate | Flag 
".

2. Data Structure and Algorithm
Determine if path exists:
Figure 1 and Figure 2 are talking about vertical path. Figure 1 shows a case of having a vertical path and Figure 2 shows a case of not having a vertical path.

Figure 1: Have a Vertical Path

Figure 2: Does Not Have a Vertical Path

The sensors are merged into sensor ranges if they are crossed with each other. Given a rectangle and sensors in it, there is no vertical path if there exists any merged sensor range that crosses both left and right bounds of the rectangle. And there is no horizontal path if there exists any merged sensor range that crosses both top and bottom bounds of the rectangle.
In Figure 2 sensors, S1, S2, S3, S4, S5, S6 and S7, are merged together and cross both left and right bounds of the rectangle, therefore there is not vertical path. However in Figure 1 there does not exists such sensor range, therefore there are paths cross top and bottom boundary.

Merge sensors as sensor range if they are crossed:
Two sensors are crossed if the distance between their center is not greater than sum of their radius. If two sensors are crossed, they will be merged as a sensor range.
Data structure of Sensor range:
    - A list of sensors which they are crossed
    - Four crosses - each with one boundary of the rectangle (left, right, top and bottom)
        * The crosses are tracked and updated when a new sensor joins
        * If both left and right crosses exist, then there is no horizontal path
        * If both top and bottom crosses, exist, then there is no vertical path

How a new sensor is added:
One sensor and one sensor range are crossed if this sensor is crossed with any sensor consisting of this sensor range.
Check if this new sensor is crossed with any existing sensor ranges.
    - Add a new sensor range (consisting of this single sensor), if not crossed with
       any other sensor range
    - Merge this sensor with all crossed sensor ranges to form a new sensor range
      The new sensor range includes:
          * A list of sensors: this sensor and all sensors consisting of crossed sensor ranges
          * Merge the crosses with rectangle of this sensor and of crossed sensor ranges

Figure 3: Merge Sensors

For example in Figure 3,
    - SR1 (sensor range 1) has one sensor S1
    - SR3 (sensor range 3) has one sensor S3
Now add S2, then S2 crosses with two sensor ranges SR1 and SR3. Then S1, S2 and S3 forms a new sensor range.
And merge the cross of SR1 and SR2 and S2 together,
    - SR1 has top cross [P1, P2]
    - SR3 has top cross [P3, P4]
    - S2 does not cross with rectangle
Then the merged cross is [P1, P4]
    - Lower bound = min(all low bounds)
    - Upper bound = max(all upper bounds)

Corner Case of Merge Crosses:
Figure 4 shows the corner case when detecting vertical path. In this example in Figure 4, SR1 consists of 4 sensors - S1, S2, S3 and S4. SR1 has a merged top cross with rectangle as [P1, P2]. The corner case here is that SR1 also has a valid left cross with rectangle.

Figure 4: Merge Crosses - Corner Case

Therefore any point in the range of [Ps, P1) is not a valid starting point of a vertical path. So SR1 should have a top cross with rectangle of [Ps, P2]. The same as the sensor range at the right bottom corner with a bottom cross of [P1, Pe].

The Path returned:
After senors are merged into sensor ranges, the complement ranges of sensor ranges 4 crosses on rectangle boundaries are populated. For example in Figure 5, P1 and P2 are in complement ranges of top boundary, and P3 and P4 are in the complement ranges of bottom boundary. And combinations of point from complement ranges of top and bottom can form a valid vertical path.

Figure 5: Cross Path

In this implementation it is to find the first complement range of pair (top cross, bottom cross) in vertical path search or (left cross, right cross) in horizontal path search. And then return the mid point of the range.

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

3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <array>
#include <limits>
#include <set>
#include <vector>
#include <cassert>
#include <cmath>
struct Location
{
    Location()
        : x(-1.0)
        , y(-1.0)
    {}
    Location(double x_, double y_)
        : x(x_)
        , y(y_)
    {}
    double x;
    double y;
    static double GetDistance(const Location &l1, const Location &l2) {
        const double deltaX = l1.x - l2.x;
        const double deltaY = l1.y - l2.y;
        return sqrt(deltaX*deltaX + deltaY*deltaY);
    }
    bool operator==(const Location &rhs) const {
        return x == rhs.x && y == rhs.y;
    }
};
struct EdgeCross
{
    EdgeCross()
    {}
    EdgeCross(double lb, double ub)
        : lowerBound(lb)
        , upperBound(ub)
    {}
    inline void SetBounds(double lb, double ub)
    {
        lowerBound = lb;
        upperBound = ub;
    }
    inline void SetLowerBound(double lb)
    {
        lowerBound = lb;
    }
    inline void SetUpperBound(double ub)
    {
        upperBound = ub;
    }
    bool IsValid() const {
        return lowerBound != std::numeric_limits<double>::max() &&
               upperBound != std::numeric_limits<double>::min();
    }
    double lowerBound = std::numeric_limits<double>::max();
    double upperBound = std::numeric_limits<double>::min();
    void MergeBounds(const EdgeCross &rhs)
    {
        SetBounds(std::min(lowerBound, rhs.lowerBound),
                  std::max(upperBound, rhs.upperBound));
    }
    enum EDGE
    {
        LEFT = 0UL,
        TOP,
        RIGHT,
        BOTTOM,
        MAX
    };
    using EdgeCrosses = std::array<EdgeCross, EDGE::MAX>;
};
struct EdgeCrossCmpLess
{
    bool operator() (const EdgeCross *lhs, const EdgeCross *rhs) const {
        return lhs->upperBound < rhs->lowerBound;
    }
};
struct Sensor
{
    Sensor()
    {}
    Sensor(const Location &cnter, double rds)
        : center(cnter)
        , radius(rds)
    {
        assert(radius >= 0.0);
    }
    Location center;
    double radius = 0.0;
    bool Crossed(const Sensor &rhs) const {
        double dist = Location::GetDistance(this->center, rhs.center);
        return dist <= fabs(this->radius + rhs.radius);
    }
    bool CrossedWithHLine(const double Y, EdgeCross& ec) const {
        if (Y >= (center.y - radius) && Y <= (center.y + radius)) {
            const double deltaY = center.y - Y;
            const double deltaX = sqrt(radius*radius - deltaY*deltaY);
            ec.SetBounds(center.x - deltaX, center.x + deltaX);
            return true;
        }
        return false;
    }
    bool CrossedWithVLine(const double X, EdgeCross& ec) const {
        if (X >= (center.x - radius) && X <= (center.x + radius)) {
            const double deltaX = center.x - X;
            const double deltaY = sqrt(radius*radius - deltaX*deltaX);
            ec.SetBounds(center.y - deltaY, center.y + deltaY);
            return true;
        }
        return false;
    }
};
struct SensorRange
{
    SensorRange()
    {}
    EdgeCross::EdgeCrosses edgeCrosses;
    std::vector<const Sensor *> sensors;
    void MergeEdgeCross(const EdgeCross::EdgeCrosses &ecs) {
        for (size_t idx = 0; idx < ecs.size(); ++idx) {
            edgeCrosses[idx].MergeBounds(ecs[idx]);
        }
    }
    void Merge(const SensorRange &sr) {
        MergeEdgeCross(sr.edgeCrosses);
        sensors.insert(sensors.end(), sr.sensors.begin(), sr.sensors.end());
    }
};
struct Rectangle {
    Rectangle()
    {}
    Rectangle(const double l, const double r, const double t, const double b)
    {
        assert(l < r);
        assert(b < t);
        edges[EdgeCross::LEFT] = l;
        edges[EdgeCross::RIGHT] = r;
        edges[EdgeCross::TOP] = t;
        edges[EdgeCross::BOTTOM] = b;
    }
    std::array<double, EdgeCross::MAX> edges;
};
void FindCrossBetweenSensorAndRect(const Sensor &sensor,
                                   const Rectangle &rect,
                                   EdgeCross::EdgeCrosses &edgeCrosses)
{
    for (size_t edge = EdgeCross::LEFT; edge < EdgeCross::MAX; ++edge) {
        if (edge & 1UL) {
            sensor.CrossedWithHLine(rect.edges[edge], edgeCrosses[edge]);
        }
        else {
            sensor.CrossedWithVLine(rect.edges[edge], edgeCrosses[edge]);
        }
    }
}

// Merge sensors into sensor ranges in Figure 3
bool GenerateSenorRangeMap(const std::vector<Sensor> &sensors,
                           const Rectangle &rect,
                           const bool breakIfNoPath,
                           const bool vPath,
                           std::vector<SensorRange> &sensorRanges)
{
    auto itEnd = sensors.cend();
    std::vector<size_t> toMerge;
    for (auto it = sensors.cbegin(); it != itEnd; ++it) {
        const size_t CUR_SIZE = sensorRanges.size();
        toMerge.clear();
        toMerge.reserve(CUR_SIZE);
        // populate all sensor ranges crossed with this sensor
        for (size_t idx = 0; idx < CUR_SIZE; ++idx) {
            auto&& sRange = sensorRanges[idx];
            auto itSenEnd = sRange.sensors.cend();
            for (auto itSen = sRange.sensors.cbegin(); itSen != itSenEnd; ++itSen) {
                if ((*itSen)->Crossed(*it)) {
                    toMerge.push_back(idx);
                    break;
                }
            }
        }
        const SensorRange *workingSR = NULL;
        if (toMerge.empty()) {
            // create a new sensor range if not crossed with any sensor ranges
            SensorRange sr;
            sr.sensors.emplace_back(&(*it));
            FindCrossBetweenSensorAndRect(*it, rect, sr.edgeCrosses);
            sensorRanges.push_back(sr);
            workingSR = &sensorRanges.back();
        }
        else {
            // merge all existing sensor range
            // 1. merge the rest into the first senror range
            // 2. erase the sensor ranges except the very first
            auto itMergeREnd = toMerge.crend() - 1;
            for (auto itMergeR = toMerge.crbegin(); itMergeR != itMergeREnd; ++itMergeR) {
                auto&& sRangeToKeep = sensorRanges[*toMerge.begin()];
                auto&& sRangeToMerge = sensorRanges[*itMergeR];
                sRangeToKeep.Merge(sRangeToMerge);
                sensorRanges.erase(sensorRanges.begin() + *itMergeR);
            }
            // merge with the sensor
            EdgeCross::EdgeCrosses edgeCrosses;
            FindCrossBetweenSensorAndRect(*it, rect, edgeCrosses);
            auto&& sRangeToKeep = sensorRanges[*toMerge.begin()];
            sRangeToKeep.MergeEdgeCross(edgeCrosses);
            sRangeToKeep.sensors.push_back(&(*it));
            workingSR = &sRangeToKeep;
        }
        if (workingSR && breakIfNoPath) {
            if ((vPath &&
                 workingSR->edgeCrosses[EdgeCross::LEFT].IsValid() &&
                 workingSR->edgeCrosses[EdgeCross::RIGHT].IsValid()) ||
                (!vPath &&
                 workingSR->edgeCrosses[EdgeCross::TOP].IsValid() &&
                 workingSR->edgeCrosses[EdgeCross::BOTTOM].IsValid())) {
                    return false;
            }
        }
    }
    return true;
}

// Process the corner case in Figure 4
bool ProcessCornerCase(const bool vPath,
                       const EdgeCross::EdgeCrosses &edgeCrosses,
                       const Rectangle &rect,
                       EdgeCross &edge)
{
    if (edge.IsValid()) {
        if (vPath) {
            // left corner
            if (edgeCrosses[EdgeCross::LEFT].IsValid()) {
                edge.SetLowerBound(rect.edges[EdgeCross::LEFT]);
            }
            // right corner
            if (edgeCrosses[EdgeCross::RIGHT].IsValid()) {
                edge.SetUpperBound(rect.edges[EdgeCross::RIGHT]);
            }
        }
        else {
            // top corner
            if (edgeCrosses[EdgeCross::TOP].IsValid()) {
                edge.SetUpperBound(rect.edges[EdgeCross::TOP]);
            }
            // bottom corner
            if (edgeCrosses[EdgeCross::BOTTOM].IsValid()) {
                edge.SetLowerBound(rect.edges[EdgeCross::BOTTOM]);
            }
        }
        return true;
    }
    return false;
}

using Path = std::array<Location, 2>;
using EdgeCrossSet = std::set<const EdgeCross*, EdgeCrossCmpLess>;
// Get the mid point in Figure 5
bool GetMidPointOfFirstGap(const EdgeCrossSet &ecs,
                           const Rectangle &rect,
                           const bool vPath,
                           double &val)
{
    const double lowerBound = vPath ?
        rect.edges[EdgeCross::LEFT] : rect.edges[EdgeCross::BOTTOM];
    const double upperBound = vPath ?
        rect.edges[EdgeCross::RIGHT] : rect.edges[EdgeCross::TOP];
    if (ecs.empty()) {
        val = (lowerBound + upperBound) / 2;
        return true;
    }
    auto itFirst = ecs.cbegin();
    if ((*itFirst)->lowerBound > lowerBound) {
        val = (lowerBound + (*itFirst)->lowerBound) / 2;
        return true;
    }
    auto itSecond = ++ecs.cbegin();
    if (itSecond == ecs.cend()) {
        if ((*itFirst)->upperBound < upperBound) {
            val = ((*itFirst)->upperBound + upperBound) / 2;
            return true;
        }
        return false;
    }
    if ((*itFirst)->upperBound < (*itSecond)->lowerBound) {
        val = ((*itFirst)->upperBound + (*itSecond)->lowerBound) / 2;
        return true;
    }
    return false;
}

bool FindPath(const std::vector<Sensor> &sensors,
              const Rectangle &rect,
              const bool vPath,
              Path &path)
{
    std::vector<SensorRange> sensorRanges;
    if (!sensors.empty()) {
        // Merge sensors into sensor ranges
        if (!GenerateSenorRangeMap(sensors, rect, true, vPath, sensorRanges)) {
            return false;
        }
    }

    // Check if path exist
    if (sensorRanges.empty()) {
        if (vPath) {
            path[0] = Location{ rect.edges[EdgeCross::LEFT],
                                             rect.edges[EdgeCross::TOP] };
            path[1] = Location{ rect.edges[EdgeCross::LEFT],
                                             rect.edges[EdgeCross::BOTTOM] };
        }
        else {
            path[0] = Location{ rect.edges[EdgeCross::LEFT],
                                             rect.edges[EdgeCross::TOP] };
            path[1] = Location{ rect.edges[EdgeCross::RIGHT],
                                             rect.edges[EdgeCross::TOP] };
        }
        return true;
    }
    EdgeCrossSet ecsFrom;
    EdgeCrossSet ecsTo;
    auto itEnd = sensorRanges.end();
    for (auto it = sensorRanges.begin(); it != itEnd; ++it) {
        // Process the corner case shown in Figure 4
        // And populate the first complement range
        if (vPath && ProcessCornerCase(vPath,
                                       it->edgeCrosses,
                                       rect,
                                       it->edgeCrosses[EdgeCross::TOP])) {
            ecsFrom.insert(&(it->edgeCrosses[EdgeCross::TOP]));
        }
        if (vPath && ProcessCornerCase(vPath,
                                       it->edgeCrosses,
                                       rect,
                                       it->edgeCrosses[EdgeCross::BOTTOM])) {
            ecsTo.insert(&(it->edgeCrosses[EdgeCross::BOTTOM]));
        }
        if (!vPath && ProcessCornerCase(vPath,
                                        it->edgeCrosses,
                                        rect,
                                        it->edgeCrosses[EdgeCross::LEFT])) {
            ecsFrom.insert(&(it->edgeCrosses[EdgeCross::LEFT]));
        }
        if (!vPath && ProcessCornerCase(vPath,
                                        it->edgeCrosses,
                                        rect,
                                        it->edgeCrosses[EdgeCross::RIGHT])) {
            ecsTo.insert(&(it->edgeCrosses[EdgeCross::RIGHT]));
        }
    }
    double valFrom, valTo;
    // Return the path (the mid point of the first complement range pair)
    if (GetMidPointOfFirstGap(ecsFrom, rect, vPath, valFrom) &&
        GetMidPointOfFirstGap(ecsTo, rect, vPath, valTo)) {
        path[0] = vPath ? Location(valFrom, rect.edges[EdgeCross::TOP]) :
                          Location(rect.edges[EdgeCross::LEFT], valFrom);
        path[1] = vPath ? Location(valTo, rect.edges[EdgeCross::BOTTOM]) :
                          Location(rect.edges[EdgeCross::RIGHT], valTo);
        return true;
    }
    return false;
}
// ********************************************************************************
// Test
// ********************************************************************************
void TestFindPathBetweenSensors()
{
    Path path;
    const Rectangle rect = { 1.0, 9.0, 8.0, 1.0 };
    {
        const std::vector<Sensor> sensors{ { { 2.0, 3.0 }, 1.0 },
                                           { { 4.0, 3.0 }, 1.0 },
                                           { { 6.0, 3.0 }, 1.0 },
                                           { { 8.0, 3.0 }, 1.0 }
                                         };
        assert(FindPath(sensors, rect, true, path) == false);
        assert(FindPath(sensors, rect, false, path) == true);
        assert(path.at(0) == Location(1.0, 2.0) && path.at(1) == Location(9.0, 2.0));
    }
    {
        const std::vector<Sensor> sensors{ { { 2.0, 3.0 }, 1.0 },
                                           { { 4.0, 3.0 }, 1.0 },
                                           { { 6.0, 3.0 }, 1.0 },
                                           { { 8.0, 3.0 }, 1.0 },
                                           { { 8.0, 8.0 }, 1.0 },
                                           { { 7.0, 7.0 }, 1.0 }
                                         };
        assert(FindPath(sensors, rect, true, path) == false);
        assert(FindPath(sensors, rect, false, path) == true);
        assert(path.at(0) == Location(1.0, 2.0) && path.at(1) == Location(9.0, 2.0));
    }
    {
        const std::vector<Sensor> sensors{ { { 2.0, 7.2 }, 1.0 },
                                           { { 3.0, 6.0 }, 1.0 },
                                           { { 4.0, 4.5 }, 1.0 },
                                           { { 8.0, 7.2 }, 1.0 },
                                           { { 7.0, 6.2 }, 1.0 },
                                           { { 2.0, 3.0 }, 1.0 },
                                           { { 3.0, 4.0 }, 1.0 },
                                           { { 9.0, 1.0 }, 1.0 }
                                         };
        assert(FindPath(sensors, rect, true, path) == true);
        assert(path.at(0) == Location(5.0, 8.0) && path.at(1) == Location(4.5, 1.0));
        assert(FindPath(sensors, rect, false, path) == true);
        assert(path.at(0) == Location(1.0, 2.0) && path.at(1) == Location(9.0, 4.6));
    }
}

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