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