Flipkart Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
Use dynamic programming :
Following is the algorithm :
Let B[100] is the matrix(I am representing the matrix(10*10) as an array(with Mat[j][k] = B[i] where i = 10*(j-1) + k))
A[1] = 1;A[2] = 1;A[3] = 1;A[4] = 1;A[5] = 1;A[6] = 1;
for i=7:100
if B[i] != -1 // -1 to represent snake
A[i] = A[i-1] + 1;
for j=i-2:i-7
if A[i] > A[j] + 1
A[i] = A[j] + 1;
else
A[i] = MAX /// this is to ignore the value when we calculate minimum.
return A[100]
Here we don't have to consider expectation, as we only need to tell minimum number of dice rolling,
We have given MAT[][] as the information of the 10x10 grid, information are like where are snake, or where are ladders, etc.
B is just an abstraction of matrix MAT into an array, where the index conversation is done by B[i] = MAT[j][k], where i = 10*(j-1) + k, in simple scene it is just to consider the matrix as an array.
A[i] will give you minimum number of dice rolling require to reach at i(1<=i<=100)
And expectation is in terms of probability, but it is not required here.
We have 100 squares an some number of ladders leaving some square and arriving at another square.
Form a graph with 100 vertices. From vertex 'm' there is an edge to any of the vertices 'm+1' to 'm+6' (you can get to the corresponding squares from square 'm' in one roll). Now if a ladder leaves square 'l' for square 'a' do this: on the graph remove all edges ending at vertex 'l' and add new edges ending at vertex 'a'. For instance, the edge between 'l-3' and 'l'is replaced with an edge between 'l-3' and 'a'. Note that vertex 'l' will be removed.
The minimum number of die rolls is equal to the shortest path from vertex 1 to vertex 100.
You can model the problem as a directed weighted graph as follows.
1. Each number 1 ,2,3...100 represents a vertex say v1,v2,v3...v100.
2. If there is a ladder from a node vi to vj , there is an edge from vi to vj with weight vj-vi.
3. If there is a snake from a node vi to vj , there is an edge from vi to vj with weight vi-vj.
4. For any two consecutive nodes vi,vi+1 such that neither vi nor vi+1 have a ladder or a snake there is an edge from vi to vi+1 with weight 1.
For this graph problem now reduces to finding shortest path between v0 and v100.
Snakes and Ladder via DP
B[i] contains the snakes and ladder board in flat form (1 to 100). It contains -1 to denote there's a snake and N to denote there's a ladder where N is the number to which that ladder ends, and 0 otherwise.
A[i] where i is from 1 to 100 stores the min number of dice rolls to reach i from start.
A[i] for i = 1 to 100 is INT_MAX.
MinDiceRolls (Psuedocode)
{
for(int i = 1 to 100)
{
if(B[i] == -1) // its a snake and thus, we don't consider this node
continue;
if(B[i] != 0) // ladder
{
// B[i] will always be having the number greater than i as its the point where ladder ends
A[B[i]] = MIN(A[i-1], A[i-2], A[i-3], A[i-4], A[i-5], A[i-6]) + 1; // i.e. equal to min number of dice rolls that would have been required to reach A[i] (if a ladder would not have been there). Please make sure that index does not reach < 1 and A[i] is != -1, ignore that if that's the case.
A[i] = -1; // implies we can never reach this node in any number of dice rolls as this node has ladder.
}
else
{
// normal case
A[i] = MIN(A[i-1], A[i-2], A[i-3], A[i-4], A[i-5], A[i-6]) + 1;
}
}
return A[100];
}
dijkstra's algorithm for shortest path. O(vlogv).
as the edge weights are integers from 1-6, its O(v).
Can you explain with an example. Suppose I have a board with a ladder from 2 to 100, then answer should be 2 i.e. 1->2->100. But if I understood your solution, the answer would be 1+3+5+...99
Consider the board as directed graph.
- SR November 23, 20121. k is linked to k + 1 k + 2, k + 3, k + 4, k + 5, k +6 because from k you can reach these nodes in one throw of dice.
2. If any of these neighbors of k has a ladder which takes you to j, then j becomes the neighbor instead of the base of the ladder. Lets say k + 3 node takes you to j node, then instead of k + 3, j is the neighbor of k.
3. Similarly if any of the neighbors of k has a snake which takes you to l, then l is a neighbor of k.
Using these conditions, build the graph. Now this is transformed into a Shortest path between two nodes in a directed graph problem.