Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
4
of 4 vote

pseudo-code

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

- mrsurajpoudel.wordpress.com August 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

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

- jjongpark August 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just a clarification on the O for this solution. Is this O(n) or O(n2) since for loop also does a recursion within it. Just wondering ...

- Manoj April 23, 2019 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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 August 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@helloru your solution isO(n^2) as is. Also, it fails in some cases if cities have the same population.

- Anonymous August 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 August 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@helloru The first solution by @mrsurajpoudel.wordpress.com is clearly O(n). Pretty smart solution.

- TryToCode August 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@helloru The first solution is in O(n). Its pretty smart solution as well.

- Anonymous August 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You're right. mrsurajpoudel.wordpress.com has a tough, yet correct solution. Only minor issue is that the last node added to the leaf set will not have any neighbors, so a check should be placed. I've upvoted it.

- helloru August 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I can do it in O(n) when getting the max traffic flow for every city in one game city scenario. For instance, if game city is 1, then i would get the following: City1 = 14, City2 = 0, City3 = 0, City4 = 0, City5 = 9

How do you cover all cities in O(n) ?

- eckstar August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ben August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- Ben August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How is this O(n)? For each city (O(n)), you have to check all of it's neighbors (O(n)). That's O(n^2).

- helloru August 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sankingshi August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the gamecity only has one neighbor, the total traffic should be the summary of all other city's population.
If the gamecity have more than one neighbors, to calculate the summary of population of every neighbor sub tree, then find the max one as the return.

- sankingshi August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- flygan1988 August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- guilhebl August 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can someone explain the solution

- P G August 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

did you really get this question?

- tangolingo August 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

did you really get this question?

- tangolingo August 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

    }
}

- Tofurk3y August 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

    }
}

- Tofurk3y August 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Natalia Zelenskaya August 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe the example input given is a bit too simplistic to have an idea as to how to solve the problem:

This would be better input:

38
/
8
/
7
/
1 2
\ / \
5 15
/ \
4 3

- Vistian August 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe the example input given is a bit too simplistic to have an idea as to how to solve the problem correctly. You need to have internal nodes whose children aren't adjacent to external nodes.

This would be better input:

38
           /
         8
        /
      7
     /
1   2
 \ / \
  5   15
 / \
4   3

- Vistian August 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- DSKim September 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Whichever city has the game, for each of its edge calculate the population of that sub-graph (doing a DFS or BFS) and return the max of all those sub-graphs. O(n)

- tryingtosolvemystery September 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- peter tang September 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous October 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sumit October 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sumit October 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kvdeshmukh1989 November 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Nitish Garg January 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If graph is sparse graph then we can use dfs(modify to add weight while traversing) on all the neighbors and max of all the nighbor city traffic will be the answer.

- ankur7026 March 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If all nodes are connected, then just do sum of all nodes. While querying for a node, subtract node value from sum.

- evo August 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- littlefinger October 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Trying August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This isn't what the question is asking, though. The question isn't asking for the sum of all incoming traffic to a game city. It's asking from which route is most of the traffic coming from.

- helloru August 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This can easily be done in O(n)

- Anonymous August 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

}

- mger1979 August 20, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More