## Amazon Interview Question

Country: India
Interview Type: Written Test

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

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

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

Works in O(nlogn)

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

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.

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

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.

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

1325, is there a path?

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

boy . no such path 1325

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

@anan I also thought the same. But seems like this is a directed graph.

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

answer should be 7, isn't it?
15
125
1325
1235
135
1345
12345

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

Connections are one directional...

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

If directional I see only 5 paths. Not sure why the poster says the answer is 6.
Edit: Must have been sleepy. There are 6 directed paths.

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

“If there exists a cycle in a path from source to destination print Infinite path”
I don't get your point. If there is no cycle between source and destination, there must be only one path between them. Do you mean that we only consider the simple path?

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

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

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

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

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

What would your source code answer if your node is not a part of loop but loop exists in the graph.

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

``````#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;
}``````

Comment hidden because of low score. Click to expand.
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]);

}

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);
}
}

}

}

}

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

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``````

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

This comment has been deleted.

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

There are 6 paths
1-2-3-4-5
1-2-3-5
1-2-5
1-3-5
1-3-4-5
1-5

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

tag

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

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

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

``````#define N 5
#define SRC 0
#define DST 4
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]);
}``````

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.