## Google Interview Question for Software Engineers

Country: United Kingdom
Interview Type: In-Person

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

Use bottom-up dynamic programming to calculate the min number of rolls to get to position i
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)

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

This doesn't return the actual path and it also doesn't take into account snakes.

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

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.

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

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

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

@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.

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

Actually, looking at it again, snakes do need to be accounted for. tjcbs2's suggestion is good to handle this.

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

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
}
}
minDice[i] = min;
}
return minDice[size];
}``````

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

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.

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

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|

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

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.

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

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?

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

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).

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

Dijiktra algorithm wont work here . We have to use BFS as it calculates min no of edges to reach from vertex to vertex B . Dijiktra only works to path shortest path len when edge lengths are unequal.

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

``````public static int roles(Struct[][] board){
if(board == null || board.length == 0 || board.length == 0 || board.length != board.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
* 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;
}
}``````

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

Dynamic Programming :

Opt[i] is the number of steps(rules) required between i and 100

Base cases:
Opt=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

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

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 ?

roll to max position with out a snake in 6;
maxValue= currentPosition;
get max value;

Its very crude in its form but implemented it will do the job.

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

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

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

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;

if (current.Position.Equals(board.Finish))
{
var path = new List<Node>();
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;
}
}
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 Square Start { get; set; }
public Square End { get; set; }
}
public class Board
{
public Snake[] Snakes { 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
.Select(s => s.Tail)
.SingleOrDefault();
if (snakeEnd != null) return snakeEnd;

.Where(l => l.Start.Equals(landingSquare))
.Select(l => l.End)
.SingleOrDefault();

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, Tail = squares } ,
},
Ladders = new [] { new Ladder { Start = squares, End = squares}},
};
var solver = new Solver();
List<Square> bestpath = solver.Solve(board);
foreach (Square s in bestpath)
Console.WriteLine(s.X);
Assert.AreEqual(0, bestpath.X);
Assert.AreEqual(11, bestpath.X);
Assert.AreEqual(13, bestpath.X);
}
}``````

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

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)

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

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.

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

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.

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

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

ArrayList<Integer> numRollList = new ArrayList<Integer>();
for(int newStart : arr)
{
}

return Collections.min(numRollList);
}

public static void main(String[] args) {

HashMap<Integer, Integer> ladderSnake = new HashMap<Integer, Integer>();
HashMap<Integer, Boolean> visitedIndex = new HashMap<Integer, Boolean>();

}``````

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

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

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

``````#include <iostream>

using namespace std;

int MinNumMovesToEnd;
int LandingSquare;
int BestNextLandingSquare;

int FindMinMovestoEnd()
{
int currentPos = 0;
int BestLandingPos = 0;
int NumOfMoves = findMinMovesToEnd(currentPos, BestLandingPos);
BestNextLandingSquare = 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
}

//add code for setting   int LandingSquare;
cout<<FindMinMovestoEnd();
return 0;
}``````

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

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;
int LandingSquare;
int BestNextLandingSquare;

int FindMinMovestoEnd()
{
int currentPos = 0;
int BestLandingPos = 0;
int NumOfMoves = findMinMovesToEnd(currentPos, BestLandingPos);
BestNextLandingSquare = 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
}

//add code for setting   int LandingSquare;
cout<<FindMinMovestoEnd();
return 0;
}``````

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

Dynamic programming :-

O(n), n=num of grids in the game

``````//+ve=>ladder, -ve=>snake, 0=>neither

//initialize first roll consequences
MinRolls=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;
continue;
else{
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;``````

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.