Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
we can impliment it by graph bfs.
public void snackAndLadderProblem(){
Integer[] map = new Integer[30];
map[2]=21;
map[4]=7;
map[10]=25;
map[19]=28;
map[16]=3;
map[18]=6;
map[20]=8;
map[26]=0;
int minDiceThrown = 30;
System.out.println("min steps needed to finish snack and ladder game:-
"+this.snackAndLadderCheckForNextSixElement(map, minDiceThrown, 0, 0));
}
private int snackAndLadderCheckForNextSixElement(Integer[] map, int
minDiceThrown, int startingPoint, int currentCountOfDiceThrown){
if(currentCountOfDiceThrown > minDiceThrown){
return minDiceThrown;
}
for (int i = 1; i <= 6; i++) {
int currentIndex = startingPoint+i;
if(currentIndex >= map.length){
return currentCountOfDiceThrown+1;
}
if(currentIndex < map.length && map[currentIndex]!= null ){
int diceThrownAfterThisDip =
this.snackAndLadderCheckForNextSixElement(map,
minDiceThrown, map[currentIndex], currentCountOfDiceThrown+1);
if(diceThrownAfterThisDip < minDiceThrown){
minDiceThrown = diceThrownAfterThisDip;
}
}
}
int lastIndex = startingPoint+6;
while(lastIndex > map.length || map[lastIndex]!=null){
lastIndex--;
}
int diceThrownAfterThisDip =
this.snackAndLadderCheckForNextSixElement(map, minDiceThrown,
lastIndex, currentCountOfDiceThrown+1);
if(diceThrownAfterThisDip < minDiceThrown){
minDiceThrown = diceThrownAfterThisDip;
}
return minDiceThrown;
}
sassad
- Anonymous March 31, 2017