Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
And actually, it'll work for a directed graph as well... just as long as it's unweighted.
Here is the code, I'm not going to include the graph implementation but it's pretty easy to build one that provides what my graph does.
public static void findShortestPath(Graph g, int start, int stop)
{
g.getEdges(start);
Queue <Integer> toVisit = new LinkedList<>();
Set <Integer> alreadyVisited = new HashSet<>();
Map <Integer, Integer> parent = new HashMap<>();
alreadyVisited.add(start);
toVisit.add(start);
parent.put(start, null);
while(!toVisit.isEmpty())
{
int cur = toVisit.poll();
//We win
if(cur == stop)
{
Integer at = cur;
while(at != null)
{
System.out.print(at + ", ");
at = parent.get(at);
}
return;
}
for(Edge e : g.getEdges(cur))
{
if(!alreadyVisited.contains(e.getVertexTo()))
{
parent.put(e.getVertexTo(), cur);
alreadyVisited.add(e.getVertexTo());
toVisit.offer(e.getVertexTo());
}
}
}
//We lose
System.out.println("Couldn't find");
}
but question states that we have only two arguments start and end nodes
how can we take graph as another argument...
Here is sample implementation of dijkstra's algorithm
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int q[100],rear,front;
int dist[100];
void enqueue(int data)
{
int i,k;
if(rear == -1)
{
rear = 0;
front = 0;
q[rear] = data;
}
else
{
for(i=0;i<rear+1;i++)
{
if(dist[data] >= dist[i])
{
continue;
}
else
{
for(k=rear;k>i;k--)
{
q[k+1] = q[k];
}
q[i] = data;
rear++;
return;
}
}
}
}
int dequeue()
{
int tmp;
tmp = q[front];
if(front == rear)
{
front = -1;
rear = -1;
}
else
{
front++;
}
return tmp;
}
int dijkstra(int **w,int n,int src)
{
int i,alt;
int u,v;
for(i=0;i<n;i++)
{
dist[i] = 9999;
enqueue(i);
}
dist[src] = 0;
while(front != -1 && rear != -1)
{
u = dequeue();
for(v=0;v<n;v++)
{
if(w[u][v] != 0)
{
alt = dist[u] + w[u][v];
if(alt < dist[v])
{
dist[v] = alt;
enqueue(v);
}
}
}
}
}
int main()
{
int **weight;
int max_node,i,j;
int src;
FILE * fin = fopen("input.txt","r");
/* input file is "input.txt"
eg. 4
0 10 20 30
0 0 5 15
0 0 0 5
0 0 0 0
*/
weight = (int **)malloc(10*sizeof(int*));
fscanf(fin,"%d",&max_node);
for(i=0;i<max_node;i++)
{
weight[i] = (int *)malloc(10*sizeof(int));
}
for(i=0;i<max_node;i++)
{
for(j=0;j<max_node;j++)
{
fscanf(fin,"%d",&weight[i][j]);
/* weight[i][j] = 0 if no path
between i and j */
}
}
src = 0;
dijkstra(weight,max_node,src);
for(i=0;i<max_node;i++)
{
printf("\n %d",dist[i]);
}
/* sample output
eg. 0
10
15
20
*/
return 0;
}
use minheap instead of the queue as:
int heap[100];
int top=0;
void enqueue(int data)
{
int k;
if(top == 0)
{
top = 1;
heap[top] = data;
}
else
{
top++;
k = top;
while(dist[heap[k/2]] > dist[data] && k > 1)
{
heap[k] = heap[k/2];
k = k/2;
}
heap[k] = data;
}
}
int dequeue()
{
int tmp,val,ind,j;
int i,left,right;
int flag = 0,count = 0;;
tmp = heap[1];
heap[1] = heap[top];
heap[top] = tmp;
tmp = heap[1];
i =1;
ind = i;
while((2*i+1) < top && flag == 0)
{
flag = 1;
left = 2*i;
right = 2*i+1;
if(dist[heap[left]] < dist[tmp] && left <= top)
{
ind = left;
}
if(dist[heap[right]] < dist[heap[ind]] && right <= top)
{
ind = right;
}
if(ind != i)
{
heap[i] = heap[ind];
i = ind;
flag = 0;
}
}
heap[i] = tmp;
val = heap[top];
top--;
return val;
}
Here is a C# implementation.
public class Vertex
{
public string Id { get; set; }
public List<Edge> Neighbours { get { return this.neighbours; } }
private List<Edge> neighbours = new List<Edge>();
}
public class Edge
{
public Vertex Target { get; set; }
public int Cost { get; set; }
}
public class Graph
{
public List<Vertex> Vertices { get { return this.vertices; } }
private List<Vertex> vertices = new List<Vertex>();
public int ShortestPath(Vertex start, Vertex end, ref List<Vertex> path)
{
// set initial distances
Hashtable<Vertex, int> distances = this.InitializeDistances(start);
// keep track of previous path
Hashtable<Vertex, Vertex> previous = new Hashtable<Vertex, Vertex>();
// process each vertex after adding them into a queue
List<Vertex> queue = new List<Vertex> (this.Vertices);
while (queue.Count > 0)
{
// get the vertex, which has the smallest distance, from the queue
Vertex v = PopWithSmallestDistance (queue, distances);
int distanceV = distances [v];
if ( distanceV == Int32.Max)
break; // no edge or no need to continue
if ( v == end)
break; // we are done
foreach ( Vertex n in v.Neighbours)
{
int altN = distanceV + n.Cost;
if ( altN < distances [n.Target] ) // relax
{
distances [n.Target] = altN; // improve the result
previous [n.Target] = v; // add or override
}
}
}
// build up the path
Vertex temp = end;
while (temp != start)
{
path.Add (temp);
temp = previous [temp];
}
// add the initial vertex, too
path.Add (start);
// reverse the path
path.Reverse();
// return the shortest distance from start to end
return distances [end];
}
private static Vertex PopWithSmallestDistance (
List<Vertex> queue, Hashtable<Vertex, int> distances)
{
Vertex v = null;
int min = Int32.Max;
foreach ( Vertex t in queue)
{
int cost = distances [ t ];
if ( cost < min )
{
v = t;
min = cost;
}
}
queue.Remove (v);
return v;
}
private Hashtable<Vertex, int> InitializeDistances (Vertex start)
{
Hashtable<Vertex, int> distances = new Hashtable<Vertex, int>();
foreach (Vertex v in this.Vertices)
{
if (v != start)
{
// initial distance is inifite
distances.Add(v, Int32.Max);
}
else
{
distances.Add (v, 0);
}
}
return distances;
}
}
package com.careercup.google;
import java.util.ArrayList;
import java.util.LinkedHashSet;
public class ShortestPath {
static class Node
{
public ArrayList<Node> neighborNodes;
public int value;
public Node(int v)
{
neighborNodes = new ArrayList<Node>();
value = v;
}
}
static int traverse(Node node1, Node node2, LinkedHashSet<Node> traversedNodes, int knownLength, LinkedHashSet<Node> out)
{
int minLen = Integer.MAX_VALUE;
LinkedHashSet<Node> minPath = new LinkedHashSet<Node>();
if (!traversedNodes.contains(node1))
{
traversedNodes.add(node1);
if (!node1.equals(node2))
{
for (int i =0; i < node1.neighborNodes.size(); i++)
{
int len = traverse(node1.neighborNodes.get(i), node2, traversedNodes, knownLength + 1, out);
if (len < minLen)
{
minLen = len;
minPath.clear();
minPath.addAll(out);
}
}
}
else
{
minLen = knownLength + 1;
minPath.addAll(traversedNodes);
}
if (minPath.size() > 0)
{
out.clear();
out.addAll(minPath);
}
traversedNodes.remove(node1);
}
return minLen;
}
static void printResult(LinkedHashSet<Node> path) {
int i = path.size();
for (Node n : path)
{
System.out.print(n.value + ",");
}
}
/**
* @param args
*/
public static void main(String[] args) {
Node node1 = new Node(1),
node2 = new Node(2),
node3 = new Node(3),
node4 = new Node(4),
node5 = new Node(5),
node6 = new Node(6),
node7 = new Node(7),
node8 = new Node(8),
node9 = new Node(9);
node1.neighborNodes.add(node2);
node2.neighborNodes.add(node5);
node5.neighborNodes.add(node6);
node6.neighborNodes.add(node8);
node2.neighborNodes.add(node6);
node1.neighborNodes.add(node3);
node3.neighborNodes.add(node4);
node4.neighborNodes.add(node8);
node1.neighborNodes.add(node5);
node5.neighborNodes.add(node6);
node6.neighborNodes.add(node8);
LinkedHashSet<Node> traversedNodes = new LinkedHashSet<Node>();
LinkedHashSet<Node> out = new LinkedHashSet<Node>();
int i = traverse(node1, node8, traversedNodes, 0, out);
if (i != Integer.MAX_VALUE)
{
printResult(out);
}
}
}
It think the hidden point in this question is "only the starting and the end nodes and nothing else". This implies that we are unsure about the wights. Algorithm such as Dijkstra cannot be a safe bet since it can't deal with negative weights. Furthermore, BFS is a good choice for finding the shortest path in a graph with unit weights edges. I think the better idea is to use the Bellman-Ford algorithm since it handles the shortest path regardless of the sign of the weight values and also checks if the graph has a negative-weight cycle in which case no all-pairs shortest paths (in case needed/asked) can be constructed.
import java.util.ArrayList;
import java.util.LinkedHashSet;
public class ShortestPath {
static class Node
{
public ArrayList<Node> neighborNodes;
public int value;
public Node(int v)
{
neighborNodes = new ArrayList<Node>();
value = v;
}
}
static int traverse(Node node1, Node node2, LinkedHashSet<Node> traversedNodes, int knownLength, LinkedHashSet<Node> out)
{
int minLen = Integer.MAX_VALUE;
LinkedHashSet<Node> minPath = new LinkedHashSet<Node>();
if (!traversedNodes.contains(node1))
{
traversedNodes.add(node1);
if (!node1.equals(node2))
{
for (int i =0; i < node1.neighborNodes.size(); i++)
{
int len = traverse(node1.neighborNodes.get(i), node2, traversedNodes, knownLength + 1, out);
if (len < minLen)
{
minLen = len;
minPath.clear();
minPath.addAll(out);
}
}
}
else
{
minLen = knownLength + 1;
minPath.addAll(traversedNodes);
}
if (minPath.size() > 0)
{
out.clear();
out.addAll(minPath);
}
traversedNodes.remove(node1);
}
return minLen;
}
static void printResult(LinkedHashSet<Node> path) {
int i = path.size();
for (Node n : path)
{
System.out.print(n.value + ",");
}
}
/**
* @param args
*/
public static void main(String[] args) {
Node node1 = new Node(1),
node2 = new Node(2),
node3 = new Node(3),
node4 = new Node(4),
node5 = new Node(5),
node6 = new Node(6),
node7 = new Node(7),
node8 = new Node(8),
node9 = new Node(9);
node1.neighborNodes.add(node2);
node2.neighborNodes.add(node5);
node5.neighborNodes.add(node6);
node6.neighborNodes.add(node8);
node2.neighborNodes.add(node6);
node1.neighborNodes.add(node3);
node3.neighborNodes.add(node4);
node4.neighborNodes.add(node8);
node1.neighborNodes.add(node5);
node5.neighborNodes.add(node6);
node6.neighborNodes.add(node8);
LinkedHashSet<Node> traversedNodes = new LinkedHashSet<Node>();
LinkedHashSet<Node> out = new LinkedHashSet<Node>();
int i = traverse(node1, node8, traversedNodes, 0, out);
if (i != Integer.MAX_VALUE)
{
printResult(out);
}
}
}
If you downvote any question please put reasons...it would serve as guideline to people who are going to post any new questions..else there is no meaning...In this questions I guess downvote is for not describing the graph type properly..
(or downvoted because question is very simple ???? it is simple if you have a lot of time...)
If it's an unweighted, undirectional graph then this can be done in O(N) (rather than O(N^2) for Djkstra) by simply doing a BFS traversal. You just keep looking through the nodes adjacent to any nodes you're currently examining that you haven't seen before until you see the node you're looking for, and then you reconstruct the path.
- Anonymous July 10, 2013