C++: 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:

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

C++

Sunday 18 September 2016

Data Structure and Algorithm - Find the Maximal Traffic between Cities

No comments:

Post a Comment

Blog Archive