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

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