Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
Java code with O(n) performance
class City {
private final int population;
private final List<City> neighbors;
// this is to cache the calculated traffic value from this city to a neighbor city
private final Map<City, Integer> trafficCache;
public City(int population) {
this.population = population;
neighbors = new ArrayList<City>();
trafficCache = new HashMap<City, Integer>();
}
/**
* traffic from this city to city c
*/
private int trafficTo(City c) {
if (!neighbors.contains(c)) {
return 0;
}
// if we already calculated the value, return it immediately
if (trafficCache.contains(c)) {
return trafficCache.get(c);
}
// sum of all traffic from neighbors(except c) + pop. of this city
int traffic = 0;
for(City n: neighbors) {
if (n == c) { continue;}
traffic += n.trafficTo(this);
}
traffic += this.population;
// save the result for later use
trafficCache.put(c, traffic);
return traffic;
}
/**
* maximum traffic expected for this city
*/
int maximumTraffic() {
int maximum = 0;
// this is simply the maximum among traffic from neighbors
for(City n: neighbors) {
int traffic = n.trafficTo(this);
if (traffic > maximum) maximum = traffic;
}
return maximum;
}
}
EDIT: This solution is O(n^2). I didn't correctly read the problem before coding it. mrsurajpoudel.wordpress.com's answer is correct.
Pretty straightforward using recursion. There's two situations for a city:
1. If the game is at the city, get the maximum out of all of your neighbors.
2. If the game is at another city, get the sum of all of your neighbors not in the direction of the game and yourself. Return that sum to the neighbor in the direction of the game.
Swift 2.2
class City {
var pop: Int
var neighbors: [City]
init() {
self.pop = 0
self.neighbors = []
}
init(pop: Int) {
self.pop = pop
self.neighbors = []
}
init(pop: Int, neighbors: [City]) {
self.pop = pop
self.neighbors = neighbors
}
}
func getMaxTraffic(city: City, gameCity: City) -> Int {
var total = 0
if (city.pop == gameCity.pop) {
// If the game is at our city, get get the largest neighbor.
for neigh in city.neighbors {
total = max(getMaxTraffic(neigh, gameCity: city), total)
}
} else {
// If game is in another city, add all other traffic including ourself.
for neigh in city.neighbors {
if (neigh.pop != gameCity.pop) {
total += getMaxTraffic(neigh, gameCity: city)
}
}
total += city.pop
}
return total
}
func getAllTraffic(cities: [City]) {
print("Cities: ")
for city in cities {
print("\(city.pop), \(getMaxTraffic(city, gameCity: city))")
}
}
// First example
var city5 = City(pop: 5)
var city1 = City(pop: 1, neighbors: [city5])
var city2 = City(pop: 2, neighbors: [city5])
var city3 = City(pop: 3, neighbors: [city5])
var city4 = City(pop: 4, neighbors: [city5])
city5.neighbors = [city1, city2, city3, city4]
getAllTraffic([city1, city2, city3, city4, city5]) // tested and works
// Second example
var city7 = City(pop: 7, neighbors: [city2])
var city15 = City(pop: 15, neighbors: [city2])
city2.neighbors = [city5, city7, city15]
getAllTraffic([city1, city2, city3, city4, city5, city7, city15]) // tested and works
@helloru your solution isO(n^2) as is. Also, it fails in some cases if cities have the same population.
I'll admit that I missed that tidbit when I read over it. But even then so, it doesn't really seem possible to do it in O(n) time. Only thing I can think of us pre-processing with a hash map so that getMaxTraffic runs in constant time. Pre-processing will take O(n^2) time, though. Bottom line, in order to determine the max traffic for a city, you NEED to check the other cities, and you just can't do that in O(1) time.
And yes, we can add some identifiers to ensure the cities are unique regardless of population. But for this problem, I made the assumption that the populations were unique. Something that you obviously want to ask your interviewer about.
@helloru The first solution by @mrsurajpoudel.wordpress.com is clearly O(n). Pretty smart solution.
A working solution in Python:
import itertools
class Node:
def __init__(self, pop, nbrs = []):
self.pop = pop
self.nbrs = nbrs
self.cnt = None #Stores the population count of all cities not including previous city
def count(self, exclude):
if self.cnt is None:
self.cnt = self.pop
for nbr in self.nbrs:
if nbr is not exclude:
self.cnt += nbr.count(self)
return self.cnt
def countTraffic(self, out, exclude, excl_count):
count = excl_count
max_t = count
for nbr in self.nbrs:
if nbr is not exclude:
curr = nbr.count(self)
max_t = max(max_t, curr)
count += curr
out[self] = max_t
count += self.pop
for nbr in self.nbrs:
if nbr is not exclude:
nbr.countTraffic(out, self, count - nbr.count(self))
def countTraffic(cities):
out = dict()
for city in cities:
if city not in out:
city.countTraffic(out, None, 0)
return out
A solution in Python is listed below. Runs in O(N) time and space.
import itertools
class Node:
def __init__(self, pop, nbrs = []):
self.pop = pop
self.nbrs = nbrs
self.cnt = None #Stores the population count of all cities not including previous city
def count(self, exclude):
if self.cnt is None:
self.cnt = self.pop
for nbr in self.nbrs:
if nbr is not exclude:
self.cnt += nbr.count(self)
return self.cnt
def countTraffic(self, out, exclude, excl_count):
count = excl_count
max_t = count
for nbr in self.nbrs:
if nbr is not exclude:
curr = nbr.count(self)
max_t = max(max_t, curr)
count += curr
out[self] = max_t
count += self.pop
for nbr in self.nbrs:
if nbr is not exclude:
nbr.countTraffic(out, self, count - nbr.count(self))
def countTraffic(cities):
out = dict()
for city in cities:
if city not in out:
city.countTraffic(out, None, 0)
return out
public static class City{
private String name;
private int population;
private List<City> neighbors = new ArrayList<City>();
public City(String name, int population) {
super();
this.name = name;
this.population = population;
}
public static void addaddNeighborPair(final City c1, final City c2){
c1.addNeighbor(c2);
c2.addNeighbor(c1);
}
public void addNeighbor(City city){
this.neighbors.add(city);
}
public int getPopulation() {
return population;
}
public void setPopulation(int population) {
this.population = population;
}
public List<City> getNeighbors() {
return neighbors;
}
public void setNeighbors(List<City> neighbors) {
this.neighbors = neighbors;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
public static int getMaxTraffic(City city){
int max = 0;
for( City c : city.neighbors){
max = Math.max(max, get(city, c));
}
return max;
}
public static int get(City gameCity, City city){
int traffic = city.population;
for(City neighbor : city.getNeighbors()){
if( gameCity != neighbor ){
traffic += get(city, neighbor);
}
}
return traffic;
}
My python solution:
import sys
class GraphNode:
def __init__(self, V):
self.value = V
self.neighbors = []
def Traffic(n, node):
total = node.value
for neighbor in node.neighbors:
if neighbor == n:
continue
total += Traffic(node,neighbor)
return total
def maxTraffic(graph):
result = {}
for node in graph:
Max = -sys.maxsize
for neighbor in node.neighbors:
#total = 0
total = Traffic(node,neighbor)
Max = max(Max,total)
result[node.value] = Max
return result
if __name__ == '__main__':
gn1 = GraphNode(1)
gn2 = GraphNode(2)
gn3 = GraphNode(3)
gn4 = GraphNode(4)
gn5 = GraphNode(5)
gn7 = GraphNode(7)
gn15 = GraphNode(15)
gn1.neighbors.append(gn5)
gn2.neighbors.append(gn5)
gn2.neighbors.append(gn7)
gn2.neighbors.append(gn15)
gn3.neighbors.append(gn5)
gn4.neighbors.append(gn5)
gn5.neighbors.append(gn1)
gn5.neighbors.append(gn2)
gn5.neighbors.append(gn3)
gn5.neighbors.append(gn4)
gn7.neighbors.append(gn2)
gn15.neighbors.append(gn2)
graph = []
graph.append(gn1)
graph.append(gn2)
graph.append(gn3)
graph.append(gn4)
graph.append(gn5)
graph.append(gn7)
graph.append(gn15)
print(maxTraffic(graph))
Here's my solution, it's O(n). I coded it on white board first, took me close to 40 minutes.
struct node {
vector<node*> nbs;
vector<int> traffic; // same len as "nbs", initialized to zero
int population; // >= 1
node(int pop) {
population = pop;
}
};
int dfs(node * n, set<node*> seen) {
int ans = n->population;
for (int i = 0; i < n->nbs.size(); i++) {
if (n->traffic[i] == 0 && !seen.count(n->nbs[i])) {
seen.insert(n->nbs[i]);
n->traffic[i] = dfs(n->nbs[i], seen);
seen.erase(n->nbs[i]);
}
if (!seen.count(n->nbs[i])) {
ans += n->traffic[i];
}
}
return ans;
}
vector<int> solve(vector<node*> graph) {
vector<int> ans(graph.size());
for (int i = 0; i < graph.size(); i++) {
set<node*> seen {graph[i]};
dfs(graph[i], seen);
int res = 0;
for (int a : graph[i]->traffic) {
res = max(res, a);
}
ans[i] = res;
}
return ans;
}
public class MaxCityTraffic {
public static void main(String[] args) {
int[][] adj = {
{1,5},
{2,5},
{3,5},
{4,5}
};
int[][] adj2 = {
{1,5},
{3,5},
{4,5},
{2,5},
{2,7},
{2,15}
};
MaxCityTraffic mc = new MaxCityTraffic();
mc.maxTraffic(adj);
System.out.println();
mc.maxTraffic(adj2);
}
public void maxTraffic(int[][] adj) {
// build Graph
int grandTotal = 0;
int idx = 0;
Map<Integer, Node> nodeMap = new HashMap<>();
for (int i = 0; i < adj.length; i++) {
int n1 = adj[i][0];
int n2 = adj[i][1];
Node node1 = null;
if (!nodeMap.containsKey(n1)) {
node1 = new Node(n1, idx);
grandTotal += n1;
idx++;
} else {
node1 = nodeMap.get(n1);
}
Node node2 = null;
if (!nodeMap.containsKey(n2)) {
node2 = new Node(n2, idx);
grandTotal += n2;
idx++;
} else {
node2 = nodeMap.get(n2);
}
node1.neighbors.add(node2);
node2.neighbors.add(node1);
if (!nodeMap.containsKey(n1)) {
nodeMap.put(n1, node1);
}
if (!nodeMap.containsKey(n2)) {
nodeMap.put(n2, node2);
}
}
// iterate over graph and print maxTraffic for each node
for(Map.Entry<Integer, Node> e : nodeMap.entrySet()) {
System.out.println(e.getKey() + " " + maxTraffic(e.getValue(), grandTotal));
}
}
private int maxTraffic(Node node, int grandTotal) {
if (node.neighbors.size() == 1) { // case of leaf
return grandTotal - node.val;
}
int maxLocal = -1;
for(Node n2: node.neighbors) {
maxLocal = Math.max(maxLocal, sumSubtree(n2, node));
}
return maxLocal;
}
private int sumSubtree(Node root, Node excluded) {
int sum = root.val;
for(Node n2 : root.neighbors) {
if (!n2.equals(excluded)) {
sum += sumSubtree(n2, root);
}
}
return sum;
}
}
class Node {
int i;
int val;
Set<Node> neighbors;
public Node(int val, int i) {
super();
this.i = i;
this.val = val;
this.neighbors = new HashSet<>();
}
}
Use BFS on each neighbor and save the max value from each neighbor we look at.
We can make sure we don't revisit any Vertices by keeping a HashSet of vertices we have seen.
public class GraphSum {
public static class Vertex {
List<Vertex> vertices;
int val;
public Vertex(int val) {
this.val = val;
vertices = new LinkedList<Vertex>();
}
}
public static int maxTraffic(Vertex game) {
if(game == null) return 0;
int max = 0;
HashSet<Vertex> map = new HashSet<Vertex>();
map.add(game);
for(Vertex v: game.vertices) {
max = Math.max(BFSHelp(v, map), max);
}
return max;
}
private static int BFSHelp(Vertex neighbor, HashSet<Vertex> map) {
Queue<Vertex> queue = new LinkedList<Vertex>();
queue.add(neighbor);
int sum = neighbor.val;
while(!queue.isEmpty()) {
Vertex curr = queue.poll();
map.add(curr);
for(Vertex v: curr.vertices) {
if(!map.contains(v)) {
sum += v.val;
queue.add(v);
}
}
}
return sum;
}
public static void main(String[] args) {
Vertex game = new Vertex(5);
game.vertices.add(new Vertex(1));
game.vertices.add(new Vertex(2));
Vertex temp = game.vertices.get(1);
temp.vertices.add(new Vertex(15));
temp.vertices.add(new Vertex(7));
game.vertices.add(new Vertex(3));
game.vertices.add(new Vertex(4));
System.out.println(maxTraffic(game));
}
}
import java.util.*;
public class GraphSum {
public static class Vertex {
List<Vertex> vertices;
int val;
public Vertex(int val) {
this.val = val;
vertices = new LinkedList<Vertex>();
}
}
public static int maxTraffic(Vertex game) {
if(game == null) return 0;
int max = 0;
HashSet<Vertex> map = new HashSet<Vertex>();
map.add(game);
for(Vertex v: game.vertices) {
max = Math.max(BFSHelp(v, map), max);
}
return max;
}
private static int BFSHelp(Vertex neighbor, HashSet<Vertex> map) {
Queue<Vertex> queue = new LinkedList<Vertex>();
queue.add(neighbor);
int sum = neighbor.val;
while(!queue.isEmpty()) {
Vertex curr = queue.poll();
map.add(curr);
for(Vertex v: curr.vertices) {
if(!map.contains(v)) {
sum += v.val;
queue.add(v);
}
}
}
return sum;
}
public static void main(String[] args) {
Vertex game = new Vertex(5);
game.vertices.add(new Vertex(1));
game.vertices.add(new Vertex(2));
Vertex temp = game.vertices.get(1);
temp.vertices.add(new Vertex(15));
temp.vertices.add(new Vertex(7));
game.vertices.add(new Vertex(3));
game.vertices.add(new Vertex(4));
System.out.println(maxTraffic(game));
}
}
===== 1
calculate total weight of graph
==== 2
for(node in Nodes)
{
int traffic;
if(node.isProcessed)
{
traffic = total - node.weight;
}
else
{
node.isVisiting = true;
traffic = Integer.Min;
for(child in node.Children)
{
traffic = Math.Max(traffic, GetWeight(child));
}
}
print("node: %s, maximum traffic: %d", node.id, traffic);
}
private int GetWeight(Node node)
{
if(node.isProcessed)
return node.weight;
node.isVisiting = true;
for(child in node.Children)
{
if(child.isVisiting)
continue;
node.weight += GetWeight(child);
}
node.isProcessed = true;
node.isVisiting = false;
return node.weight;
}
The graph is no cycle so the graph can be viewed as a tree. Suppose that for each node i in the tree, S_i denotes the sum of its descendants. Also suppose that j1, ..., jk denote the index of the children of i. Then, the max traffic value for node i is max (the total sum - S_i, S_j1, S_j2, ..., S_jk). This idea is same as what mrsurajpoudel.wordpress.com proposes in the top with a very clever and consice implementation.
It is to take node-base graph data structure. Take a random vertex as root and populate the traffic of all its children node. At this moment only the root has all children node's traffic populated. The rest nodes have only traffic of parent node not populate. Then the second round is to populate the parent node's traffic. Afterwords find maximal traffic of each node, which is the what we are looking for.
Details: cpluspluslearning-petert.blogspot.co.uk/2016/09/data-structure-and-algorithm-find.html
C++ and Python implementations are provided.
# python unit test
import unittest
from gNodeHelper import gNode
from gNodeHelper import gNodeHelper
class Test_GenerateMaxTraffic(unittest.TestCase):
def test_A(self):
node1 = gNode(1, 1)
node2 = gNode(2, 2)
node3 = gNode(3, 3)
node4 = gNode(4, 4)
node5 = gNode(5, 5)
node1.AppendNeighbour(node5)
node5.AppendNeighbours((node1, node2, node3, node4))
node2.AppendNeighbour(node5)
node3.AppendNeighbour(node5)
node4.AppendNeighbour(node5)
gNodeHelper.GenerateMaxTraffic(node1)
self.assertEqual(node1.maxTraffic, 14)
self.assertEqual(node2.maxTraffic, 13)
self.assertEqual(node3.maxTraffic, 12)
self.assertEqual(node4.maxTraffic, 11)
self.assertEqual(node5.maxTraffic, 4)
def test_B(self):
node1 = gNode(1, 1)
node2 = gNode(2, 2)
node3 = gNode(3, 3)
node4 = gNode(4, 4)
node5 = gNode(5, 5)
node1.AppendNeighbour(node5)
node5.AppendNeighbours((node1, node2, node3, node4))
node2.AppendNeighbour(node5)
node3.AppendNeighbour(node5)
node4.AppendNeighbour(node5)
gNodeHelper.GenerateMaxTraffic(node5)
self.assertEqual(node1.maxTraffic, 14)
self.assertEqual(node2.maxTraffic, 13)
self.assertEqual(node3.maxTraffic, 12)
self.assertEqual(node4.maxTraffic, 11)
self.assertEqual(node5.maxTraffic, 4)
def test_C(self):
node1 = gNode(1, 1)
node2 = gNode(2, 2)
node3 = gNode(3, 3)
node4 = gNode(4, 4)
node5 = gNode(5, 5)
node7 = gNode(7, 7)
node8 = gNode(8, 8)
node15 = gNode(15, 15)
node38 = gNode(38, 38)
node1.AppendNeighbour(node5)
node5.AppendNeighbours((node1, node2, node3, node4))
node2.AppendNeighbours((node5, node7, node15))
node3.AppendNeighbour(node5)
node4.AppendNeighbour(node5)
node7.AppendNeighbours((node2, node8))
node8.AppendNeighbours((node7, node38))
node15.AppendNeighbour(node2)
node38.AppendNeighbour(node8)
gNodeHelper.GenerateMaxTraffic(node1)
self.assertEqual(node1.maxTraffic, 82)
self.assertEqual(node2.maxTraffic, 53)
self.assertEqual(node3.maxTraffic, 80)
self.assertEqual(node4.maxTraffic, 79)
self.assertEqual(node5.maxTraffic, 70)
self.assertEqual(node7.maxTraffic, 46)
self.assertEqual(node8.maxTraffic, 38)
self.assertEqual(node15.maxTraffic, 68)
self.assertEqual(node38.maxTraffic, 45)
def test_D(self):
node1 = gNode(1, 1)
node2 = gNode(2, 2)
node3 = gNode(3, 3)
node4 = gNode(4, 4)
node5 = gNode(5, 5)
node7 = gNode(7, 7)
node8 = gNode(8, 8)
node15 = gNode(15, 15)
node38 = gNode(38, 38)
node1.AppendNeighbour(node5)
node5.AppendNeighbours((node1, node2, node3, node4))
node2.AppendNeighbours((node5, node7, node15))
node3.AppendNeighbour(node5)
node4.AppendNeighbour(node5)
node7.AppendNeighbours((node2, node8))
node8.AppendNeighbours((node7, node38))
node15.AppendNeighbour(node2)
node38.AppendNeighbour(node8)
gNodeHelper.GenerateMaxTraffic(node5)
self.assertEqual(node1.maxTraffic, 82)
self.assertEqual(node2.maxTraffic, 53)
self.assertEqual(node3.maxTraffic, 80)
self.assertEqual(node4.maxTraffic, 79)
self.assertEqual(node5.maxTraffic, 70)
self.assertEqual(node7.maxTraffic, 46)
self.assertEqual(node8.maxTraffic, 38)
self.assertEqual(node15.maxTraffic, 68)
self.assertEqual(node38.maxTraffic, 45)
if __name__ == '__main__':
unittest.main()
// C++ test
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);
}
}
I dont Know why people complicated this solution.The simple solution for this in O(n) is-
#include <iostream>
#include <map>
using namespace std;
int main()
{
int input;
int totaldistance = 0;
int cities[5]={3,8,10,20,15};
cout<<"Enter the city where the match will be happening"<<endl;
cin>>input;
//make the value also the key
map<int,int> distance;
distance.insert(make_pair(3,3));
distance.insert(make_pair(8,8));
distance.insert(make_pair(10,10));
distance.insert(make_pair(20,20));
distance.insert(make_pair(15,15));
//Searching Starts
map<int,int> :: iterator itr;
for(itr = distance.begin();itr!=distance.end();itr++)
{
if(itr->first == input)
{}
else
totaldistance += (itr->second);//Can also sum the key as Key is same as value
}
cout<<"Traffic of all the cities emerging for a match in city "<< input << " is " << totaldistance<<endl;
return 0;
}
I don't Know why people complicated this solution so much.Below is the solution of this in O(n)-
#include <iostream>
#include <map>
using namespace std;
int main()
{
int input;
int totaldistance = 0;
int cities[5]={3,8,10,20,15};
cout<<"Enter the city where the match will be happening"<<endl;
cin>>input;
//make the value also the key
map<int,int> distance;
distance.insert(make_pair(3,3));
distance.insert(make_pair(8,8));
distance.insert(make_pair(10,10));
distance.insert(make_pair(20,20));
distance.insert(make_pair(15,15));
//Searching Starts
map<int,int> :: iterator itr;
for(itr = distance.begin();itr!=distance.end();itr++)
{
if(itr->first == input)
{}
else
totaldistance += (itr->second);//Can also sum the key as Key is same as value
}
cout<<"Traffic of all the cities emerging for a match in city "<< input << " is " << totaldistance<<endl;
return 0;
}
To Print all the cities popuation.Below is the modified solution-
// C++ program to print largest contiguous array sum
/*#include<iostream>
using namespace std;
int maxSubArraySum(int a[], int size)
{
int max_so_far = 0, max_ending_here = 0;
for (int i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
/*Driver program to test maxSubArraySum*/
/*int main()
{
int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(a)/sizeof(a[0]);
int max_sum = maxSubArraySum(a, n);
cout << "Maximum contiguous sum is \n" << max_sum;
return 0;
}
*/
#include <iostream>
#include <map>
using namespace std;
int main()
{
int input;
int totaldistance = 0;
int cities[5]={3,8,10,20,15};
cout<<"Enter the city where the match will be happening"<<endl;
//make the value also the key
map<int,int> distance;
distance.insert(make_pair(3,3));
distance.insert(make_pair(8,8));
distance.insert(make_pair(10,10));
distance.insert(make_pair(20,20));
distance.insert(make_pair(15,15));
//Searching Starts
map<int,int> :: iterator itr;
for(itr = distance.begin();itr!=distance.end();itr++)
{
totaldistance += itr->first; //Take Total sum of the population in the cities traversing every city
}
for(itr = distance.begin();itr!=distance.end();itr++)
{
cout<< itr->first << " " << totaldistance - (itr->first)<<endl; //Subtract the city population where the match is about to happen.
}
return 0;
}
I solved this using DFS.
As far as I have understood this problem, it says that if that for each city, calculate the traffic coming from its neighboring city.
Following is my solution which works in O(n) time and space.
public static void findTrafficDetails(Graph g, int cityNum){
Vertex city = g.findVertex(cityNum);
HashSet<Integer> visited = new HashSet<>();
for(Vertex child: city.adjacencyList){
System.out.print(child + " ");
int val = calculateTraffic(child, visited);
System.out.println(val);
}
}
private static int calculateTraffic(Vertex v, HashSet<Integer> visited) {
visited.add(v.data);
int trafficCount = v.data;
for (Vertex adjacentVertex : v.adjacencyList) {
if (!visited.contains(adjacentVertex.data)) {
trafficCount = trafficCount+ calculateTraffic(adjacentVertex, visited);
}
}
return trafficCount;
}
public static void main(String[] args) {
Graph graph = new Graph();
graph.addEdge(5, 1);
graph.addEdge(5, 2);
graph.addEdge(5, 3);
graph.addEdge(5, 4);
findTrafficDetails(graph, 1);
}
from collections import defaultdict
class City(object):
def __init__(self, population):
self.population = population
def __str__(self):
return str(self.population)
class State(object):
def __init__(self):
self.cities = []
self.roads = defaultdict(list)
def add_cities(self, cities):
self.cities.extend(cities)
def add_road(self, c1, c2):
self.roads[c1].append(c2)
self.roads[c2].append(c1)
def get_max_traffic(self):
cache = dict()
for city in self.cities:
max_traffic = \
max([self.game_day_traffic(nbor, city, cache) \
for nbor in self.roads[city]])
yield str(city) + " " + str(max_traffic)
def game_day_traffic(self, from_city, to_city, cache):
key = (from_city, to_city)
if key not in cache:
cache[key] = from_city.population
for city in self.roads[from_city]:
if city is to_city: continue
else:
cache[key] += \
self.game_day_traffic(city, from_city, cache)
return cache[key]
c1 = City(1)
c2 = City(2)
c3 = City(3)
c4 = City(4)
c5 = City(5)
c7 = City(7)
c15 = City(15)
c8 = City(8)
c38 = City(38)
s = State()
s.add_cities([c1,c2,c3,c4,c5, c7, c15, c8, c38])
s.add_road(c1,c5)
s.add_road(c2,c5)
s.add_road(c4,c5)
s.add_road(c3,c5)
s.add_road(c2,c7)
s.add_road(c2,c15)
s.add_road(c7,c8)
s.add_road(c8,c38)
for max_traffic in s.get_max_traffic() :
print max_traffic
1- do topology sort
// 2- go over the list
// 2.1 - mark as visited
// 2.2 - if has one neighbour then
// 2.2.1 - update beforeMe to be the node population
// 2.2.2 - update max to be total_population - my population
// 2.3 - else:
// 2.3.1 - update beforeMe to be the sum of all the beforeMe of the visited neighbours
// 2.3.2 - update the max to be the maximum between the neighbours' beforeMe and (the total_population - visitorsUntilNow) since it is topological sort and we have another neighbour to visit
the code becomes as follows:
package training;
import java.util.ArrayList;
public class BaseballCity{
public static int id = 1;
public static int totalPopulation = 0;
public boolean isCalculating = false;
public int cityId;
public int population;
public int beforeMe = -1;
public int max = -1;
public ArrayList<BaseballCity> neighbours;
public BaseballCity(int population){
this.population = population;
cityId = id;
id++;
totalPopulation+=population;
neighbours = new ArrayList<>();
}
public void addNeighbour(BaseballCity n){
if(!neighbours.contains(n))
neighbours.add(n);
if(!n.neighbours.contains(n))
n.neighbours.add(this);
}
public ArrayList<BaseballCity> runTopologySort(BaseballCity n, boolean[] visited){
ArrayList<BaseballCity> res = new ArrayList<>();
visited[n.cityId] = true;
for(BaseballCity b : n.neighbours){
if(!visited[b.cityId]){
res.addAll(runTopologySort(b,visited));
}
}
res.add(n);
return res;
}
public void calcVisitors(){
// 1- do topology sort
// 2- go over the list
// 2.1 - mark as visited
// 2.2 - if has one neighbour then
// 2.2.1 - update beforeMe to be the node population
// 2.2.2 - update max to be total_population - my population
// 2.3 - else:
// 2.3.1 - update beforeMe to be the sum of all the beforeMe of the visited neighbours
// 2.3.2 - update the max to be the maximum between the neighbours' beforeMe and (the total_population - visitorsUntilNow) since it is topological sort and we have another neighbour to visit
boolean[] visited = new boolean[id];
ArrayList<BaseballCity> tsorted = runTopologySort(this, visited);
for(BaseballCity b : tsorted){
if(b.neighbours.size() == 1){
b.beforeMe = b.population;
b.max = totalPopulation - b.population;
}else{
int max = 0;
b.beforeMe = b.population;
for(BaseballCity i : b.neighbours){
if(i.beforeMe != -1){
if(i.beforeMe > max){
max = i.beforeMe;
}
b.beforeMe += i.beforeMe;
}
}
int flowFromOtherNodes = totalPopulation -b.beforeMe;
b.max = max > flowFromOtherNodes? max: flowFromOtherNodes;
}
}
}
@Override
public boolean equals(Object o){
return ((BaseballCity)o).cityId == cityId;
}
@Override
public String toString(){
return "city " +cityId + " : " + max;
}
public static void main(String[] args){
BaseballCity b1 = new BaseballCity(7);
BaseballCity b2 = new BaseballCity(2);
BaseballCity b3 = new BaseballCity(15);
BaseballCity b4 = new BaseballCity(1);
BaseballCity b5 = new BaseballCity(5);
BaseballCity b6 = new BaseballCity(3);
BaseballCity b7 = new BaseballCity(7);
BaseballCity b8 = new BaseballCity(4);
BaseballCity b9 = new BaseballCity(3);
//BaseballCity b = new BaseballCity();
b1.addNeighbour(b2);
b2.addNeighbour(b3);
b2.addNeighbour(b5);
b5.addNeighbour(b4);
b5.addNeighbour(b6);
b5.addNeighbour(b8);
b8.addNeighbour(b7);
b8.addNeighbour(b9);
b1.calcVisitors();
boolean[] visited = new boolean[id];
ArrayList<BaseballCity> tsorted = b1.runTopologySort(b1, visited);
for(BaseballCity b : tsorted)
System.out.println(b.toString());
}
}
void setMaxTraffic(List<Node> graph){
int totalTraffic = 0;
for(Node node : graph){
totalTraffic += node.traffic;
}
setMaxTraffic(graph.get(0),null,totalTraffic);
}
private int setMaxTraffic(Node root, Node prevNode, int totalTraffic){
if(root.neighbors.size() == 1 && prevNode != null){
root.maxTraffic = totalTraffic - root.traffic;
return root.traffic;
}
int maxTraffic = 0, allTraffic = 0;
for(Node node : root.neighbors){
if(node == prevNode)continue;
int traffic = setMaxTraffic(node,root,totalTraffic);
allTraffic += traffic;
maxTraffic = Math.max(maxTraffic, traffic);
}
allTraffic += root.traffic;
int prevTraffic = totalTraffic - allTraffic;
maxTraffic = Math.max(maxTraffic, prevTraffic);
root.maxTraffic = maxTraffic;
return allTraffic;
}
class Node{
public List<Node> neighbors = new ArrayList<Node>();
public int traffic;
public int maxTraffic;
}
I am not sure what interviewer was trying to get out from this question. If its only the solution which matters, here is what i will do:
1. Visit all the nodes in the graph once in the beginning or while constructing the graph.
2. When ever queried for the traffic, just subtract the population of the current node from the sum and return the traffic data.
It may sound a very stupid solution, but it resolve the purpose and it work in O(n) time....considering that we have to search the source node which is going to host the game.
UPD: Sorry did not understand task.
Code in Java
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class TestClass{
public static void main(String[] args) {
City c1 = new City(1);
City c2 = new City(2);
City c3 = new City(3);
City c4 = new City(4);
City c5 = new City(5);
City c7 = new City(7);
City c15 = new City(15);
City c8 = new City(8);
City c38 = new City(38);
c1.neighbors.add(c5);
c2.neighbors.add(c5);
c3.neighbors.add(c5);
c4.neighbors.add(c5);
c2.neighbors.add(c7);
c2.neighbors.add(c15);
c5.neighbors.add(c1);
c5.neighbors.add(c3);
c5.neighbors.add(c4);
c5.neighbors.add(c2);
c7.neighbors.add(c2);
c15.neighbors.add(c2);
c8.neighbors.add(c7);
c7.neighbors.add(c8);
c8.neighbors.add(c38);
c38.neighbors.add(c8);
Queue<City> queue = new LinkedList<City>();
int totalPopulation = 0;
for (City c : new City[] { c1, c2, c3, c4, c5, c7, c15, c8 , c38 }) {
totalPopulation += c.population;
if (c.neighbors.size() == 1) {
queue.add(c);
}
}
while (!queue.isEmpty()) {
City c = queue.remove();
int maxPopulation = totalPopulation - c.sumPopulation - c.population;
maxPopulation = maxPopulation > c.maxPopulation ? maxPopulation : c.maxPopulation;
System.out.println(c.population + ":" + maxPopulation);
if (c.neighbors.isEmpty()) {
continue;
}
City linked = c.neighbors.iterator().next();
linked.neighbors.remove(c);
if (linked.neighbors.size()==1) {
queue.offer(linked);
}
linked.maxPopulation = linked.maxPopulation < c.sumPopulation + c.population ? c.sumPopulation
+ c.population : linked.maxPopulation;
linked.sumPopulation += c.population + c.sumPopulation;
}
}
static class City {
int population;
Set<City> neighbors = new HashSet<City>();
// helpers
int maxPopulation;
int sumPopulation;
City(int population) {
this.population = population;
}
}
}
pseudo-code
- mrsurajpoudel.wordpress.com August 10, 2016// preprocess your input graph to the following structure // node -> hash set of neighbors // hash set to enable amortized O(1) deletions vector<unordered_set<int>> topology(n); vector<int> metadata(n); // contains the population count vector<int> current_leaf_set; int global_sum = 0; for each node id i in topology{ if(topology[i].size() == 1 ) current_leaf_set.push_back(i); global_sum += metadata[i]; } int i = 0; vector<int> sum(n), max(n); // initialize them to zero while(i < current_leaf_set.size()){ int node_id = current_leaf_set[i++]; std::cout << node_id << " : " << (std::max( max[node_id], global_sum - metadata[node_id] - sum[node_id] )) << "\n"; if( topology[node_id].size() == 0 ) continue; // Thanks @helloru int next_node = *(topology[node_id].begin()); // will only have one neighbor sum[next_node] += ( metadata[node_id] + sum[node_id]); max[next_node] = std::max( max[next_node], ( metadata[node_id] + sum[node_id]) ); topology[next_node].erase(node_id); if( topology[next_node].size() == 1 ) current_leaf_set.push_back(next_node); }