Start learning free

LESSON 320 OF 321 · OBJECT-ORIENTED DESIGN - INTERVIEWS

Snakes and Ladders in Kotlin

Practice O(1)

This is a design round. You write the classes, and the interviewer checks that they behave.

Here you build the board game Snakes and Ladders, without the dice. Each roll is given to you.

The board has squares numbered from 1 to size. A ladder takes a piece up to a higher square. A snake takes it down to a lower square.

Implement two classes:

  • Board(size) makes a board with no snakes and no ladders.
  • addSnake(head, tail) adds a snake. A piece that stops on head slides down to tail.
  • addLadder(bottom, top) adds a ladder. A piece that stops on bottom climbs to top.
  • landOn(square) returns where a piece that stops on square ends up. With no snake or ladder there, that is square itself.
  • getSize() returns the number of squares.
  • Game(board, players) starts a game on that board. The players are numbered from 1.
  • roll(dice) moves the player whose turn it is. It returns that player's square after the roll.
  • position(player) returns the square that player is on.
  • turn() returns the player who rolls next.
  • winner() returns the player who won, or 0 while nobody has.
  • isOver() returns true once someone has won.

Every player starts on square 0, before the first square. Player 1 rolls first.

A roll moves the player dice squares forward. If a snake or a ladder starts there, the player takes it.

A roll that would go past the last square doesn't move the player.

A player who ends a roll on the last square wins. Then the game is over.

After each roll, the turn passes to the next player, even if nobody moved. After the last player comes player 1. After a win, the turn stays with the winner.

Once the game is over, roll changes nothing and returns -1.

The first calls go to a new Board. Then a Game starts on that board, and the other calls go to the game. Every call except addSnake and addLadder writes one line of output. Booleans are written as True and False.

 

Example 1:

Input:
Board(20)
1. addLadder(3, 12)
2. addSnake(15, 5)
3. landOn(3)
4. landOn(15)
5. landOn(7)
Game(board, 2)
6. roll(3)
7. roll(4)
8. roll(3)
9. position(1)
10. position(2)
11. turn()
Output:
12
5
7
12
4
5
5
4
2
Explanation:
Square 3 starts a ladder to 12. Square 15 starts a snake to 5.
Nothing starts on square 7, so call 5 returns 7.
In call 6, player 1 lands on 3 and climbs to 12.
In call 7, player 2 lands on 4.
In call 8, player 1 lands on 15 and slides down to 5.
Now player 2 rolls next.

Example 2:

Input:
Board(10)
1. addLadder(4, 8)
Game(board, 2)
2. roll(4)
3. roll(6)
4. roll(5)
5. roll(4)
6. isOver()
7. winner()
8. turn()
9. roll(1)
10. position(1)
Output:
8
6
8
10
True
2
2
-1
8
Explanation:
In call 2, player 1 climbs the ladder from 4 to 8.
In call 4, player 1 would reach 13, past the last square.
So player 1 stays on 8, and the turn passes.
In call 5, player 2 reaches 10, the last square.
So player 2 wins.
The turn stays with the winner, so call 8 returns 2.
The game is over, so call 9 returns -1.

Example 3:

Input:
Board(12)
1. addLadder(5, 12)
2. addSnake(11, 2)
Game(board, 3)
3. turn()
4. winner()
5. roll(6)
6. roll(1)
7. roll(2)
8. turn()
9. roll(5)
10. roll(4)
11. winner()
12. position(3)
Output:
1
0
6
1
2
1
2
12
2
2
Explanation:
Before any roll, player 1 is next and nobody has won.
After players 1, 2 and 3 roll, it is player 1's turn again.
In call 9, player 1 lands on 11 and slides down to 2.
In call 10, player 2 lands on 5 and climbs to 12, the last square.
Players 1 and 3 are both on square 2 now.

 

Constraints:

  • size is a whole number from 10 to 1,000,000.
  • players is a whole number from 2 to 10.
  • dice is a whole number from 1 to 6.
  • Every square given to a call is from 1 to size.
  • A snake's tail is lower than its head.
  • A ladder's top is higher than its bottom.
  • No snake or ladder starts on the last square.
  • A square starts at most one snake or ladder.
  • No snake or ladder ends on a square where another one starts.
  • All snakes and ladders are added before the game starts.
  • The player given to position is from 1 to players.
  • At most 100,000 calls follow the constructors.

Note:

Each call should run in O(1) time. Looking through every snake and ladder on each roll would take O(n) time, for n snakes and ladders.

STEP 1 OF 22
    Ctrl + Enter to check

    Snakes And Ladders in Kotlin

    Keep going with Kotlin1,600+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free