Amazon Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
public class ExceptedValue {
int []isSelected;
int [][] relation;
public static void main(String args[]) throws IOException {
@SuppressWarnings("resource")
BufferedReader read = new BufferedReader(new FileReader(
"input/expectedInput.txt"));
String cLine;
int n = Integer.parseInt(read.readLine());
System.out.println(n);
ExceptedValue ev = new ExceptedValue();
ev.isSelected = new int[n];
ev.relation = new int[n][n];
while ((cLine = read.readLine()) != null) {
System.out.println(cLine);
//getWays gw = new getWays();
String[] funArray = cLine.split("-");
int currentNode = Integer.parseInt(funArray[0]) -1;
ev.isSelected[currentNode] = 0;
for (int i = 0; i < n; i++) {
if(funArray[1].charAt(i)=='1')
ev.relation[currentNode][i] = 1;
else
ev.relation[currentNode][i] = 0;
}
}
ev.isSelected[0] = 1;
double expectedlenght = ev.findExpected(1,0,n);
System.out.println(expectedlenght);
}
double findExpected(double currentProbablity, int currentNode, int n) {
System.out.println("at" + currentNode);
int possibleChoice = 0;
int visitedNode = 0;
for(int i =0; i < n ; i++) {
if(relation[currentNode][i] == 1 && isSelected[i] ==0)
possibleChoice++;
if(isSelected[i] ==1)
visitedNode++;
}
if(possibleChoice == 0)
return currentProbablity*visitedNode;
else {
double currentexpected = 0.0;
for(int i =0; i < n ; i++) {
if(relation[currentNode][i] == 1 && isSelected[i] ==0) {
isSelected[i] = 1;
System.out.println("calling for" + currentNode);
currentexpected += findExpected(currentProbablity/possibleChoice,i,n);
isSelected[i] = 0;
}
}
return currentexpected;
}
}
}
Can you clarify the problem statement?
- Anonymous November 17, 2014