Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Inspired by ricardolira48
The problem can be solved in O(n) time where n is the number of nodes.
Since the graph has no cycle, an edge e divides the graph into two sub graphs. For any path between the two graphs, the edge is always used exactly once. And there are (n1 * n2) number of possible paths between the sub-graphs (n1 is the number of nodes in sub-graph 1 and n2 is the number of the nodes in sub-graph 2). Therefore, the amount of value that the edge contributes to the final sum is 'w * n1 * n2, where w is the weight of the edge.
So, we basically calculate w * n1 * n2 for all edges and sum them up. Then how do we calculate n1 and n2? It is obvious that n1 + n2 = n, where n is the number of all nodes in the graph. So we need to only calculate either n1 or n2.
At this point, let's treat the graph as a tree by taking an arbitrary node as root. Note that this possible since the graph does not have any cycle.
Then, we can solve the problem by traversing the tree and sum up (w * size of a sub-tree * (n - size of a sub-tree) when visiting a node.
// convert the graph g into a tree with node n as the root.
Tree convertToTree(Graph g, Node n) {// left unimplemented; }
abstract class Tree {
int size; // number of nodes in a tree (including this node)
}
// Leaf node.
class Leaf extends Tree {
Leaf() {
size = 1; // size of the leaf node is always 1 since it is the only node
}
// returns the amount of values that the edge
// between this node and its parent node contributes to the final sum
int visit(int weight) {
// the edge is used to connect this node to other g.size -1 nodes.
return weight * (g.size - 1);
}
}
// non-leaf node
class Parent extends Tree {
List<Tree> children; // list of children
List<Integer> weights; // weight of edges for each child
int visit(int weight) {
int sum = 0;
int size = 1;
// visit child nodes
for(int i=0; i<children.size(); i++) {
// accumulate the sum
sum += children.get(i).visit(weights.get(i));
// accumulate the number of nodes under this node
size += children.get(i).size;
}
// consider edge from parent node to this node
sum += weight * size * (g.nodes.size() - size);
// update the size of this node (to be used by parent node)
this.size = size;
}
}
int sumOfAllPathWeights(Graph g) {
if (g.nodes.size == 0) { return 0;}
// convert to a tree by taking the first node as root
Tree t = convertToTree(g, g.nodes.get(0));
// the root node has no incoming edge so the initial weight is 0.
return t.visit(0);
}
Forgetting to ask the interviewer about whether the edges can be negative would probably be seen as a big mistake.
I'm assuming the question asks for the sum of shortest paths between all pairs of vertices i, j. In the case where edges are guaranteed to be it seems to me that the straightforward solution is the best one.
- Floyd Warshall algorithm does this in O(n^3).
- Dijsktra algorithm implemented using Fibonacci heaps and started from every vertex does this in n * O(n * logn + m) = O(logn * n^2 + nm), which is better.
- Dijkstra algorithm implemented using standard heaps and started from every vertex does this in n * O((m + n) * logn) = O(n(m+n) * logn).
If the graph is sparse, Floyd Warshall is significantly worse. Perhaps in the case where the graph has Omega(n^2) vertices, it makes a lot of sense to use Floyd Warshall since it is very simple and is going to cache well (I think).
Does anyone know of a better algorithm? Note that the question is interested just in the sum of the weights.
And perhaps the question actually asks for the sum of all paths, not just the ones that are shortest paths between two vertices. The wording is slightly ambiguous.
package tt.oleg.problems.careercup.SumWeightOfEachPath;
import java.util.HashMap;
import java.util.Map;
/**
* Created by oleg on 8/22/16.
*/
public class Graph
{
static class Vertex
{
final String name;
final Map<Vertex, Integer> adj = new HashMap<>();
Vertex(String name)
{
this.name = name;
}
public void addAdj(Vertex v, int Weight)
{
adj.put(v, Weight);
}
@Override
public int hashCode()
{
return name.hashCode();
}
}
final Vertex[] vertices;
public Graph(Vertex[] vertices)
{
this.vertices = vertices;
}
public int calculateAllWeights()
{
int total = 0;
final Map<Vertex, HashMap<Vertex, Integer>> cache = new HashMap<>();
for (Vertex v : vertices)
{
countNodesforAdj(v, null, cache);
}
for (Vertex v : vertices)
{
if (cache.containsKey(v))
{
for (Map.Entry<Vertex, Integer> edge : v.adj.entrySet())
{
if (cache.get(v).containsKey(edge.getKey()))
{
int oneWayEdgeCounter = cache.get(v).get(edge.getKey());
cache.get(v).remove(edge.getKey());
int backawrdWayEdgeCounter = cache.get(edge.getKey()).get(v);
cache.get(edge.getKey()).remove(v);
total += (oneWayEdgeCounter * backawrdWayEdgeCounter * edge.getValue());
}
}
}
}
return total;
}
private int countNodesforAdj(Vertex to, Vertex from, Map<Vertex, HashMap<Vertex, Integer>> cache)
{
if (cache.containsKey(from) && cache.get(from).containsKey(to)) return cache.get(from).get(to);
int countResult = 0;
for (Vertex n : to.adj.keySet())
{
if (n == from) continue;
countResult += countNodesforAdj(n, to, cache);
}
countResult++;
if (from != null)
{
if (!cache.containsKey(from)) cache.put(from, new HashMap<Vertex, Integer>());
Map<Vertex, Integer> map = cache.get(from);
map.put(to, countResult);
}
return countResult;
}
}
Floyd Warshall
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
class Solution {
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(0, 2, 4);
graph.addEdge(1, 2, 5);
graph.addEdge(2, 3, 1);
graph.addEdge(3, 4, 2);
graph.addEdge(3, 5, 3);
//graph.printMatrix();
graph.floyd();
System.out.println(graph.getSum());
}
}
class Graph{
int size=0;
Map<Integer, List<Edge>> map = new HashMap<>();
int[][] matrix;
public Graph(int size){
this.size = size;
matrix = new int[size][size];
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
matrix[i][j] = Integer.MAX_VALUE;
if(i==j) matrix[i][j] = 0;
}
}
//printMatrix();
}
public void addEdge(int start, int end, int weight){
if(!map.containsKey(start)){
List<Edge> edges = new ArrayList<>();
map.put(start, edges);
}
map.get(start).add(new Edge(start, end, weight));
}
public int getSum(){
//return 1;
//printMatrix();
int sum = 0;
for(int i=0; i<size;i++){
for(int j=0; j<size;j++){
if(matrix[i][j] != Integer.MAX_VALUE){
sum += matrix[i][j];
}
}
}
return sum/2;
}
public void floyd(){
//printMatrix();
for(List<Edge> edges : map.values()){
for(Edge edge: edges){
//System.out.println(edge.start+","+edge.end);
matrix[edge.start][edge.end] = edge.weight;
matrix[edge.end][edge.start] = edge.weight;
}
}
for(int k=0; k<this.size;k++){
for(int i=0; i<this.size;i++){
for(int j=0; j<this.size;j++){
if(matrix[i][k] !=Integer.MAX_VALUE &&
matrix[k][j] !=Integer.MAX_VALUE &&
matrix[i][k] + matrix[k][j] < matrix[i][j]){
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
}
//printMatrix();
}
public void printMatrix(){
for(int i=0; i<this.size;i++){
for(int j=0; j<this.size;j++){
System.out.print((matrix[i][j]==Integer.MAX_VALUE?"*":matrix[i][j]) +"\t");
}
System.out.println();
}
}
}
class Edge{
int start;
int end;
int weight;
public Edge(int start, int end, int weight){
this.start =start;
this.end =end;
this.weight =weight;
}
}
Simple solution- Run BFS and keep track of all the paths we have encountered from this node
struct Node{
char Name;
unordered_map<Node*, int> neighbors // hash table with corrosponding weight
}
void printSum(vector<Node*>& graph){
unordered_map<Node*, unordered_set<Node*>> paths; // all the paths we have for this node
int global_sum = 0;
for (Node* n : graph)
paths.insert(n,unordered_set<Node*>()); // initialize all nodes
for (Node* n : graph){
runBFS(n,global_sum,paths);
cout << global_sum<<endl;
}
void runBFS(Node* root, int& global_sum,unordered_map<Node*, unordered_set<Node*>>& paths){
Queue<pair<Node*,int>> q; /// queue with the path to this node
unordered_set<Node*> seen; // keep track of which nodes we have seen
q.push(make_pair(root,0));
seen.insert(root);
unordered_set<Node*> my_paths = paths.find(root)->second; // my paths
// start bfs
while (!q.empty()){
auto top = q.front(); // get the top
q.pop();
Node * visiting_node = top.first; // get the visiting node
// loop through neihbors
for (Node* neighbor: visiting_node->neighbors){
if (seen.find(neighboor) == seen.end()){
seen.add(neighbor);
auto temp = make_pair(neighbor->first,top->second+neighbor->second); // make pair with my distance plus my parents total distance
if (my_paths.find(neighbor->first) == my_paths.end()){ // i havent visited it
auto& neighbor_path = paths.find(neighbor->first)->second;
neigbor_path.insert(root); // we have a path from root to this guy
global_sum += temp->second; // update sum
} // end of visiting if
q.push(temp);
} // end of if
} // end of for
} // end of while
} // end of runBFS method
}
If the graph have no cycles, there's on path from each vertex to another.
Take the following graph for example:
A
|
B
/ \
C D
/ \
E F
A
|
B
/
C D
/ \
E F
Take for example the path from B to D and remove it.
This edge is contributed to the paths from every node on one sub-tree to the other sub-tree.
On each side there are three vertices, so it's contributed 3*3 times = 9
The path from D to F for example will cut the graph to one vertex on one side and 5 on the other side
So there are 1*5 paths, it's contributed to.
/*
I noticed the task was quite exactly specified with the few words, but it needed some repetition:
- unidirected graph with weights and no cycles: -> that can be viewed as a tree
- the sum of the weight of each path: means one value for the whole structure
- shortest path between two vertices: in this setup, it's as well the shortest
weighted path because no forward and backward edges exist (would create cycles
on unidirected graph)
--> no need for Djikstra or other heavy weight algos
--> negative weights don't matter
Solution approach:
- pick an arbitrary node as root to start, traverse down until first leave,
note it's total tree size (=1) propagate that size to the parent, so parent
can keeps track of it's total tree size etc. While doing this for every completely
visited node store in a list it's tree size and weight of edge to parent
- when tree is completely traversed, go through the above created list
(with length n) with pairs that contain tree size (s) and edge-weight (w):
sum += (n-s)*s*w
(node: an edge kind of cut's the tree in two, if a leave is cut,
it's sub-tree is 1, so 1*n paths to all vertices, if the subtree is 2, it's 2*(n-2),
because from each of the two nodes goes a path to each of the remaining n-2 nodes)
The solution looks still complicated, maybe there is an easy algo for it.
Time-Complexity: O(|V|+|E|) = O(|V|+[V]) = O(|V|) due to constraints given
Space-Complexity: O(|V|)
*/
#include <vector>
#include <string>
#include <stack>
#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;
class Node
{
private:
string _id;
vector<pair<int, Node*>> _adj;
Node *_parent = nullptr; // parent
int _size = 1; // subtree sisze
int _wtop = 0; // weight to parent
bool _visited = false;
public:
Node(string id) : _id{ id } {}
void Connect(Node *adj, int w)
{
_adj.emplace_back(pair<int, Node*>(w, adj));
adj->_adj.emplace_back(pair<int, Node*>(w, this));
}
int SumAllPairWeight()
{
ClearAll();
vector<pair<int, int>> nodes; //1st: treesize, 2nd: weight to parent
stack<Node*> s;
s.push(this);
while (!s.empty())
{
auto u = s.top();
bool visit = true;
for (auto e : u->_adj)
{
auto v = e.second;
auto w = e.first;
if (v != u->_parent && !v->_visited)
{
visit = false;
s.push(v);
v->_parent = u;
v->_wtop = w;
v->_size = 1;
}
}
if (visit)
{
u->_visited = true;
s.pop();
nodes.emplace_back(pair<int, int>(u->_size, u->_wtop));
auto p = u->_parent;
if (p != nullptr)
{
p->_size += u->_size;
}
}
}
int sum = 0;
int n = nodes.size();
for (auto u : nodes)
{
int s = u.first;
int w = u.second;
sum += (n - s)*s*w;
}
return sum;
}
private:
void ClearAll()
{
unordered_set<Node*> vis;
stack<Node*> s;
s.push(this);
while (!s.empty())
{
auto u = s.top();
s.pop();
u->_visited = false;
u->_parent = nullptr;
u->_wtop = 0;
u->_size = 1;
vis.emplace(u);
for (auto e : u->_adj)
{
auto v = e.second;
if (vis.find(v) == vis.end())
{
s.emplace(v);
}
}
}
}
};
int main()
{
Node a{ "A" };
Node b{ "B" };
Node c{ "C" };
Node d{ "D" };
a.Connect(&b, 1);
b.Connect(&c, 2);
b.Connect(&d, 3);
cout << "sum (from a): " << a.SumAllPairWeight() << endl;
cout << "sum (from b): " << b.SumAllPairWeight() << endl;
getchar();
}
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
class Solution {
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(0, 2, 4);
graph.addEdge(1, 2, 5);
graph.addEdge(2, 3, 1);
graph.addEdge(3, 4, 2);
graph.addEdge(3, 5, 3);
//graph.printMatrix();
graph.floyd();
System.out.println(graph.getSum());
}
}
class Graph{
int size=0;
Map<Integer, List<Edge>> map = new HashMap<>();
int[][] matrix;
public Graph(int size){
this.size = size;
matrix = new int[size][size];
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
matrix[i][j] = Integer.MAX_VALUE;
if(i==j) matrix[i][j] = 0;
}
}
//printMatrix();
}
public void addEdge(int start, int end, int weight){
if(!map.containsKey(start)){
List<Edge> edges = new ArrayList<>();
map.put(start, edges);
}
map.get(start).add(new Edge(start, end, weight));
}
public int getSum(){
//return 1;
//printMatrix();
int sum = 0;
for(int i=0; i<size;i++){
for(int j=0; j<size;j++){
if(matrix[i][j] != Integer.MAX_VALUE){
sum += matrix[i][j];
}
}
}
return sum/2;
}
public void floyd(){
//printMatrix();
for(List<Edge> edges : map.values()){
for(Edge edge: edges){
//System.out.println(edge.start+","+edge.end);
matrix[edge.start][edge.end] = edge.weight;
matrix[edge.end][edge.start] = edge.weight;
}
}
for(int k=0; k<this.size;k++){
for(int i=0; i<this.size;i++){
for(int j=0; j<this.size;j++){
if(matrix[i][k] !=Integer.MAX_VALUE &&
matrix[k][j] !=Integer.MAX_VALUE &&
matrix[i][k] + matrix[k][j] < matrix[i][j]){
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
}
//printMatrix();
}
public void printMatrix(){
for(int i=0; i<this.size;i++){
for(int j=0; j<this.size;j++){
System.out.print((matrix[i][j]==Integer.MAX_VALUE?"*":matrix[i][j]) +"\t");
}
System.out.println();
}
}
}
class Edge{
int start;
int end;
int weight;
public Edge(int start, int end, int weight){
this.start =start;
this.end =end;
this.weight =weight;
}
}
This seems to be a hard problem as we need to create first a method that finds the shortest path and enumerate each of the node pairs.
We could use memoization in order to make avoid making the algorithm exponential.
public GetShortPathSums(List<Node> nodes)
{
int sum = 0;
var memo = new Dictionary<Node, Dictionary<Node, int>>();
var hashSet = new HashSet<Node>();
foreach(var start in nodes)
{
foreach(var end in nodes)
{
if(!memo.ContainsKey(start) || !memo[start].ContainsKey(end))
{
visited.Add(start);
sum += GetShortestPathWeigth(start, end, hashSet, memo);
visited.Remove(start);
}
}
}
}
private int GetShortestPathWeigth(
Node start,
Node end,
HashSet<Node> visited,
Dictionary<Node, Dictionary<Node, int> memo)
{
if(memo.ContainsKey(start) && memo[start].ContainsKey(end))
{
return memo[start][end];
}
if(start == end) return 0;
var min = int.MaxValue;
foreach(var path in start.Paths)
{
if(!visited.Contains(path.Node))
{
visited.Add(path.Node);
var temp = GetShortestPathWeigth(path.Node, end, visited, memo);
if(temp < min)
{
min = temp;
}
visited.Remove(path.Node);
}
}
if(!memo.ContainsKey(start))
{
memo.Add(start, new Dictionary<Node, int>());
}
memo[start].Add(end, min);
// Because the path could go both ways so path from start-> end == end -> start
if(!memo.ContainsKey(end))
{
memo.Add(end, new Dictionary<Node, int>());
}
memo[end].Add(start, min);
return min;
}
For grapth w/o cycles, this might be good solution:
def traverse(tree, node, parent, acc):
neighbours = set(tree[node].iterkeys())
if neighbours == {parent}:
return 1
else:
ret = 0
for n, w in tree[node].iteritems():
if n != parent:
sub = traverse(tree, n, node, acc)
acc.append(w * (len(tree)-sub) * sub)
ret += sub
return ret
if __name__ == '__main__':
tree = {
'a': {'b':1, 'c':2 , 'd':3,},
'b': {'a':1, 'e':4, },
'c': {'a':2, },
'd': {'a':3, },
'e': {'b':4, },
}
acc = []
traverse(tree, 'a', None, acc)
print sum(acc)
from collections import defaultdict
class Graph(object):
def __init__(self, nodes):
self.nodes = nodes
self.edges = defaultdict(list)
self.weights = []
def add_edge(self, u, v, weight):
self.edges[u].append(v)
self.edges[v].append(u)
self.weights.append((weight, (u,v)))
def weight_sum(self):
result = 0
for w, (u, v) in self.weights:
s1 = self.sub_graph_size(u, v)
s2 = self.nodes - s1
result += w*s1*s2
return result
def sub_graph_size(self, u, v):
cnt = 1
for edge in self.edges[u]:
if edge is v: continue
else:
cnt += self.sub_graph_size(edge, u)
return cnt
g = Graph(6)
g.add_edge(0, 1, 1)
g.add_edge(1, 2, 2)
g.add_edge(1, 3, 3)
g.add_edge(0, 4, 4)
g.add_edge(0, 5, 5)
print g.weight_sum()
I know this is kind of a old post. I just wanted to post my thoughts to see if it is right:
In this problem since we have n nodes and no cycles, there will be n-1 edges.
Consider an edge 'e' between a pair of verticies (u, v):
a) This edge is the shortest path between u and v (no cycles)
b) All other n-2 verticies (other than u and v) has to take this edge to reach either u or v (since we need shorted path for all pairs)
From this we can conclude that each edge e is used n - 1 times (1 for shorted path between u and v and n - 2 for all other verticies) in the total sum
The above is true for all edges. Hence the total sum would be (e1, e2, e3 are edges):
e1 *(n - 1) + e2* (n - 1) + e3*(n - 1) ....
which is same as (n - 1)*(e1 + e2 + e3..)
public int SumOfWeights(Node[] nodeArray)
{
bool[] hasVisited = new bool[nodeArray.Length];
int height = 0;
for (int i = 0; i < nodeArray.Length; i++)
{
height += sumOfWeights(-1, 0, nodeArray[i], hasVisited);
hasVisited[i] = true;
}
return height;
}
int sumOfWeights(int parentIndex, int incomingWeight, Node root, bool[] hasVisited)
{
int height = 0;
if (!hasVisited[root.index])
{
height = incomingWeight;
}
for (int i = 0; i < root.neighbours.Count; i++)
{
if (root.neighbours[i].Item1.index == parentIndex)
{
continue;
}
height += sumOfWeights(root.index, incomingWeight + root.neighbours[i].Item2, root.neighbours[i].Item1, hasVisited);
}
return height;
}
- ricardolira48 August 20, 2016Optimal solutions is to multiply each weight by the amount of nodes to the left times the amount of nodes to the right, so for: E F 4 \ / 5 A 1 | B 2 / \ 3 C D Answer is 1*3*3 + 2*1*5 + 3*1*5 + 4*1*5 + 5*1*5 = 79