Google Interview Question
Country: India
Interview Type: In-Person
As it is non-weighted graph BFS will always give shortest path. but there may be more than 1 shortest path with same distance. I have used BFS to find out shortest path.
Here I am adding visited node to queue so that once path is found, queue will have multiple destination node with distance from source. I am filtering out the shortest distance.
Java code is given below -
class Graph {
private int num_of_vertices =0;
private int num_of_edges =0;
private Map<Integer, ArrayList<Integer>> adjListsMap = new HashMap<>();
public int addVertex() {
adjListsMap.put(++num_of_vertices, new ArrayList<>());
return num_of_vertices;
}
public void addEdge(int u,int v) {
if (adjListsMap.containsKey(u) && adjListsMap.containsKey(v)) {
++num_of_edges;
ArrayList<Integer> neighbors = adjListsMap.get(u);
neighbors.add(v);
} else {
throw new IllegalArgumentException("either starting or ending node is not present in graph");
}
}
public List<Integer> getNeighbors(int vertex){
return adjListsMap.get(vertex);
}
}
public class AllShortestPathInGraph {
public static int getNumberOfShortestPath(Graph graph,int source,int destination){
class QueueNode{
Integer vertex;
Integer distance;
public QueueNode(Integer vertex, Integer distance) {
this.vertex = vertex;
this.distance = distance;
}
}
int shortestDistance =0;
Deque<QueueNode> deque = new LinkedList<>();
int shortestPath = 0;
boolean found = false;
deque.add(new QueueNode(source,0));
while (!deque.isEmpty()){
QueueNode node = deque.remove();
for (Integer neighbor : graph.getNeighbors(node.vertex)) {
if(neighbor.equals(destination)){
if (!found) {
found = true;
shortestDistance = node.distance + 1;
shortestPath++;
}
else if (shortestDistance==node.distance+1){
shortestPath++;
}
}
if (!found){
deque.add(new QueueNode(neighbor,node.distance+1));
}
}
}
return shortestPath;
}
public static void main(String[] a) {
Graph graph = new Graph();
for (int i = 0; i < 5; i++) {
graph.addVertex();
}
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 5);
graph.addEdge(4, 5);
System.out.println(getNumberOfShortestPath(graph,1,5));
}
}
package test;
import java.util.Map.Entry;
import java.util.TreeMap;
public class GoogleShortestPaths {
public static void main(String[] args) {
GraphDFS theGraph = new GraphDFS();
theGraph.addVertex('A'); // 0 (start for dfs)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4
theGraph.addVertex('R'); // 5
theGraph.addVertex('S'); // 6
theGraph.addEdge(0, 1); // AB
theGraph.addEdge(1, 2); // BC
theGraph.addEdge(0, 3); // AD
theGraph.addEdge(3, 4); // DE
theGraph.addEdge(3, 2); // DC
theGraph.addEdge(5, 0); // RB
theGraph.addEdge(5, 6); // RS
theGraph.addEdge(6, 2); // SC
theGraph.dfs('A', 'C'); // depth-first search
theGraph.deleteMaxPathOfMap();
System.out.println("shortestPath "+theGraph.shortestPath);
}
}
class StackDFS
{
private final int SIZE = 20;
private int[] stack;
private int top;
// ------------------------------------------------------------
public StackDFS() // constructor
{
stack = new int[SIZE]; // make array
top = -1;
}
// ------------------------------------------------------------
public void push(int j) // put item on stack
{
stack[++top] = j; }
// ------------------------------------------------------------
public int pop() // take item off stack
{
stack[top] = -1;
return stack[top--]; }
// ------------------------------------------------------------
public int peek() // peek at top of stack
{
return stack[top];
}
// ------------------------------------------------------------
public boolean isEmpty() // true if nothing on stack
{
return (top == -1); }
// ------------------------------------------------------------
} // end class StackX
////////////////////////////////////////////////////////////////
class VertexDFS
{
public char label; // label (e.g. 'A')
public boolean wasVisited;
// ------------------------------------------------------------
public VertexDFS(char lab) // constructor
{
label = lab;
wasVisited = false;
}
// ------------------------------------------------------------
} // end class Vertex
////////////////////////////////////////////////////////////////
class GraphDFS
{
private final int MAX_VERTS = 20;
private VertexDFS vertexList[]; // list of vertices
private int adjacencyMatrix[][]; // adjacency matrix
private int numberVerts; // current number of vertices
private StackDFS theStack;
TreeMap<String, Integer> shortestPath = new TreeMap<String, Integer>();
// ------------------------------------------------------------
public GraphDFS() // constructor
{
vertexList = new VertexDFS[MAX_VERTS];
// adjacency matrix
adjacencyMatrix = new int[MAX_VERTS][MAX_VERTS];
numberVerts = 0;
for(int y=0; y<MAX_VERTS; y++) // set adjacency
for(int x=0; x<MAX_VERTS; x++) // matrix to 0
adjacencyMatrix[x][y] = 0;
theStack = new StackDFS();
} // end constructor
// ------------------------------------------------------------
public void addVertex(char lab)
{
vertexList[numberVerts++] = new VertexDFS(lab);
}
// ------------------------------------------------------------
public void addEdge(int start, int end)
{
adjacencyMatrix[start][end] = 1;
adjacencyMatrix[end][start] = 1;
}
public void dfs(char vertixBase, char vertixToFind) // depth-first search
{
int indexVertixBase = findIndexVertex(vertixBase);
int indexVertixToFind = findIndexVertex(vertixToFind);
int counterDepth = 0, vertexUnvisited = -1;
StringBuilder chainCharofGrahp = new StringBuilder();
if (indexVertixBase > -1){
while (getIndexAdjUnvisitedVertex( indexVertixBase ) > -1 ){
vertexList[indexVertixBase].wasVisited = true;
theStack.push(indexVertixBase);
counterDepth++;
chainCharofGrahp.append(vertixBase);
while( !theStack.isEmpty() ) // until stack empty,
{
// get an unvisited vertex adjacent to stack top
vertexUnvisited = getIndexAdjUnvisitedVertex( theStack.peek() );
if(vertexUnvisited == -1) // if no such vertex,
theStack.pop();
else // if it exists,
{
counterDepth++;
chainCharofGrahp.append(vertexList[vertexUnvisited].label);
System.out.println("label "+vertexList[vertexUnvisited].label);
if (vertexUnvisited == indexVertixToFind){
shortestPath.put(chainCharofGrahp.toString(), counterDepth);
chainCharofGrahp = new StringBuilder();
counterDepth = 0;
break;
}
vertexList[vertexUnvisited].wasVisited = true; // mark it
theStack.push(vertexUnvisited); // push it
}
}
}
// stack is empty, so we're done
for(int j=0; j<numberVerts; j++) // reset flags
vertexList[j].wasVisited = false;
}
}
// ------------------------------------------------------------
// returns an unvisited vertex adj to v
public int getIndexAdjUnvisitedVertex(int peekStack)
{
for(int j=0; j<numberVerts; j++)
if(adjacencyMatrix[peekStack][j]==1 && vertexList[j].wasVisited==false)
return j;
return -1;
}
private int findIndexVertex(char vertixBase){
for (int i=0; i<vertexList.length;i++){
if( vertexList[i].label == vertixBase){
return i;
}
}
return -1;
}
public void deleteMaxPathOfMap(){
Entry<String, Integer> entry= shortestPath.firstEntry();
int keyMinumun = entry.getValue();
for (Entry<String, Integer> entryMap: shortestPath.entrySet()){
int value=entryMap.getValue();
if (value > keyMinumun)
shortestPath.remove(entryMap.getKey());
}
}
// ------------------------------------------------------------
} // end class Graph
package test;
import java.util.Map.Entry;
import java.util.TreeMap;
public class GoogleShortestPaths {
public static void main(String[] args) {
GraphDFS theGraph = new GraphDFS();
theGraph.addVertex('A'); // 0 (start for dfs)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4
theGraph.addVertex('R'); // 5
theGraph.addVertex('S'); // 6
theGraph.addEdge(0, 1); // AB
theGraph.addEdge(1, 2); // BC
theGraph.addEdge(0, 3); // AD
theGraph.addEdge(3, 4); // DE
theGraph.addEdge(3, 2); // DC
theGraph.addEdge(5, 0); // RB
theGraph.addEdge(5, 6); // RS
theGraph.addEdge(6, 2); // SC
theGraph.dfs('A', 'C'); // depth-first search
theGraph.deleteMaxPathOfMap();
System.out.println("shortestPath "+theGraph.shortestPath);
}
}
class StackDFS
{
private final int SIZE = 20;
private int[] stack;
private int top;
// ------------------------------------------------------------
public StackDFS() // constructor
{
stack = new int[SIZE]; // make array
top = -1;
}
// ------------------------------------------------------------
public void push(int j) // put item on stack
{
stack[++top] = j; }
// ------------------------------------------------------------
public int pop() // take item off stack
{
stack[top] = -1;
return stack[top--]; }
// ------------------------------------------------------------
public int peek() // peek at top of stack
{
return stack[top];
}
// ------------------------------------------------------------
public boolean isEmpty() // true if nothing on stack
{
return (top == -1); }
// ------------------------------------------------------------
} // end class StackX
////////////////////////////////////////////////////////////////
class VertexDFS
{
public char label; // label (e.g. 'A')
public boolean wasVisited;
// ------------------------------------------------------------
public VertexDFS(char lab) // constructor
{
label = lab;
wasVisited = false;
}
// ------------------------------------------------------------
} // end class Vertex
////////////////////////////////////////////////////////////////
class GraphDFS
{
private final int MAX_VERTS = 20;
private VertexDFS vertexList[]; // list of vertices
private int adjacencyMatrix[][]; // adjacency matrix
private int numberVerts; // current number of vertices
private StackDFS theStack;
TreeMap<String, Integer> shortestPath = new TreeMap<String, Integer>();
public GraphDFS() // constructor
{
vertexList = new VertexDFS[MAX_VERTS];
// adjacency matrix
adjacencyMatrix = new int[MAX_VERTS][MAX_VERTS];
numberVerts = 0;
for(int y=0; y<MAX_VERTS; y++) // set adjacency
for(int x=0; x<MAX_VERTS; x++) // matrix to 0
adjacencyMatrix[x][y] = 0;
theStack = new StackDFS();
} // end constructor
public void addVertex(char lab)
{
vertexList[numberVerts++] = new VertexDFS(lab);
}
public void addEdge(int start, int end)
{
adjacencyMatrix[start][end] = 1;
adjacencyMatrix[end][start] = 1;
}
public void dfs(char vertixBase, char vertixToFind) // depth-first search
{
int indexVertixBase = findIndexVertex(vertixBase);
int indexVertixToFind = findIndexVertex(vertixToFind);
int counterDepth = 0, vertexUnvisited = -1;
StringBuilder chainCharofGrahp = new StringBuilder();
if (indexVertixBase > -1){
while (getIndexAdjUnvisitedVertex( indexVertixBase ) > -1 ){
vertexList[indexVertixBase].wasVisited = true;
theStack.push(indexVertixBase);
counterDepth++;
chainCharofGrahp.append(vertixBase);
while( !theStack.isEmpty() ) // until stack empty,
{
// get an unvisited vertex adjacent to stack top
vertexUnvisited = getIndexAdjUnvisitedVertex( theStack.peek() );
if(vertexUnvisited == -1) // if no such vertex,
theStack.pop();
else // if it exists,
{
counterDepth++;
chainCharofGrahp.append(vertexList[vertexUnvisited].label);
System.out.println("label "+vertexList[vertexUnvisited].label);
if (vertexUnvisited == indexVertixToFind){
shortestPath.put(chainCharofGrahp.toString(), counterDepth);
chainCharofGrahp = new StringBuilder();
counterDepth = 0;
break;
}
vertexList[vertexUnvisited].wasVisited = true; // mark it
theStack.push(vertexUnvisited); // push it
}
}
}
// stack is empty, so we're done
for(int j=0; j<numberVerts; j++) // reset flags
vertexList[j].wasVisited = false;
}
}
// returns an unvisited vertex adj to v
public int getIndexAdjUnvisitedVertex(int peekStack)
{
for(int j=0; j<numberVerts; j++)
if(adjacencyMatrix[peekStack][j]==1 && vertexList[j].wasVisited==false)
return j;
return -1;
}
private int findIndexVertex(char vertixBase){
for (int i=0; i<vertexList.length;i++){
if( vertexList[i].label == vertixBase){
return i;
}
}
return -1;
}
public void deleteMaxPathOfMap(){
Entry<String, Integer> entry= shortestPath.firstEntry();
int keyMinumun = entry.getValue();
for (Entry<String, Integer> entryMap: shortestPath.entrySet()){
int value=entryMap.getValue();
if (value > keyMinumun)
shortestPath.remove(entryMap.getKey());
}
}
} // end class Graph
public class Solution {
public static int getNumberOfPaths(int [][] adjMatrix, int source, int destination) {
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.add(new Node(0, source, 1));
boolean [] founds = new boolean[adjMatrix.length];
int [] ways = new int[adjMatrix.length];
int [] minCosts = new int[adjMatrix.length];
for (int i = 0; i < adjMatrix.length; i++) {
minCosts[i] = Integer.MAX_VALUE;
}
while (!queue.isEmpty()) {
Node n = queue.poll();
if (founds[n.vertex] == false) {
ways[n.vertex] += n.way;
founds[n.vertex] = true;
break;
}
if (founds[n.vertex] && minCosts[n.vertex] == n.cost) {
ways[n.vertex] += n.way;
continue;
}
if (founds[n.vertex] && minCosts[n.vertex] > n.cost) {
ways[n.vertex] = n.way;
minCosts[n.vertex]= n.cost;
for (int i = 0; i < adjMatrix.length; i++) {
if (adjMatrix[n.vertex][i] != 0) {
if (founds[i] == false) {
queue.add(new Node(n.cost + adjMatrix[n.vertex][i], i, n.way));
}
}
}
continue;
}
for (int i = 0; i < adjMatrix.length; i++) {
if (adjMatrix[n.vertex][i] != 0) {
if (founds[i] == false) {
queue.add(new Node(n.cost + adjMatrix[n.vertex][i], i, n.way));
}
}
}
}
return ways[destination];
}
}
class Node implements Comparable<Node>{
final int cost;
final int vertex;
final int way;
public Node(int cost, int vertex, int way) {
this.cost = cost;
this.vertex = vertex;
this.way = way;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.cost, o.cost);
}
}
We can use simultaneous BFS from both source and destination to achieve ~2*sqrt(n) frontier size instead of n for random graphs.
Whenever two searches meet, we keep the minimal distances from each node and ignore longer paths from that moment - something like branch and bound.
To count number of shortest paths we track paths count in each vertex and then multiply them.
- emb May 27, 2016from collections import defaultdict, deque graph = defaultdict(list) graph.update({ 0: [1, 2, 3], 4: [1, 2, 3], 5: [4, 6], 6: [7, 8, 9], 10: [7, 8, 9] }) # prettify graph def normalize(graph): for v, neighbours in graph.items(): for u in neighbours: if u != v: graph[u].append(v) for v, neighbours in graph.iteritems(): graph[v] = sorted(list(set(neighbours))) return graph def simultaneous_bfs(graph, source, destination): SOURCE_TYPE, DESTINATION_TYPE = range(2) queue = deque([(source, SOURCE_TYPE), (destination, DESTINATION_TYPE)]) allpaths = [defaultdict(int), defaultdict(int)] alldistances = [defaultdict(int), defaultdict(int)] min_distances = None allpaths[SOURCE_TYPE][source] = 1 allpaths[DESTINATION_TYPE][destination] = 1 alldistances[SOURCE_TYPE][source] = 0 alldistances[DESTINATION_TYPE][destination] = 0 while queue: u, vertex_type = queue.popleft() paths = allpaths[vertex_type] distances = alldistances[vertex_type] if min_distances is not None: if distances[u] >= min_distances[vertex_type]: continue for v in graph[u]: if paths[v]: if distances[v] == distances[u] + 1: paths[v] += paths[u] else: this_distance = distances[u] + 1 if allpaths[1 - vertex_type][v]: other_distance = alldistances[1 - vertex_type][v] if min_distances is None: min_distances = [None] * 2 min_distances[vertex_type] = this_distance min_distances[1 - vertex_type] = other_distance else: if min_distances[vertex_type] < this_distance: continue min_distances[vertex_type] = this_distance distances[v] = this_distance paths[v] = paths[u] queue.append((v, vertex_type)) result = 0 if min_distances is None: return 0 for v in allpaths[0]: if alldistances[0][v] == min_distances[0] and alldistances[1][v] == min_distances[1]: result += allpaths[0][v] * allpaths[1][v] return result graph = normalize(graph) assert simultaneous_bfs(graph, 0, 10) == 9 assert simultaneous_bfs(graph, 0, 4) == 3 assert simultaneous_bfs(graph, 3, 10) == 3