Amazon Interview Question
Country: India
Interview Type: Phone Interview
This is a classic graph traversal question.
In program, adjacencyMap is used to store edges.
vertexMap stores vertices. An vertex has inDegree and inDegree properties.
An vertex with zero inDegree means a journey starts from the vertex.
Edge's visited flag is used to indicate if an edge has been visited during traversing.
findStartingVerties returns vertices with zero inDegree.
public class Graph {
Map<String, Set<Edge>> adjacencyMap = new HashMap<>();
Map<String, Vertex> vertexMap = new HashMap<>();
public static class Edge {
protected String source;
protected String dest;
boolean visited = false;
public Edge(String source, String dest) {
this.source = source;
this.dest = dest;
}
}
public static class Vertex {
protected String name;
protected int inDegree = 0;
protected int outDegree = 0;
public Vertex(String name) {
this.name = name;
}
}
public Graph addEdge(String source, String dest) {
getEdgeSet(source).add(new Edge(source, dest));
getVertex(source).outDegree++;
getVertex(dest).inDegree++;
return this;
}
public void resetVisit() {
adjacencyMap.values().stream().flatMap(edges -> edges.stream())
.forEach(e -> e.visited = false);
}
private Set<Edge> getEdgeSet(String source) {
if (!adjacencyMap.containsKey(source)) {
Set<Edge> edgeSet = new HashSet<Edge>();
adjacencyMap.put(source, edgeSet);
return edgeSet;
} else {
return adjacencyMap.get(source);
}
}
private Vertex getVertex(String name) {
Vertex v = null;
if (!vertexMap.containsKey(name)) {
v = new Vertex(name);
vertexMap.put(name, v);
} else {
v = vertexMap.get(name);
}
return v;
}
// depth-first traversal
public void dft(String vertexName) {
if (adjacencyMap.containsKey(vertexName)) {
for (Edge e : adjacencyMap.get(vertexName)) {
if (e.visited == false) {
System.out.println(vertexName + "->" + e.dest);
e.visited = true;
dft(e.dest);
}
}
}
}
public List<Vertex> findStartingVerties() {
return vertexMap.values().stream().filter(v -> v.inDegree == 0)
.collect(Collectors.toList());
}
public static void main(String[] args) {
Graph g = new Graph();
// SFO->LAX, LAX->ATL, ATL->DEN, DEN->BOS, BOS->JFK, JFK->DEN,DEN->PHL
g.addEdge("SFO", "LAX").addEdge("LAX", "ATL").addEdge("ATL", "DEN")
.addEdge("DEN", "BOS").addEdge("BOS", "JFK")
.addEdge("JFK", "DEN").addEdge("DEN", "PHL")
.addEdge("PHL", "DFW").addEdge("DFW", "SEA")
.addEdge("SEA", "DEN").addEdge("DEN", "HOU")
.addEdge("HOU", "MIA");
g.findStartingVerties().stream().forEach(v -> {
g.resetVisit();
g.dft(v.name);
});
// starting from sfo with dft
g.resetVisit();
System.out.println("Let's pick SFO as the starting point.");
g.dft("SFO");
}
}
public class FrequentTraveller {
public static class Ticket {
public String startLocation;
public String destinationLocation;
public Ticket next;
public Ticket(String start,String dest){
this.startLocation = start;
this.destinationLocation = dest;
}
}
public static Ticket createJourney(List<Ticket> ticketList){
Ticket first = null;
Map<String,Ticket> startMap = new HashMap<String, Ticket>();
Map<String,Ticket> destMap = new HashMap<String, Ticket>();
for(Ticket ticket:ticketList){
startMap.put(ticket.startLocation,ticket);
destMap.put(ticket.destinationLocation, ticket);
}
for(Ticket ticket:ticketList){
if (!destMap.containsKey(ticket.startLocation)){
first = ticket;
}else {
destMap.get(ticket.startLocation).next = ticket;
}
if (startMap.containsKey(ticket.destinationLocation)){
ticket.next = startMap.get(ticket.destinationLocation);
}
}
return first;
}
@Test
public void testJourney(){
List<FrequentTraveller.Ticket> tickets = new ArrayList<FrequentTraveller.Ticket>();
tickets.add(new FrequentTraveller.Ticket("c","d"));
tickets.add(new FrequentTraveller.Ticket("d","e"));
tickets.add(new FrequentTraveller.Ticket("e","f"));
tickets.add(new FrequentTraveller.Ticket("a","b"));
tickets.add(new FrequentTraveller.Ticket("b","c"));
FrequentTraveller.Ticket ticket = FrequentTraveller.createJourney(tickets);
while(ticket != null){
System.out.println(ticket.startLocation+"=>"+ticket.destinationLocation);
ticket = ticket.next;
}
}
}
This is a problem of directed graph. Say there n (=6 here) tickets
T1 (A to B)
T2 (B to C)
T3 (C to A)
T4 (B to D)
T5 (A to B)
T6 (X to Y)
1. Draw a graph with START and DESTINATION as vertices and Ticket as edge. Vertex having in-degree 0 (connects only out edge and no in edge) will be the starting point. Vertex having out-degree 0 (no out edge) will be the end point.
2. There is a possibility that graph contains one or multiple cycles (ticket T1, T2 and T3, A->B->C->A) in that case order doesn't matter. Traveler can pick any of the ticket which form cycle to start the journey. Here any of T1/T2/T3.
3. There is also a possibility that graph contains an isolated edge (ticket T6). This can be flagged as - traveler needs at least one more connecting ticket.
Without date attributes on the tickets how would you resolve the starting point? Even the simplest A->B B->A case, who could you possibly find out which was the "original" starting point?
indegree = 0, Since each station can be travelled number of times hence its not the only condition for checking the start point. Same is with outDegree.
For finding the starting point, simple BFS can solve the problem. Once all the station are visited, then root station will be starting point.
For last station, take the difference of outDegree and inDegree, if it is negative that will be the last station.
#include <stdio.h>
enum stations {delhi = 1,mumbai = 2,london = 3,SF = 4, NY = 5, Tokyo = 6, Seoul = 7, Sydney = 8};
int inputStations[30] = {1,2,1,5,1,7,1,8,2,1,2,3,3,1,4,1,5,4,6,2,7,4,8,6};
int input[9][9] = {0};
int visited[15] = {0};
int vertex, edges;
int inDegree[15] = {0};
int outDegree[15] = {0};
int findStart(int station) {
int front = -1, rear = -1;
int queue[1000] = {0}, Count = 1;
for(int i = 1; i <= vertex; i++)
visited[i] = 0;
queue[++rear] = station;
visited[station] = 1;
int nextStation = 0;
while(front != rear) {
nextStation = queue[++front];
for(int i = 1; i <= vertex; i++) {
if(!visited[i] && input[nextStation][i]) {
queue[++rear] = i;
visited[i] = 1;
Count++;
}
}
if(Count == vertex) {
printf("\nStart Station %d", station);
return station;
}
}
return 0;
}
int main() {
int y, x, start = 0;
vertex = 8;
edges = 12;
for(int i = 0; i < (2*edges); i++) {
y = inputStations[i++];
x = inputStations[i];
input[y][x] = 1;
outDegree[y]++;
inDegree[x]++;
}
for(int i = 1; i <= vertex; i++) {
start = findStart(i);
if(start)
break;
}
int end= 0;
for(int i = 1; i <= vertex; i++) {
if(!outDegree[i]) {
end = i;
break;
}
if((outDegree[i] - inDegree[i]) < 0 )
if(i != start)
end = i;
else
end = start;
}
printf("\n%d %d", start, end);
return 0;
}
#include <stdio.h>
enum stations {delhi = 1,mumbai = 2,london = 3,SF = 4, NY = 5, Tokyo = 6, Seoul = 7, Sydney = 8};
int inputStations[30] = {1,2,1,5,1,7,1,8,2,1,2,3,3,1,4,1,5,4,6,2,7,4,8,6};
int input[9][9] = {0};
int visited[15] = {0};
int vertex, edges;
int inDegree[15] = {0};
int outDegree[15] = {0};
int findStart(int station) {
int front = -1, rear = -1;
int queue[1000] = {0}, Count = 1;
for(int i = 1; i <= vertex; i++)
visited[i] = 0;
queue[++rear] = station;
visited[station] = 1;
int nextStation = 0;
while(front != rear) {
nextStation = queue[++front];
for(int i = 1; i <= vertex; i++) {
if(!visited[i] && input[nextStation][i]) {
queue[++rear] = i;
visited[i] = 1;
Count++;
}
}
if(Count == vertex) {
printf("\nStart Station %d", station);
return station;
}
}
return 0;
}
int main() {
int y, x, start = 0;
vertex = 8;
edges = 12;
for(int i = 0; i < (2*edges); i++) {
y = inputStations[i++];
x = inputStations[i];
input[y][x] = 1;
outDegree[y]++;
inDegree[x]++;
}
for(int i = 1; i <= vertex; i++) {
start = findStart(i);
if(start)
break;
}
int end= 0;
for(int i = 1; i <= vertex; i++) {
if(!outDegree[i]) {
end = i;
break;
}
if((outDegree[i] - inDegree[i]) < 0 )
if(i != start)
end = i;
else
end = start;
}
printf("\n%d %d", start, end);
return 0;
}
public class Traveller {
private List<Ticket> tickets;
private Flight root = null;
/**
* @param args
*/
public static void main(String[] args) {
List<Ticket> routes = new ArrayList<Ticket>();
Traveller traveller = new Traveller();
Ticket route1 = new Ticket("ADD", "JFK");
routes.add(route1);
Ticket route8 = new Ticket("JFK", "BWI");
routes.add(route8);
Ticket route2 = new Ticket("IAD", "ATL");
routes.add(route2);
Ticket route3 = new Ticket("JFK", "IAD");
routes.add(route3);
Ticket route4 = new Ticket("ATL", "LAX");
routes.add(route4);
Ticket route5 = new Ticket("ORD", "ADD");
routes.add(route5);
Ticket route6 = new Ticket("LAX", "DCA");
routes.add(route6);
Ticket route7 = new Ticket("DCA", "JFK");
routes.add(route7);
traveller.setTickets(routes);
traveller.mapTraveller();
}
public Traveller() {
this.tickets = new ArrayList<Ticket>();
}
public void setTickets(List<Ticket> tickets) {
this.tickets = tickets;
}
public void addFlight(Ticket ticket) {
Flight flight = new Flight(ticket);
if (root == null) {
root = flight;
return;
}
if (flight.ticket.stop == root.ticket.start) {
root.previousFlight = flight;
flight.nextFlight = root;
root = flight;
return;
}
Flight current = root;
Flight left = null;
Flight right = null;
while (current != null) {
if (flight.ticket.start == current.ticket.stop) {
left = current;
} else if (flight.ticket.stop == current.ticket.start) {
right = current;
}
if (current.nextFlight == null) {
break;
}
current = current.nextFlight;
}
if (left != null && right != null) {
Flight temp1 = left.nextFlight;
Flight temp2 = right.nextFlight;
left.nextFlight = flight;
flight.nextFlight = right;
right.nextFlight = temp1;
if (temp1 != null) {
temp1.nextFlight = temp2;
}
} else if (left != null) {
Flight temp = left.nextFlight;
left.nextFlight = flight;
flight.nextFlight = temp;
} else {
current.nextFlight = flight;
}
}
public void mapTraveller() {
for (Ticket ticket : this.tickets) {
this.addFlight(ticket);
}
if (root != null) {
Flight current = root;
while (current != null) {
System.out.println(current.ticket.start + " to " + current.ticket.stop);
current = current.nextFlight;
}
}
}
}
class Ticket {
String start;
String stop;
Ticket(String start, String stop) {
this.start = start;
this.stop = stop;
}
}
class Flight {
Flight previousFlight;
Flight nextFlight;
Ticket ticket;
Flight (Ticket ticket) {
this.ticket = ticket;
}
}
To those concerned about cycles and not knowing where to start. If you interpret the problem as "find any sequence of tickets for which every destination is reached", then starting point doesn't matter. If we don't know where to start, try each starting location until you find a full traversal of the directed graph. Searching for the node with indegree == 0 is just an optimization, because in the worst case no node will have indegree == 0, so its better to write an algorithm that doesn't care about this (in my opinion). Here is a solution, with a sample tickets that form a cyclic graph. Complexity is 0(n^2)
#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <map>
typedef std::pair<std::string, std::string> ticket;
struct graph_node
{
std::string name;
std::vector<graph_node*> neighbors;
};
void traverse_graph(graph_node* root,
size_t numTickets,
std::deque<ticket>& path)
{
// Remember list of neighbor nodes, so we can restore
// after each recursion below
std::vector<graph_node*> originalNeighbors = root->neighbors;
// Depth first search the graph, removing edges as we go
// Termination condition is when path is size of numTickets
// i.e. we have used every possible traversal path
for(size_t i = 0; i < root->neighbors.size(); ++i)
{
graph_node* node = root->neighbors[i];
// We are about to use this ticket, add it to our current path
path.push_back(ticket{root->name, node->name});
// This ticket is used, remove it so further searching doesn't reconsider it
root->neighbors.erase(root->neighbors.begin() + i);
// Depth first search
traverse_graph(node, numTickets, path);
// Did we find a path?
if(path.size() >= numTickets)
{
// Terminate recursion without damaging our path
return;
}
// We are leaving this node, put the ticket back
path.pop_back();
// This is a clumsy but safe way to undo the delete
// Otherwise outer loop logic needs reconsideration
root->neighbors = originalNeighbors;
}
}
int main()
{
std::vector<ticket> tickets;
// A ticket graph with some cycles
tickets.push_back({"a", "b"});
tickets.push_back({"b", "c"});
tickets.push_back({"c", "a"});
tickets.push_back({"a", "d"});
tickets.push_back({"d", "e"});
tickets.push_back({"e", "c"});
tickets.push_back({"a", "f"});
tickets.push_back({"f", "g"});
tickets.push_back({"g", "h"});
tickets.push_back({"h", "i"});
tickets.push_back({"i", "g"});
tickets.push_back({"g", "j"});
tickets.push_back({"j", "a"});
// Somewhere to store the graph nodes
typedef std::map<std::string, graph_node> graph_context;
graph_context graphContext;
// Build the graph
for(const ticket& t : tickets)
{
graph_node& arrive = graphContext[t.second];
arrive.name = t.second;
graph_node& depart = graphContext[t.first];
depart.name = t.first;
depart.neighbors.push_back(&arrive);
}
// Try each node as a starting point to see if we can find a solution
for(graph_context::value_type& p : graphContext)
{
// Traverse using this node as the start point
std::deque<ticket> path;
traverse_graph(&p.second, tickets.size(), path);
// Was every ticket used?
if(path.size() == tickets.size())
{
// Then this path is a solution
std::cout << "Found solution:" << std::endl;
for(const ticket& t : path)
{
std::cout << t.first << " -> " << t.second << std::endl;
}
break;
}
}
}
How about this example?
- Anonymous September 26, 2016a-b-c
c-b-a
a-b
b-a
a-b-c
c-b-a
a-b
b-a
a-b-c-d
How can you reconstruct this path having only an unordered list of tickets?
How do you know user went from a-b-a after first a-b-c roundtrip or after second time ? You can find source and final destination but it is impossible to
rebuild the path.