## Amazon Interview Question

**Country:**India

**Interview Type:**Written Test

Create a Dictionary of Node to int, which will act as a counter. Perform a breadth first search starting from the source traversal, adding k to each node's counter as you process it (where k is the number of the currently processing nodes). The destination node's counter will be the number of paths to the node. Time is ~O(n), where n = number of edges. This doesn't check for cycles, however.

You algorithm doesn't work. Because there is no absolute breadth. Only nodes in a tree has breath, because there is no cycles in a tree.

1)create adjacency list from given connection

2)CreateQueue(),int count=0;

3)Enqueue(source)

4)while(!isQueueEmty)

{

int elem =Dequeue();

if(count&&elem=source){

print("loop");

exit;}

else if(elem==destination){

count++;

continue;

}

else{

for all w adjacent to elem{

Enqueue(w);

}

}//end else

}//end while

Ex:initial q 1,

then 2,3,5

then 5,3,3,5

then count=1 q= 3,3,5

then 5,4,3,5

then count =2 and q= 4,3,5

then 5,3,5

then count =3 q= 3 ,5

then 4,5,5

then 5,5,5

then count =4 q= 5,5

then count =5

then count =6

while loop done ,total path =count =6

why do you only enqueue the nodes that has a greater value than the current node? why not all the adjacent node?

thats why you neglect the possibility 1->3->2->5

```
#include<iostream>
#include<map>
#include <vector>
using namespace std;
#define SIZE 4
struct IntPairs
{
int x;
int y;
}pairs[SIZE];
map<int, vector<int> > xMapy;
map<int, vector<int> >::iterator itr;
vector<int>::iterator vitr;
int CountPaths(int sourceNode, int destiNode);
void InitPairs()
{
for(int i=0; i<SIZE; i++)
{
cout<<endl<<"For Pairs "<<i<<" Enter X: ";
cin>>pairs[i].x;
cout<<"->";
cin>>pairs[i].y;
}
}
void GetPaths(int sourceNode, int destiNode)
{
int countPaths = 0;
for(int i=0; i<SIZE; i++)
{
xMapy[pairs[i].x].push_back(pairs[i].y);
}
if((itr = xMapy.find(sourceNode)) != xMapy.end())
{
for(int i = 0; i < itr->second.size(); i++)
{
countPaths += CountPaths(itr->second[i], destiNode);
}
}
cout<<"Total Paths: "<<countPaths<<endl;
}
int CountPaths(int sourceNode, int destiNode)
{
if(sourceNode == destiNode)
{
return 1;
}
if(xMapy.find(sourceNode) == xMapy.end())
{
return 0;
}
else
{
for(int i = 0; i < xMapy.find(sourceNode)->second.size(); i++)
{
return CountPaths(xMapy.find(sourceNode)->second[i], destiNode);
}
}
}
int main()
{
InitPairs();
int sourceNode;
int destiNode;
cout<<"Enter source: ";
cin>>sourceNode;
cout<<endl<<" Enter Destination Node: "<<endl;
cin>>destiNode;
GetPaths(sourceNode, destiNode);
return 0;
}
```

package amazon;

import java.util.ArrayList;

import java.util.Iterator;

class Pair {

int sourceVal;

int destVal;

Pair(int src, int dest) {

this.sourceVal = src;

this.destVal = dest;

}

}

public class TestDestination {

static int count = 0;

public static void main(String[] args) {

ArrayList<Pair> inputList = new ArrayList<Pair>();

/*

* infinite loop case

* int input[][] = { { 1, 2 }, { 1, 3 }, { 1, 5 }, { 2, 5 }, { 2, 3 },

{ 3, 4 }, { 3, 5 }, { 3, 2 },{ 3, 2 }, { 4, 5 } };

*

*/

int input[][] = { { 1, 2 }, { 1, 3 }, { 1, 5 }, { 2, 5 }, { 2, 3 },

{ 3, 4 }, { 3, 5 },{ 4, 5 } };

for (int i = 0; i < input.length; i++) {

populate(inputList, input[i]);

}

if (count == -1) {

System.out.println("Infinite loop is found");

} else {

countPath(inputList, 1, 5);

System.out.println(count);

}

}

public static void populate(ArrayList<Pair> list, int[] val) {

Iterator<Pair> it = list.iterator();

while (it.hasNext()) {

Pair pair = (Pair) it.next();

if (pair.sourceVal == val[1]) {

count = -1;

return;

}

}

Pair pair = new Pair(val[0], val[1]);

list.add(pair);

}

public static void countPath(ArrayList<Pair> list, int src, int dest) {

for (int i = 0; i < list.size(); i++) {

Pair tempPair = list.get(i);

if (tempPair.sourceVal == src) {

if (tempPair.destVal == dest)

count++;

else {

countPath(list, tempPair.destVal, dest);

}

}

}

}

}

Beat this . Ruby rulz .

```
@path = [[1, 2],[1, 3],[1, 5],[2, 5],[2, 3],[3, 4],[3, 5],[4, 5]]
def pathExist(frm,dest,visited)
puts visited and return if frm == dest
return if visited.length > 9
@path.each do | st |
pathExist(st.last,dest,visited + "-" + st.last.to_s) if st.first == frm
end
end
```

We need to fix backtracking with memorization. for the example given in the question if f(n) represents the number of paths from nth node. then f(1) = f(2)+f(3) + f(5) directly connected nodes.

f(1) = f(2)+f(3) + f(5)

f(1) = (f(3) + f(5)) + (f(4) + f(5)) + f(5)

f(1) = ((f(4) + f(5)) + f(5)) + (f(5) + f(5)) + f(5)

f(1) = ((f(5) + f(5)) + f(5)) + (f(5) + f(5)) + f(5) = 6 as f(5) = 1.

here we are calc f(3) twice which we can store and reduce calc

```
#define N 5
#define SRC 0
#define DST 4
int G[N][N}={{0,1,1,0,1},{0,0,1,0,1},{0,0,0,1,1},{0,0,0,0,1},{0,0,0,0,0}}; // Adjacency matrix
int path[N]={0,0,0,0,0} // initialize number of paths to destination from each node
int main(void)
{
for(i=0;i<N; i++)
if(G[i][DST]==1)
path[i]++;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(G[i][j]==1&&path[j]>0)
path[i]=path[i]+path[j];
}
}
print(path[SRC]);
}
```

Apply Djikshtra's algorithm and keep track of number of times you update the destination node.

- Epic_coder September 29, 2012