## Flipkart Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

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

Consider the board as directed graph.
1. 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.

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

Use dynamic programming :
Following is the algorithm :

``````Let B 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;A = 1;A = 1;A = 1;A = 1;A = 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``````

Here we don't have to consider expectation, as we only need to tell minimum number of dice rolling,

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

Can you explain the meaning of :

A
B
Mat
expectation

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

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.

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

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.

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

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.

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

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;

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

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

BFS should be used.snakes head and ladders start should be replaced by their respective other ends in the graph.

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

{{
test

}}

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

consider board as a graph ,
when there is a ladder , the node at the base points to the node at top (from ladder base to ladder top)..
same way would be used for snakes.

so all we have to do is find shortest path (kruskal or dijikstra),and later divide by 6

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

dijkstra's algorithm for shortest path. O(vlogv).
as the edge weights are integers from 1-6, its O(v).

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

How exactly are you building your graph? What are the weights on the edges? How did it go from O(vlogv) to O(v)?

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

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

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

off topic comment !
Vikas,
Thru whom did you get this Flipkart intvw call? Have been searching for a source but no luck...

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.