Google Interview Question
Software EngineersTeam: Graduate
Country: United Kingdom
Interview Type: In-Person
You could just assign infinity to cells which are the mouths of snakes, since no optimal path includes them.
Instead of an array of integers, make dp an array of structures which includes both the value and the idx of the best previous position. Then work backward from the end to retrieve the path.
A correction for the recurrence
dp[i] = min(dp[i], dp[x] + 1) ....
This is because you could come to i due to a ladder
@nilkn, you can completely disregard snakes as the dp[] I've defined is the optimal # rolls to get to position i. If you get there and slide down a snake, that doesn't affect that you still had # rolls to get there.
@mithya this case is taken into account by the "If x is the top of a ladder, x = j where j is the bottom of the ladder", but you're right in that it could be written more formally.
Actually, looking at it again, snakes do need to be accounted for. tjcbs2's suggestion is good to handle this.
Many people wrote the answer. I thought I share mine as well. I got the idea from your answer BTW.
public int getMinDiceToWin(int size, Map<Integer, Integer> ladders, Map<Integer, Integer> snakes) {
int[] minDice = new int[size + 1];
for (int i = 2; i <= size; i++) {//i==1 needs zero move which already is filled
//if this location is a snake mouth then put it infinity dice for not being used later
if (snakes.values().contains(i)) {
minDice[i] = Integer.MAX_VALUE;
continue;
}
int min = Integer.MAX_VALUE;
//checking all 6 locations before current location
for (int j = 1; j <= 6; j++) {
if (i - j > 0 && i - j <= size) {
if (min > minDice[i - j] + 1) {
min = minDice[i - j] + 1;
}
}
}
//Checking for ladder in current location
Integer ladderBottom = ladders.get(i);
if (ladderBottom != null) {
if (min > minDice[ladderBottom]) {
min = minDice[ladderBottom];
}
}
minDice[i] = min;
}
return minDice[size];
}
Dynamic Programming :
Opt[i] is the number of steps(rules) required between i and 100
Base cases:
Opt[100]=0
Opt[i]=j if ith position has a ladder and j is the other end of ladder, similarly for snake too
recursive rule
Opt[i]=max(1+Opt(k)) { 0< k < 18}
Assuming that we can get min of 1 and max of 17 (6+6+5) in one rule
Find Opt[1]
Convert the game board into a directed graph, one node for each cell. If a node doesn't have any snakes or ladders on it, then it will have six outgoing edges to the next six cells, respectively. If it has an ascending ladder, then it will have just one outgoing edge. Likewise, if it has a descending snake, then it will have just one outgoing edge.
The number of edges is at worst O(6|V|) = O(|V|). So running Dijkstra's algorithm on this graph, using a Fibonacci heap, would give us a running time of O(|E| + |V| * log |V|) = O(|V| * log |V|). So basically O(N log(N)) where N is the number of cells in the grid.
I made a mistake. I meant O(N) for the last running time. It's
O(|E| + |V| * log |V|) -- running time of Dijkstra's algorithm
= O(|V| + |V| * log |V|) -- because |E| = O(|V|)
= O(|V|) -- |V| is the more dominant factor
= O(N) -- N = |V|
Gah, I'm crazy. It was right the first time.
Looks like dynamic programming might be a more efficient solution though none of the DP solutions posted actually solves the full problem as stated.
i thought of the same approach. consider it like a graph and find the shortest distance. can you explain why dynamic prog. is better that this solution?
No need for Dijkstra, Breadth First Search with a simple Queue is enough because the edges of the graph are 1 unit long (1 dice roll).
public static int roles(Struct[][] board){
if(board == null || board.length == 0 || board[0].length == 0 || board.length != board[0].length)
return 0;
int n = board.length;
int[] roles = new int[n * n];
for(int i = 0; i < n * n; i++){
int x = i / n;
int y = (x % 2 != 0) ? (n - 1 - i % n) : i % n;
if(i < 6){
roles[i] = board[x][y].s.equals("SU") ? Integer.MAX_VALUE / 2 : 1;
}
else{
roles[i] = Integer.MAX_VALUE;
for(int j = i - 6; j < i; j++)
roles[i] = Math.min(roles[i], roles[j] + 1);
if(board[x][y].s.equals("LU"))
//in case the lower end of the ladder is the upper end of the
//snake
roles[i] = Math.min(ladder(board, x, y, roles), roles[i]);
else if(board[x][y].s.equals("SU"))
roles[i] = Integer.MAX_VALUE / 2;
}
}
return roles[n * n - 1];
}
private static int ladder(Struct[][] board, int x, int y, int[] roles){
int n = board.length;
int xc = board[x][y].x;
return xc % 2 != 0 ? roles[xc * n + (n - 1 - board[x][y].y)]
: roles[xc * n + board[x][y].y];
}
/**
* consists the string which represents the status of the square:
* "SU": snake upper side
* "SL": snake lower side
* "LU": ladder upper side
* "LL": ladder lower side
* as well as the coordinates of its corresponding end
* e.g., "SU", 1, 1 indicates the lower side of the snake is at x = 1, y = 1
* @author shirleyyoung
*
*/
private static class Struct{
String s;
//the coordinate of the corresponding square
int x;
int y;
public Struct(String s, int x, int y){
this.s = s;
this.x = x;
this.y = y;
}
}
Why do we need to complicate this so much.
Lets keep the solution simple.
probability of your roll is 1-6.
roll value [1-6]
for each position
starting from 1 remembering the snakes and ladders starts at 1.
while current position < 100
i will check for each position from
if currentPosition<100 && currentPoint to currentPoint+6
how many ladders to i have ?
if ladders ==0
roll to max position with out a snake in 6;
else if ladders ==1
roll ladders.get(0).getIntialPosition();
currentPosition = ladders.get(0).getInitialPosition();
jump to ladders.get(0).getJumpPosition()
currentPosition = ladders.get(0).getJumpPosition();
return to step 1;
else if ladders > 1
maxValue= currentPosition;
for each ladder in ladders
if(maxValue<ladder.getJumpPosition())
maxValue = ladder.getJumpPosition();
get ladder with maxValue;
currentPosition = ladder.getInitialPosition;
get max value;
roll ladder.getIntialPosition();
currentPosition = ladder.getInitialPosition();
jump to ladder.getJumpPosition()
currentPosition = ladders.getJumpPosition();
return to step 1;
Its very crude in its form but implemented it will do the job.
Algo
1. ittrate once and get the info's of pairs where it has very high difference : ex ladder from 61 to 99 make a list and of all pair ladders and sort them descending order of difference ex (99-61)
2. now choose top most non looping pairs from above data in consideration and fill up the space between ladders by n (0<n<7) blocks which doesn't contains snake.
complexity - {step 1} + {step 2} ={ (o)n + (o)mlogm (m - number of ladders) }+ {constant} =~ (o)n
Use the A* Search Algorithm,
* Each node in the search tree represents a position on the board
* Depending on current position, the successor function will return the next 6 positions (6 possible moves based on the dice). If the successor is attached to a ladder or a snake, the Node should reflect the position after the ladder or snake has been taken into account.
* G = how many rolls has it taken me to get here
* H = heuristic to indicate how far away to my goal, ie. the finish square
* F = G + H, we pick Minimum(F(successor)) as the next move
public class Solver
{
public List<Square> Solve(Board board)
{
var prevStep = new Dictionary<Node, Node>();
var openList = new List<Node>();
var closedList = new List<Node>();
openList.Add(new Node { Position = board.Start });
Node current = null;
while (openList.Count > 0)
{
Node bestNode = PopBestNode(openList);
prevStep[bestNode] = current;
current = bestNode;
closedList.Add(current);
if (current.Position.Equals(board.Finish))
{
var path = new List<Node>();
path.Add(current);
while (prevStep[current] != null)
{
current = prevStep[current];
path.Insert(0, current);
}
return path.Select(n => n.Position).ToList();
}
IEnumerable<Node> successors = GetSuccessors(current, board);
foreach (Node successor in successors)
{
if (closedList.Contains(successor)) continue;
successor.G = GCalc(current, successor);
successor.H = HCalc(successor, board);
successor.F = successor.G + successor.H;
openList.Add(successor);
}
}
throw new Exception("Unable to find any path's to the finish.");
}
private Node PopBestNode(List<Node> nodes)
{
Node best = nodes.OrderBy(n => n.F).First();
nodes.Remove(best);
return best;
}
private IEnumerable<Node> GetSuccessors(Node current, Board board)
{
const int MaxDice = 6;
int distToFinish = Math.Abs(board.Finish.X - current.Position.X);
int max = MaxDice > distToFinish ? distToFinish : MaxDice;
for (int i = 1; i <= max; i++)
{
Square square = board.LandingSquareFor(current.Position, i);
yield return new Node { Position = square };
}
}
private double GCalc(Node current, Node successor)
{
return current.G + 1;
}
private double HCalc(Node successor, Board board)
{
return Math.Abs(board.Finish.X - successor.Position.X);
}
}
public class Square
{
public int X { get; set; }
public Square(int x)
{
this.X = x;
}
}
public class Snake
{
public Square Head { get; set; }
public Square Tail { get; set; }
}
public class Ladder
{
public Square Start { get; set; }
public Square End { get; set; }
}
public class Board
{
public Snake[] Snakes { get; internal set; }
public Ladder[] Ladders { get; internal set; }
public Square[] Squares { get; internal set; }
public Square Start { get { return Squares.First(); } }
public Square Finish { get { return Squares.Last(); } }
public Square LandingSquareFor(Square current, int diceValue)
{
Square landingSquare = null;
for (int i = 0; i < Squares.Length; i++)
{
if (Squares[i].Equals(current))
{
int landingIndex = i + diceValue;
if (landingIndex >= Squares.Length)
landingIndex = Squares.Length - 1 - (landingIndex - Squares.Length + 1);
if (landingIndex < 0) landingIndex = 0;
landingSquare = Squares[landingIndex];
break;
}
}
if (landingSquare == null) throw new Exception("Unable to find current square.");
Square snakeEnd = Snakes
.Where(s => s.Head.Equals(landingSquare))
.Select(s => s.Tail)
.SingleOrDefault();
if (snakeEnd != null) return snakeEnd;
Square ladderEnd = Ladders
.Where(l => l.Start.Equals(landingSquare))
.Select(l => l.End)
.SingleOrDefault();
if (ladderEnd != null)
return ladderEnd;
return landingSquare;
}
}
public class Node
{
public Node() { }
public Node(Square position)
{
this.Position = position;
}
public Square Position { get; set; }
public double F { get; set; }
public double G { get; set; }
public double H { get; set; }
public override bool Equals(object obj)
{
if (obj is Node)
return ((Node)obj).Position.X == Position.X;
return base.Equals(obj);
}
public override int GetHashCode()
{
return Position.X.GetHashCode();
}
}
[TestClass]
public class SolveTest
{
[TestMethod]
public void Solve_Basic_IsOptimal()
{
var squares = new[]
{
new Square(0),
new Square(1),
new Square(2),
new Square(3),
new Square(4),
new Square(5),
new Square(6),
new Square(7),
new Square(8),
new Square(9),
new Square(10),
new Square(11),
new Square(12),
new Square(13),
};
var board = new Board
{
Squares = squares,
Snakes = new[] {
new Snake { Head = squares[1], Tail = squares[0] } ,
},
Ladders = new [] { new Ladder { Start = squares[4], End = squares[11]}},
};
var solver = new Solver();
List<Square> bestpath = solver.Solve(board);
foreach (Square s in bestpath)
Console.WriteLine(s.X);
Assert.AreEqual(0, bestpath[0].X);
Assert.AreEqual(11, bestpath[1].X);
Assert.AreEqual(13, bestpath[2].X);
}
}
Your H-function is invalid. For A* to find the optimal path, the H-function must never overestimate the remaining distance. Since a ladder could jump us to the last square at any roll, the H-function must always return 1. (since the minimum number of rolls is always 1 and a ladder could theoretically jump us to the end)
Case 1) The board is a two dimensional array of vertexes. vertex arr[x][y] will have directed
edges of length 1 to any vertex reachable by one role of the dice. (role values 1,2,3,4,5,6)
Case 2) Ladder also is a directed edge and length is 1.
Case 3) Snake also has a directed edge with length 1.
Now run BFS from source and as the destination is reached count the levels.
Case 1) The board is a two dimensional array of vertexes. vertex arr[x][y] will have directed
edges of length 1 to any vertex reachable by one role of the dice. (role values 1,2,3,4,5,6)
Case 2) Ladder also is a directed edge and length is 1.
Case 3) Snake also has a directed edge with length 1.
Now run BFS from source and as the destination is reached count the levels.
int[] diceRoll = {1, 2, 3, 4, 5, 6};
private int getMinRoll(int start, int end, HashMap<Integer, Integer> ladderSnake, HashMap<Integer, Boolean> visitedIndex)
{
if(visitedIndex.containsKey(start))
{
return 9999999;
}
HashMap<Integer, Boolean> newVisitedIndex = new HashMap<Integer, Boolean>(visitedIndex);
newVisitedIndex.put(start, false);
if(start >= end)
return 0;
if(end - start <=6)
return 1;
ArrayList<Integer> arr = new ArrayList<Integer>();
for(int roll : diceRoll )
{
int rollTo = start+ roll;
if(ladderSnake.containsKey(start+roll))
{
rollTo = ladderSnake.get(start+roll);
}
arr.add(rollTo);
}
ArrayList<Integer> numRollList = new ArrayList<Integer>();
for(int newStart : arr)
{
numRollList.add( getMinRoll(newStart, end, ladderSnake, newVisitedIndex) + 1);
}
return Collections.min(numRollList);
}
public static void main(String[] args) {
FindMinRollLadderAndSnake minRoll = new FindMinRollLadderAndSnake();
HashMap<Integer, Integer> ladderSnake = new HashMap<Integer, Integer>();
HashMap<Integer, Boolean> visitedIndex = new HashMap<Integer, Boolean>();
ladderSnake.put(1, 4);
ladderSnake.put(3, 10);
ladderSnake.put(6, 7);
ladderSnake.put(11, 18);
ladderSnake.put(21, 14);
ladderSnake.put(15, 12);
System.out.println(minRoll.getMinRoll(0, 23, ladderSnake, visitedIndex));
}
Assume that the input board is given as an array of integers.
So, array(i) -> the number of steps infront(ladder)/backwards(snake) from 'i'.
So, if there is no snake/ladder , then array(i) = 0.
If there is a snake from 5 to 3, then array(5) = -2.
Assuming the above, we can use the DP as
optimalRole(i+j+ array(i+j)) = Min(optimalRole(i+j+array(i+j)), optimalRole(i)+1).
public static int optimalRoles(int[] array) {
int[] optimalMoves = new int[array.length];
for (int i = 1; i < optimalMoves.length;i++) {
optimalMoves[i] = Integer.MAX_VALUE;
}
optimalMoves[0] = 0;
for (int i = 0; i < array.length; i++) {
for (int j = 1;j <= 6; j++) {
if ((i +j < array.length) && (i + j + array[i+j] < array.length)) {
optimalMoves[i+j + array[i+j]] = Math.min( optimalMoves[i+j+array[i+j]], optimalMoves[i] + 1);
}
}
}
return optimalMoves[array.length - 1];
}
However, if there is a configuration where 10 ->20 ->30 , then landing on 10 takes you to 30. (i.e.. ladder multiple times or so .. ).
We can solve the same with a function to calculate resultant Index
calculateResultantIndex(int i) {
while (array(i) + i ! =0)
i = array(i);
}
#include <iostream>
using namespace std;
int MinNumMovesToEnd[101];
int LandingSquare[101];
int BestNextLandingSquare[101];
int FindMinMovestoEnd()
{
int currentPos = 0;
int BestLandingPos = 0;
int NumOfMoves = findMinMovesToEnd(currentPos, BestLandingPos);
BestNextLandingSquare[0] = BestLandingPos;
return NumOfMoves;
}
int findMinMovesToEnd(int currentPos, int& BestLandingPos)
{
int MinMoves = 99999;//some large number
for (int i = 1; i <= 6;i++)
{
if (currentPos + i > 100)
{
break;
}
int landingPos = LandingSquare[currentPos + i];
if (landingPos!=0 && MinNumMovesToEnd[landingPos] == 0)
{
int BestNextLanding = 0;
int NumMovesToEnd = findMinMovesToEnd(landingPos, BestNextLanding);
if (MinNumMovesToEnd[landingPos] > NumMovesToEnd)
{
MinNumMovesToEnd[landingPos] = NumMovesToEnd;
BestNextLandingSquare[landingPos] = BestNextLanding;
}
}
if (MinMoves>MinNumMovesToEnd[landingPos])
{
MinMoves = MinNumMovesToEnd[landingPos];
BestLandingPos = landingPos;
}
}
return MinMoves+1;
}
int _tmain(int argc, _TCHAR* argv[])
{
for (int i = 0; i < 100; i++)
{
MinNumMovesToEnd[i] = 0;//default value. if not 0 then it is min value
LandingSquare[i]=i;//assuming no snakes and ladders
}
//add code for setting int LandingSquare[100];
cout<<FindMinMovestoEnd();
return 0;
}
In Below Code
LandingSquare array will contain where u move once u land in square i.
i.e if there is a ladder at i LandingSquare of i will return some value i+x and if there is a snake some i-y and if there is nothing u will get i.
After the algo is complete MinNumMovesToEnd will contain min number of moves to finish from square i. and BestNextLandingSquare will have best position after i from where u can reach last position fast.
In this way you can trace all the path to finish in minimum moves
#include <iostream>
using namespace std;
int MinNumMovesToEnd[101];
int LandingSquare[101];
int BestNextLandingSquare[101];
int FindMinMovestoEnd()
{
int currentPos = 0;
int BestLandingPos = 0;
int NumOfMoves = findMinMovesToEnd(currentPos, BestLandingPos);
BestNextLandingSquare[0] = BestLandingPos;
return NumOfMoves;
}
int findMinMovesToEnd(int currentPos, int& BestLandingPos)
{
int MinMoves = 99999;//some large number
for (int i = 1; i <= 6;i++)
{
if (currentPos + i > 100)
{
break;
}
int landingPos = LandingSquare[currentPos + i];
if (landingPos!=0 && MinNumMovesToEnd[landingPos] == 0)
{
int BestNextLanding = 0;
int NumMovesToEnd = findMinMovesToEnd(landingPos, BestNextLanding);
if (MinNumMovesToEnd[landingPos] > NumMovesToEnd)
{
MinNumMovesToEnd[landingPos] = NumMovesToEnd;
BestNextLandingSquare[landingPos] = BestNextLanding;
}
}
if (MinMoves>MinNumMovesToEnd[landingPos])
{
MinMoves = MinNumMovesToEnd[landingPos];
BestLandingPos = landingPos;
}
}
return MinMoves+1;
}
int _tmain(int argc, _TCHAR* argv[])
{
for (int i = 0; i < 100; i++)
{
MinNumMovesToEnd[i] = 0;//default value. if not 0 then it is min value
LandingSquare[i]=i;//assuming no snakes and ladders
}
//add code for setting int LandingSquare[100];
cout<<FindMinMovestoEnd();
return 0;
}
Dynamic programming :-
O(n), n=num of grids in the game
//+ve=>ladder, -ve=>snake, 0=>neither
LadderSnakeValue[i] = +/-K;
//initialize first roll consequences
MinRolls[100]=0;
MinRolls[99->94]=1;
for(int i=93; i>0; i--){
int minRolls=INT_MAX;
//find min of all possible rolls
for(int roll=1;roll<=6;roll++){
int reachable;
if(LadderSnakeValue[i+roll] < 0) //Snake
continue;
else{
reachable = LadderSnakeValue[i+roll]+i; //add ladder value to current position
if(MinRolls[reachable] + 1< minRolls) minRolls = 1+MinRolls[reachable]; //1 for current roll + num of min rolls from climbed position
}
}
MinRolls[i]=minRolls;
}
return MinRolls[1];
Use bottom-up dynamic programming to calculate the min number of rolls to get to position i
- JW March 26, 2015Start with dp[0] = 0
Then:
dp[i] = min(dp[x] + 1 where x >= 0 and x = i-1, i-2, i-3, i-4, i-5, i-6 if x is not at the top of a ladder)
If x is the top of a ladder, x = j where j is the bottom of the ladder
Return dp[k] (k is the last position on the board) + 1
Time complexity: O(n)