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:
new Board(size)makes a board with no snakes and no ladders.AddSnake(head, tail)adds a snake. A piece that stops onheadslides down totail.AddLadder(bottom, top)adds a ladder. A piece that stops onbottomclimbs totop.LandOn(square)returns where a piece that stops onsquareends up. With no snake or ladder there, that issquareitself.GetSize()returns the number of squares.new 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()returnstrueonce 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: new Board(20) 1. AddLadder(3, 12) 2. AddSnake(15, 5) 3. LandOn(3) 4. LandOn(15) 5. LandOn(7) new 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: new Board(10) 1. AddLadder(4, 8) new 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: new Board(12) 1. AddLadder(5, 12) 2. AddSnake(11, 2) new 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:
sizeis a whole number from 10 to 1,000,000.playersis a whole number from 2 to 10.diceis a whole number from 1 to 6.- Every square given to a call is from 1 to
size. - A snake's
tailis lower than itshead. - A ladder's
topis higher than itsbottom. - 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
playergiven toPositionis from 1 toplayers. - 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.
Free plan: 30 tutor messages. PRO is unlimited.
