## Amazon Interview Question for SDE1s

Country: United States

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

If it's a connected and directed graph a possible solution could be:

1. Find all distances between each node of the graph, Djikstra applied for each node or else Floyd-Warshall algorithm could be used.

2. iterate over each node of graph and calculate average distance by summing all distances of node from all others and dividing it by N (size of graph).

3. Keep track of the min in the 2nd step and return min.

A sample implementation in Java using Floyd-warshall (Djikstra would be eventually better for performance for the sake of simplicity I'm using floyd-warshall in this example since the code is simpler):

``````class AllPairShortestPath
{
final static int INF = 99999, V = 4;

void minAverageDist(int graph[][])
{
int dist[][] = new int[V][V];
float averageDist[] = new float[V];
int i, j, k;

// step 1 - Floyd warshall - find all shortest distances between nodes
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];

for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}

// 2. once all distances are calculated for each node calculate average distance
float min = INF;
int minNode = 0;
for (i = 0; i < V; i++) {
int sum = 0;
for (j = 0; j < V; j++) {
sum += dist[i][j];
}

averageDist[i] = (float)sum / V;
if (min > averageDist[i]) {
min = averageDist[i];
minNode = i;
}
}

System.out.print("MIN dist average = " + min + " NODE = " + minNode);
}

public static void main (String[] args)
{
/* Let us create the following weighted graph
10
(0)------->(3)
|		 /|\
5 |		 |
|		 | 1
\|/		 |
(1)------->(2)
3		 */
int graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
AllPairShortestPath a = new AllPairShortestPath();
a.minAverageDist(graph);
}
}``````

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.