## Amazon Interview Question for SDE1s

• 0

Country: India
Interview Type: Written Test

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

Here's the solution based on Dijkstra algorithm and priority queue -

``````package graph;

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Vertex implements Comparable<Vertex>
{
public final String name;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;

public Vertex(String argName)
{
name = argName;
}

public String toString()
{
return name;
}

public int compareTo(Vertex other)
{
return Double.compare(minDistance, other.minDistance);
}

}

class Edge
{
public final Vertex target;
public final double weight;

public Edge(Vertex argTarget, double argWeight)
{
target = argTarget;
weight = argWeight;
}
}

public class ShortestPath
{
public static void computePaths(Vertex source)
{
source.minDistance = 0.;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
while ( !vertexQueue.isEmpty() )
{

Vertex u = vertexQueue.poll();
// Last connected vertex
if ( u.adjacencies == null )
{
continue;
}

// Visit each edge exiting u
for ( Edge e : u.adjacencies )
{
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if ( distanceThroughU < v.minDistance )
{
vertexQueue.remove(v);
v.minDistance = distanceThroughU;
v.previous = u;
}
}
}
}

public static List<Vertex> getShortestPathTo(Vertex target)
{
List<Vertex> path = new ArrayList<Vertex>();
for ( Vertex vertex = target; vertex != null; vertex = vertex.previous )

Collections.reverse(path);
return path;
}

public static void main(String[] args)
{

Vertex A = new Vertex("A");
Vertex B = new Vertex("B");
Vertex C = new Vertex("C");
Vertex D = new Vertex("D");
Vertex E = new Vertex("E");

A.adjacencies = new Edge[] { new Edge(B, 8), new Edge(D, 6) };
B.adjacencies = new Edge[] { new Edge(C, 11) };
C.adjacencies = new Edge[] { new Edge(E, 10) };
D.adjacencies = new Edge[] { new Edge(E, 32) };

computePaths(A); // run Dijkstra
System.out.println("Distance to " + E + ": " + E.minDistance);
List<Vertex> path = getShortestPathTo(E);
System.out.println("Path: " + path);
}
}``````

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.