## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
8
of 10 vote

``````Optimal 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``````

Comment hidden because of low score. Click to expand.
0

I think this solution will work as long as the graph is not cyclic. (i.e only one path exist between any two given nodes.). Unfortunately, this fact is not clarified in the question.

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

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

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

Then how about path C to D? I think the output should be 18.

Comment hidden because of low score. Click to expand.
1
of 3 vote

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.

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

@djway Did the interviewer mention that the graph didn't have cycles?

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

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

{
}

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

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;
{
if (n == from) continue;
}
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;
}
}``````

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

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

}

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

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

testin

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

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

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

}``````

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

I did not fully understand the optimal solution the interviewer described, but this is what I remember. The interviewer said to multiply each weight by the size of the tree of its connecting neighbors. So with the example, it would be 1*3 + 2*3 + 3*3 = 18.

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

@mrsurajpoudel.wordpress.com The interviewer told me not to worry about cycles for now, so I probably did not get far enough for the followup question.

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

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.

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

coder

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

``````/*
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;

Node *_parent = nullptr; // parent
int _size = 1; // subtree sisze
int _wtop = 0; // weight to parent
bool _visited = false;

public:
Node(string id) : _id{ id } {}

{
}

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

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

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

}

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

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

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

var temp = GetShortestPathWeigth(path.Node, end, visited, memo);
if(temp < min)
{
min = temp;
}

visited.Remove(path.Node);
}
}

if(!memo.ContainsKey(start))
{
}

// Because the path could go both ways so path from start-> end == end -> start
if(!memo.ContainsKey(end))
{
}

return min;
}``````

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

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

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

``````from collections import defaultdict
class Graph(object):
def __init__(self, nodes):
self.nodes = nodes
self.edges = defaultdict(list)
self.weights = []

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)
print g.weight_sum()``````

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

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

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

asdf

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

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

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use Floyd Warshall.

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.

### 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.