Problem:
Find the smallest number of jumps (i.e. optimal number of dice throws) needed to win a snakes and ladders game. Assume you are given a board with all the necessary inputs like start/end positions of all ladders and snakes.
Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...
DAG, with each number as a node. A number x is linked to x + 1, x + 2, .. x + 6 with edge 1. A number with snake's head is linked only to the snakes tail with edge weight 0. A number with ladder's tail is linked only to the number with ladder's head with weight 0.
ReplyDeleteBFS with destination = final point.
Maximum number of edges from a vertex = 6. At worse, I travel each edge exactly once. So, at definitely it is O(n). Although, I am reasonably sure, the complexity in this case will come out to be much lesser.
Its not a DAG as graph is not acyclic!
Deletethis question also came during flipkart hiring process at other IITs , i also thought it was a DAG, but one can easily form a cycle here using a snake ,plus the edge weights were different so went with dijkstra later , (however wasn't able to code dijkstra during the time limit , so had to contend with BFS code which wasnt giving full score :/ )
ReplyDeleteI would say it seems like an application of Djiktra's algorithm with source as 0 and destination as 100. Considering every move as unit cost, we just have to find the shortest path... And everything needed is given as input hence we have a graph with edges and weights.
ReplyDelete