Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

Snakes and Ladders Matrix Problem

Find the minimum number of die rolls necessary to reach the final cell of the given Snakes and Ladders board game.

Rules are as usual. Player starts from cell one, rolls a die and advances 1-6 (a random number of) steps at a time. Should they land on a cell where a ladder starts, the player immediately climbs up that ladder. Similarly, having landed on a cell with a snake’s mouth, the player goes down to the tail of that snake before they roll the die again. Game ends when the player arrives at the last cell.

Example One

Input: A board with 20 cells, two ladders 2->19 and 12->15 and a snake 9->2.

The two-dimensional view is for our visual convenience only: there are really just 20 cells, one after another, linearly. See below in the Notes how such a board is represented in the Input Parameters.

Output: 2

Having started from cell 1, player rolls 1 and moves to cell 2. The stair takes them from cell 2 to cell 19. They then roll 1 to arrive at the last, 20th cell. The player reached the end of the board in two rolls; that’s the fewest rolls possible.

Example Two:

Input: A board with eight cells, no snakes and no ladders:

Output: 2

There are several ways to reach the last cell from the first cell in two rolls: 6+1, 5+2, 4+3, 3+4, 2+5, 1+6. No way to reach it with any fewer rolls though.

Notes

Input Parameters: Function has two arguments:

1. n, size of the board, and

2. moves, array of integers defining the snakes and ladders:

● moves[i] = -1: no ladder or snake starts at i-th cell

● moves[i]  <  i: snake from i down to moves[i]

● moves[i]  >  i: ladder from i up to moves[i]

The indices and values in moves array are zero-based, for example moves[1]=18 means there is a ladder from cell 2 up to cell 19. moves for “Example One” above looks like this:

[-1, 18, -1, -1, -1, -1, -1, -1, 2, -1, -1, 15, -1, -1, -1, -1, -1, -1, -1, -1]

Output: Function must return an integer, the minimum number of dice rolls required to reach the last cell from the first. Return -1 if the last cell cannot be reached.

Constraints:

● 1

● 0

● No snake starts from the last cell and no ladder starts from the first cell.

No snake or ladder starts from a cell where another snake or ladder arrives.

Solution

Optimal solution using BFS

Consider the entire board as a graph. All cells are nodes and there is an edge from every cell to the next 6 cells on the board, as there are 6 numbers on a dice. Whenever there is a snake or a ladder, we go to its respective ends with no cost instead of staying at its beginning. For instance, when we are at cell 24 and we roll 3 to reach cell 27, we would check if a snake or a ladder starts from cell 27: if there is, our graph would not have an edge from cell 24 to 27, but instead from 24 to the end of that snake or ladder.

We need to find the minimum distance (as measured by the number of edges) to the end cell from the start cell in the graph built like so. We can run a simple breadth first search (BFS) since we just need to count edges and don’t need to account for their length or weight. Note that we don't need to build entire graph upfront: to be more efficient the provided solution creates Node objects only as it visits cells. Once it reaches the last cell, the algorithm returns without necessarily building the entire graph of possible paths. Note that the algorithm ignores any paths to a particular node except the one that was found first. That’s because the first arrival to a node using BFS is guaranteed to use the fewest possible number of edges.

Auxiliary Space Used:

Auxiliary space is taken by array visited and linked list queue.

The visited array has n elements so it takes O(n) space.

Let’s see why the queue cannot ever have more than 6*n nodes (and therefore takes O(n) space too). Processing each node adds at most 6 new nodes to the queue, and no one node is processed more than once. Even if somehow all n nodes get processed before any nodes removed from the queue (not quite possible in practice as nodes get removed from the queue as algorithm processes them), we would have the queue with 6*n nodes and no more nodes could possibly be added to it (because visited[i] is true for all indices by then).

Total Auxiliary Space Used is O(n) + O(n) = O(n)

Space Complexity:

Auxiliary Space Used of O(n) plus input size of O(n) give us a total of O(n).

Time Complexity:

Using the same logic we used when calculating the Auxiliary Space Used we can conclude the Time Complexity of O(n).


// -------- START --------

    // An entry in queue used in BFS
    static class Node {
        int index; // Zero-based index of the cell.
        int dist; // Distance, measured in dice rolls, from the 0th cell.
    }

    static int minNumberOfRolls(int n, List moves) {
        boolean[] visited = new boolean[n]; // Java guarantees to initialize all with False.

        // Add the 0th cell to the queue as we start from there
        Queue queue = new LinkedList<>();
        Node node = new Node();
        node.index = 0;
        node.dist = 0;
        queue.add(node);
        
        // Run BFS from Node 0
        while (!queue.isEmpty()) {
            node = queue.poll();
            if (visited[node.index]) {
                // If we visited this node before we must have reached it with
                // fewer dice rolls than we have done now. No need to consider it again.
                continue;
            }

            visited[node.index] = true;

            if (node.index == n-1) {
                // We arrived at the last cell. Since we advanced one dice roll at a time,
                // current distance (number of dice rolls) from the 0th is the smallest possible.
                return node.dist;
            }
            // Add all the neighbors to the queue.
            for (int dice = 1; dice <= 6; dice++) {
                int goingTo = node.index + dice;
                if (goingTo >= n) {
                    break; // No stepping beyond the board.
                }

                // Accounting for a snake or ladder if any:
                int snakeOrLadder = moves.get(goingTo);
                if (snakeOrLadder != -1) {
                    goingTo = snakeOrLadder;
                }

                Node newNode = new Node();
                newNode.index = goingTo;
                newNode.dist = node.dist + 1; // We used one dice roll to jump from node to newNode.
                queue.add(newNode);
            }
        }

        // No way to reach
        return -1;
    }

    // -------- END --------

Try yourself in the Editor

Note: Input and Output will already be taken care of.

Snakes and Ladders Matrix Problem

Find the minimum number of die rolls necessary to reach the final cell of the given Snakes and Ladders board game.

Rules are as usual. Player starts from cell one, rolls a die and advances 1-6 (a random number of) steps at a time. Should they land on a cell where a ladder starts, the player immediately climbs up that ladder. Similarly, having landed on a cell with a snake’s mouth, the player goes down to the tail of that snake before they roll the die again. Game ends when the player arrives at the last cell.

Example One

Input: A board with 20 cells, two ladders 2->19 and 12->15 and a snake 9->2.

The two-dimensional view is for our visual convenience only: there are really just 20 cells, one after another, linearly. See below in the Notes how such a board is represented in the Input Parameters.

Output: 2

Having started from cell 1, player rolls 1 and moves to cell 2. The stair takes them from cell 2 to cell 19. They then roll 1 to arrive at the last, 20th cell. The player reached the end of the board in two rolls; that’s the fewest rolls possible.

Example Two:

Input: A board with eight cells, no snakes and no ladders:

Output: 2

There are several ways to reach the last cell from the first cell in two rolls: 6+1, 5+2, 4+3, 3+4, 2+5, 1+6. No way to reach it with any fewer rolls though.

Notes

Input Parameters: Function has two arguments:

1. n, size of the board, and

2. moves, array of integers defining the snakes and ladders:

● moves[i] = -1: no ladder or snake starts at i-th cell

● moves[i]  <  i: snake from i down to moves[i]

● moves[i]  >  i: ladder from i up to moves[i]

The indices and values in moves array are zero-based, for example moves[1]=18 means there is a ladder from cell 2 up to cell 19. moves for “Example One” above looks like this:

[-1, 18, -1, -1, -1, -1, -1, -1, 2, -1, -1, 15, -1, -1, -1, -1, -1, -1, -1, -1]

Output: Function must return an integer, the minimum number of dice rolls required to reach the last cell from the first. Return -1 if the last cell cannot be reached.

Constraints:

● 1

● 0

● No snake starts from the last cell and no ladder starts from the first cell.

No snake or ladder starts from a cell where another snake or ladder arrives.

Solution

Optimal solution using BFS

Consider the entire board as a graph. All cells are nodes and there is an edge from every cell to the next 6 cells on the board, as there are 6 numbers on a dice. Whenever there is a snake or a ladder, we go to its respective ends with no cost instead of staying at its beginning. For instance, when we are at cell 24 and we roll 3 to reach cell 27, we would check if a snake or a ladder starts from cell 27: if there is, our graph would not have an edge from cell 24 to 27, but instead from 24 to the end of that snake or ladder.

We need to find the minimum distance (as measured by the number of edges) to the end cell from the start cell in the graph built like so. We can run a simple breadth first search (BFS) since we just need to count edges and don’t need to account for their length or weight. Note that we don't need to build entire graph upfront: to be more efficient the provided solution creates Node objects only as it visits cells. Once it reaches the last cell, the algorithm returns without necessarily building the entire graph of possible paths. Note that the algorithm ignores any paths to a particular node except the one that was found first. That’s because the first arrival to a node using BFS is guaranteed to use the fewest possible number of edges.

Auxiliary Space Used:

Auxiliary space is taken by array visited and linked list queue.

The visited array has n elements so it takes O(n) space.

Let’s see why the queue cannot ever have more than 6*n nodes (and therefore takes O(n) space too). Processing each node adds at most 6 new nodes to the queue, and no one node is processed more than once. Even if somehow all n nodes get processed before any nodes removed from the queue (not quite possible in practice as nodes get removed from the queue as algorithm processes them), we would have the queue with 6*n nodes and no more nodes could possibly be added to it (because visited[i] is true for all indices by then).

Total Auxiliary Space Used is O(n) + O(n) = O(n)

Space Complexity:

Auxiliary Space Used of O(n) plus input size of O(n) give us a total of O(n).

Time Complexity:

Using the same logic we used when calculating the Auxiliary Space Used we can conclude the Time Complexity of O(n).


// -------- START --------

    // An entry in queue used in BFS
    static class Node {
        int index; // Zero-based index of the cell.
        int dist; // Distance, measured in dice rolls, from the 0th cell.
    }

    static int minNumberOfRolls(int n, List moves) {
        boolean[] visited = new boolean[n]; // Java guarantees to initialize all with False.

        // Add the 0th cell to the queue as we start from there
        Queue queue = new LinkedList<>();
        Node node = new Node();
        node.index = 0;
        node.dist = 0;
        queue.add(node);
        
        // Run BFS from Node 0
        while (!queue.isEmpty()) {
            node = queue.poll();
            if (visited[node.index]) {
                // If we visited this node before we must have reached it with
                // fewer dice rolls than we have done now. No need to consider it again.
                continue;
            }

            visited[node.index] = true;

            if (node.index == n-1) {
                // We arrived at the last cell. Since we advanced one dice roll at a time,
                // current distance (number of dice rolls) from the 0th is the smallest possible.
                return node.dist;
            }
            // Add all the neighbors to the queue.
            for (int dice = 1; dice <= 6; dice++) {
                int goingTo = node.index + dice;
                if (goingTo >= n) {
                    break; // No stepping beyond the board.
                }

                // Accounting for a snake or ladder if any:
                int snakeOrLadder = moves.get(goingTo);
                if (snakeOrLadder != -1) {
                    goingTo = snakeOrLadder;
                }

                Node newNode = new Node();
                newNode.index = goingTo;
                newNode.dist = node.dist + 1; // We used one dice roll to jump from node to newNode.
                queue.add(newNode);
            }
        }

        // No way to reach
        return -1;
    }

    // -------- END --------

Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Accelerate your Interview prep with Tier-1 tech instructors
blue tick
360° courses that have helped 14,000+ tech professionals
blue tick
100% money-back guarantee*
Register for Webinar

Recommended Posts

All Posts