Low Level Design (LLD) Interview Questions
Design Snake and Ladder
Tier: EssentialDifficulty: EasyAsked of: Junior, MidAsked at: Amazon, Adobe, Microsoft, Flipkart, Swiggy, Zynga
Design a turn based board game where a die moves each player forward. Landing on a ladder moves them up, and landing on a snake moves them down.
The problem
Players start at square 0. If a player rolls 3 and square 3 has a ladder to 22, they finish the turn on 22. A player on 98 needs exactly 2 to reach 100. Rolling 4 leaves them on 98.
Start with two or more players, one die and a configurable final square. One roll follows at most one snake or ladder. A six does not give an extra turn in this agreed rule set. The caller supplies the roll so the game is easy to test.
How to explain the design
“I store each player's position and whose turn it is. I also keep a map from the start of each snake or ladder to its destination. A turn adds the die roll, checks the board boundary, applies one jump and checks for a winner. Otherwise it advances to the next player.”
One class is enough for these rules. The map treats snakes and ladders the same way because both move a player from one square to another.
Walk through a turn
- Check that the game is running and the caller is the current player.
- Check that the roll is between 1 and 6.
- Move if the roll does not go beyond the final square, then apply a jump if present.
- Declare the player the winner on the final square. Otherwise advance the turn.
Interview implementation
Keep positions private so only valid turns can move a player.
Java
SnakeAndLadder.java
package interview.snakes;
import java.util.Map;
public class SnakeAndLadder {
private final int[] positions;
private final int lastSquare;
private final Map<Integer, Integer> jumps;
private int turn;
private Integer winner;
public SnakeAndLadder(int players, int lastSquare, Map<Integer, Integer> jumps) {
if (players < 2 || lastSquare <= 1) throw new IllegalArgumentException("Invalid game");
for (var jump : jumps.entrySet()) {
if (jump.getKey() < 1 || jump.getKey() >= lastSquare || jump.getValue() < 1 ||
jump.getValue() > lastSquare || jump.getKey().equals(jump.getValue())) {
throw new IllegalArgumentException("Invalid snake or ladder");
}
}
positions = new int[players];
this.lastSquare = lastSquare;
this.jumps = Map.copyOf(jumps);
}
public int position(int player) { return positions[player]; }
public int turn() { return turn; }
public Integer winner() { return winner; }
public int move(int player, int roll) {
if (winner != null || player != turn) throw new IllegalStateException("Not this player's turn");
if (roll < 1 || roll > 6) throw new IllegalArgumentException("Invalid roll");
int destination = positions[player] + roll;
if (destination <= lastSquare) positions[player] = jumps.getOrDefault(destination, destination);
if (positions[player] == lastSquare) winner = player;
else turn = (turn + 1) % positions.length;
return positions[player];
}
}
package interview.snakes;
import java.util.Map;
public class SnakeAndLadder {
private final int[] positions;
private final int lastSquare;
private final Map<Integer, Integer> jumps;
private int turn;
private Integer winner;
public SnakeAndLadder(int players, int lastSquare, Map<Integer, Integer> jumps) {
if (players < 2 || lastSquare <= 1) throw new IllegalArgumentException("Invalid game");
for (var jump : jumps.entrySet()) {
if (jump.getKey() < 1 || jump.getKey() >= lastSquare || jump.getValue() < 1 ||
jump.getValue() > lastSquare || jump.getKey().equals(jump.getValue())) {
throw new IllegalArgumentException("Invalid snake or ladder");
}
}
positions = new int[players];
this.lastSquare = lastSquare;
this.jumps = Map.copyOf(jumps);
}
public int position(int player) { return positions[player]; }
public int turn() { return turn; }
public Integer winner() { return winner; }
public int move(int player, int roll) {
if (winner != null || player != turn) throw new IllegalStateException("Not this player's turn");
if (roll < 1 || roll > 6) throw new IllegalArgumentException("Invalid roll");
int destination = positions[player] + roll;
if (destination <= lastSquare) positions[player] = jumps.getOrDefault(destination, destination);
if (positions[player] == lastSquare) winner = player;
else turn = (turn + 1) % positions.length;
return positions[player];
}
}
Kotlin
SnakeAndLadder.kt
package interview.snakes
class SnakeAndLadder(private val players: Int, private val lastSquare: Int, jumps: Map<Int, Int>) {
private val jumps = jumps.toMap()
private val positions: IntArray
var turn = 0
private set
var winner: Int? = null
private set
init {
require(players >= 2 && lastSquare > 1)
require(jumps.all { (from, to) -> from in 1 until lastSquare && to in 1..lastSquare && from != to })
positions = IntArray(players)
}
fun position(player: Int) = positions[player]
fun move(player: Int, roll: Int): Int {
check(winner == null && player == turn) { "Not this player's turn" }
require(roll in 1..6)
val destination = positions[player] + roll
if (destination <= lastSquare) {
positions[player] = jumps[destination] ?: destination
}
if (positions[player] == lastSquare) winner = player
else turn = (turn + 1) % players
return positions[player]
}
}
package interview.snakes
class SnakeAndLadder(private val players: Int, private val lastSquare: Int, jumps: Map<Int, Int>) {
private val jumps = jumps.toMap()
private val positions: IntArray
var turn = 0
private set
var winner: Int? = null
private set
init {
require(players >= 2 && lastSquare > 1)
require(jumps.all { (from, to) -> from in 1 until lastSquare && to in 1..lastSquare && from != to })
positions = IntArray(players)
}
fun position(player: Int) = positions[player]
fun move(player: Int, roll: Int): Int {
check(winner == null && player == turn) { "Not this player's turn" }
require(roll in 1..6)
val destination = positions[player] + roll
if (destination <= lastSquare) {
positions[player] = jumps[destination] ?: destination
}
if (positions[player] == lastSquare) winner = player
else turn = (turn + 1) % players
return positions[player]
}
}
Follow-up questions
Extra turn on six?
“I would change only the turn advancement rule.” After applying the move and checking for a win, keep the same player when the roll is six. Agree on whether an overshoot still earns another turn. This fragment chooses yes, and replaces the final win and turn check in move.
Kotlin
if (positions[player] == lastSquare) winner = player
else if (roll != 6) turn = (turn + 1) % playersJava
if (positions[player] == lastSquare) winner = player;
else if (roll != 6) turn = (turn + 1) % positions.length;Chained jumps?
“I would keep following jumps until the player reaches a square without one.” For a ladder from 3 to 8 followed by one from 8 to 14, landing on 3 would finish at 14. Validate the board when creating it by following each chain and recording visited squares. Reaching a square already visited means a cycle, so reject that board instead of allowing an infinite move.
A real die?
“I would roll outside the game and pass the result into move.” The game only validates that the number is between 1 and 6. This lets the UI use randomness while tests use fixed rolls that reliably land on a snake, ladder or final square.
What should I test?
“Landing on a snake or ladder should move the player to its destination.” Overshooting the last square should leave the position unchanged, and landing exactly on it should declare a winner. A wrong player's move and every move after a win should fail. For the extra-turn extension, check both an ordinary six and an overshooting six.
Extended implementation and optional features
This reference explores a larger scope. Use it after you can explain and write the interview version. Its extra types and features are not required for the scope above.
Java
com.androidinterview.snakeandladder.game.Game.java
package com.androidinterview.snakeandladder.game;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.function.Consumer;
import com.androidinterview.snakeandladder.model.Board;
import com.androidinterview.snakeandladder.model.Dice;
import com.androidinterview.snakeandladder.model.Player;
// The whole game. A queue for turn order, one roll, one move, one win check.
// There is no snake handling and no ladder handling in here, because the board
// already resolved both into a destination.
public final class Game {
private final Board board;
private final Dice dice;
private final Deque<Player> turnOrder = new ArrayDeque<>();
private final Consumer<String> log;
private Player winner;
public Game(Board board, Dice dice, List<Player> players) {
this(board, dice, players, System.out::println);
}
// The commentary goes to a listener rather than straight to stdout, so the
// same game runs behind a socket, in a test or in a UI without anyone
// capturing a stream.
public Game(Board board, Dice dice, List<Player> players, Consumer<String> log) {
this.board = board;
this.dice = dice;
this.log = log;
this.turnOrder.addAll(players);
}
public boolean isOver() {
return winner != null;
}
public Player winner() {
return winner;
}
public void play() {
while (!isOver()) {
playTurn();
}
log.accept(winner.name() + " wins the game");
}
// One player's whole turn. A six earns another roll, and three sixes in a
// row cancels the turn, which is why the starting cell is kept.
public void playTurn() {
Player player = turnOrder.poll();
int startedAt = player.position();
int sixes = 0;
boolean rollAgain = true;
while (rollAgain) {
int roll = dice.roll();
sixes = roll == 6 ? sixes + 1 : 0;
if (sixes == 3) {
player.moveTo(startedAt);
break;
}
move(player, roll);
if (player.position() == board.size()) {
winner = player;
// The winner is not pushed back on the queue. Keeping the rest
// going until one player is left is what turns this into a
// ranking, and it costs this one return.
return;
}
rollAgain = roll == 6;
}
turnOrder.add(player);
}
private void move(Player player, int roll) {
int from = player.position();
int target = from + roll;
// The exact finish rule, and the requirement most people miss. A roll
// that would overshoot the last cell does not move the player at all.
int to = target > board.size() ? from : board.destinationFrom(target);
player.moveTo(to);
log.accept(player.name() + " rolled a " + roll + " and moved from " + from + " to " + to);
}
}
package com.androidinterview.snakeandladder.game;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import java.util.function.Consumer;
import com.androidinterview.snakeandladder.model.Board;
import com.androidinterview.snakeandladder.model.Dice;
import com.androidinterview.snakeandladder.model.Player;
public final class Game {
private final Board board;
private final Dice dice;
private final Deque<Player> turnOrder = new ArrayDeque<>();
private final Consumer<String> log;
private Player winner;
public Game(Board board, Dice dice, List<Player> players) {
this(board, dice, players, System.out::println);
}
public Game(Board board, Dice dice, List<Player> players, Consumer<String> log) {
this.board = board;
this.dice = dice;
this.log = log;
this.turnOrder.addAll(players);
}
public boolean isOver() {
return winner != null;
}
public Player winner() {
return winner;
}
public void play() {
while (!isOver()) {
playTurn();
}
log.accept(winner.name() + " wins the game");
}
public void playTurn() {
Player player = turnOrder.poll();
int startedAt = player.position();
int sixes = 0;
boolean rollAgain = true;
while (rollAgain) {
int roll = dice.roll();
sixes = roll == 6 ? sixes + 1 : 0;
if (sixes == 3) {
player.moveTo(startedAt);
break;
}
move(player, roll);
if (player.position() == board.size()) {
winner = player;
return;
}
rollAgain = roll == 6;
}
turnOrder.add(player);
}
private void move(Player player, int roll) {
int from = player.position();
int target = from + roll;
int to = target > board.size() ? from : board.destinationFrom(target);
player.moveTo(to);
log.accept(player.name() + " rolled a " + roll + " and moved from " + from + " to " + to);
}
}
com.androidinterview.snakeandladder.model.Board.java
package com.androidinterview.snakeandladder.model;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
// Cell to destination, one map. A list of snakes and a list of ladders would
// mean scanning both on every move, so the entities are flattened into a
// lookup once at construction and never scanned again.
public final class Board {
private final int size;
private final Map<Integer, Integer> jumps = new HashMap<>();
public Board(int size, List<BoardEntity> entities) {
this.size = size;
for (BoardEntity entity : entities) {
requireOnBoard(entity.start());
requireOnBoard(entity.end());
if (entity.start() == size) {
throw new IllegalArgumentException("Nothing may start on the last cell, " + entity.start());
}
if (jumps.put(entity.start(), entity.end()) != null) {
throw new IllegalArgumentException("Two entities start at cell " + entity.start());
}
}
}
// The board is the only object that knows how big it is, so the range check
// belongs here rather than on the entity. A ladder to 105 leaves a player on
// a cell that never equals the last one, so they can never win, and a snake
// head on the last cell makes the game unwinnable for everybody.
private void requireOnBoard(int cell) {
if (cell < 1 || cell > size) {
throw new IllegalArgumentException("Cell " + cell + " is off a board of " + size + " cells");
}
}
public int size() {
return size;
}
// Jumps chain, because a ladder can land you on a snake head. Follow them
// until the cell is quiet. The hop cap turns a badly built board into an
// error instead of a program that never returns.
public int destinationFrom(int cell) {
int current = cell;
for (int hop = 0; jumps.containsKey(current) && hop <= jumps.size(); hop++) {
current = jumps.get(current);
}
if (jumps.containsKey(current)) {
throw new IllegalStateException("Jumps loop forever starting at " + cell);
}
return current;
}
}
package com.androidinterview.snakeandladder.model;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public final class Board {
private final int size;
private final Map<Integer, Integer> jumps = new HashMap<>();
public Board(int size, List<BoardEntity> entities) {
this.size = size;
for (BoardEntity entity : entities) {
requireOnBoard(entity.start());
requireOnBoard(entity.end());
if (entity.start() == size) {
throw new IllegalArgumentException("Nothing may start on the last cell, " + entity.start());
}
if (jumps.put(entity.start(), entity.end()) != null) {
throw new IllegalArgumentException("Two entities start at cell " + entity.start());
}
}
}
private void requireOnBoard(int cell) {
if (cell < 1 || cell > size) {
throw new IllegalArgumentException("Cell " + cell + " is off a board of " + size + " cells");
}
}
public int size() {
return size;
}
public int destinationFrom(int cell) {
int current = cell;
for (int hop = 0; jumps.containsKey(current) && hop <= jumps.size(); hop++) {
current = jumps.get(current);
}
if (jumps.containsKey(current)) {
throw new IllegalStateException("Jumps loop forever starting at " + cell);
}
return current;
}
}
com.androidinterview.snakeandladder.model.BoardEntity.java
package com.androidinterview.snakeandladder.model;
// One type for both. A snake goes down and a ladder goes up, and that is the
// entire difference between them. Two classes would carry no extra behaviour,
// and they would push a snake branch and a ladder branch into the turn loop
// forever. With one type the loop only ever asks where a cell leads.
public record BoardEntity(int start, int end) {
public static BoardEntity snake(int head, int tail) {
if (tail >= head) {
throw new IllegalArgumentException("A snake has to go down, " + head + " to " + tail);
}
return new BoardEntity(head, tail);
}
public static BoardEntity ladder(int bottom, int top) {
if (top <= bottom) {
throw new IllegalArgumentException("A ladder has to go up, " + bottom + " to " + top);
}
return new BoardEntity(bottom, top);
}
}
package com.androidinterview.snakeandladder.model;
public record BoardEntity(int start, int end) {
public static BoardEntity snake(int head, int tail) {
if (tail >= head) {
throw new IllegalArgumentException("A snake has to go down, " + head + " to " + tail);
}
return new BoardEntity(head, tail);
}
public static BoardEntity ladder(int bottom, int top) {
if (top <= bottom) {
throw new IllegalArgumentException("A ladder has to go up, " + bottom + " to " + top);
}
return new BoardEntity(bottom, top);
}
}
com.androidinterview.snakeandladder.model.Dice.java
package com.androidinterview.snakeandladder.model;
import java.util.Random;
// The number of dice is a field, which is the whole reason the two dice
// variant is a one line change rather than a rewrite.
public final class Dice {
private final int count;
private final Random random;
public Dice(int count, Random random) {
this.count = count;
this.random = random;
}
public int roll() {
int total = 0;
for (int die = 0; die < count; die++) {
total += random.nextInt(6) + 1;
}
return total;
}
}
package com.androidinterview.snakeandladder.model;
import java.util.Random;
public final class Dice {
private final int count;
private final Random random;
public Dice(int count, Random random) {
this.count = count;
this.random = random;
}
public int roll() {
int total = 0;
for (int die = 0; die < count; die++) {
total += random.nextInt(6) + 1;
}
return total;
}
}
com.androidinterview.snakeandladder.model.Player.java
package com.androidinterview.snakeandladder.model;
// A name and a cell. Everything else about a turn belongs to the game, because
// a player that knows the rules is a player you edit when the rules change.
public final class Player {
private final String name;
private int position;
public Player(String name) {
this.name = name;
}
public String name() {
return name;
}
public int position() {
return position;
}
public void moveTo(int position) {
this.position = position;
}
}
package com.androidinterview.snakeandladder.model;
public final class Player {
private final String name;
private int position;
public Player(String name) {
this.name = name;
}
public String name() {
return name;
}
public int position() {
return position;
}
public void moveTo(int position) {
this.position = position;
}
}
Kotlin
com.androidinterview.snakeandladder.game.Game.kt
package com.androidinterview.snakeandladder.game
import com.androidinterview.snakeandladder.model.Board
import com.androidinterview.snakeandladder.model.Dice
import com.androidinterview.snakeandladder.model.Player
// The whole game. A deque for turn order, one roll, one move, one win check.
// There is no snake handling and no ladder handling here, because the board
// already resolved both into a destination.
//
// The commentary goes to a listener that defaults to println, so the same game
// runs behind a socket, in a test or in a UI without anyone capturing stdout.
class Game(
private val board: Board,
private val dice: Dice,
players: List<Player>,
private val log: (String) -> Unit = ::println,
) {
private val turnOrder = ArrayDeque(players)
var winner: Player? = null
private set
val isOver: Boolean get() = winner != null
fun play() {
while (!isOver) playTurn()
log("${winner?.name} wins the game")
}
// One player's whole turn. A six earns another roll, and three sixes in a
// row cancels the turn, which is why the starting cell is kept. The do
// while condition can read the roll declared inside the body, so there is
// no flag variable.
fun playTurn() {
val player = turnOrder.removeFirst()
val startedAt = player.position
var sixes = 0
do {
val roll = dice()
sixes = if (roll == 6) sixes + 1 else 0
if (sixes == 3) {
player.moveTo(startedAt)
break
}
move(player, roll)
if (player.position == board.size) {
winner = player
// The winner is not pushed back on the queue. Keeping the rest
// going until one player is left is what turns this into a
// ranking, and it costs this one return.
return
}
} while (roll == 6)
turnOrder.addLast(player)
}
private fun move(player: Player, roll: Int) {
val from = player.position
val target = from + roll
// The exact finish rule, and the requirement most people miss. A roll
// that would overshoot the last cell does not move the player at all.
val to = if (target > board.size) from else board.destinationFrom(target)
player.moveTo(to)
log("${player.name} rolled a $roll and moved from $from to $to")
}
}
package com.androidinterview.snakeandladder.game
import com.androidinterview.snakeandladder.model.Board
import com.androidinterview.snakeandladder.model.Dice
import com.androidinterview.snakeandladder.model.Player
class Game(
private val board: Board,
private val dice: Dice,
players: List<Player>,
private val log: (String) -> Unit = ::println,
) {
private val turnOrder = ArrayDeque(players)
var winner: Player? = null
private set
val isOver: Boolean get() = winner != null
fun play() {
while (!isOver) playTurn()
log("${winner?.name} wins the game")
}
fun playTurn() {
val player = turnOrder.removeFirst()
val startedAt = player.position
var sixes = 0
do {
val roll = dice()
sixes = if (roll == 6) sixes + 1 else 0
if (sixes == 3) {
player.moveTo(startedAt)
break
}
move(player, roll)
if (player.position == board.size) {
winner = player
return
}
} while (roll == 6)
turnOrder.addLast(player)
}
private fun move(player: Player, roll: Int) {
val from = player.position
val target = from + roll
val to = if (target > board.size) from else board.destinationFrom(target)
player.moveTo(to)
log("${player.name} rolled a $roll and moved from $from to $to")
}
}
com.androidinterview.snakeandladder.model.Board.kt
package com.androidinterview.snakeandladder.model
// Cell to destination, one map. Two lists would mean scanning both on every
// move, so the entities are flattened into a lookup once and never scanned.
class Board(val size: Int, entities: List<BoardEntity>) {
private val jumps = entities.associate { it.start to it.end }
init {
require(jumps.size == entities.size) { "Two entities start on the same cell" }
// The board is the only object that knows how big it is, so the range
// check belongs here rather than on the entity. A ladder to 105 leaves
// a player on a cell that never equals the last one, so they can never
// win, and a snake head on the last cell makes the game unwinnable for
// everybody.
jumps.forEach { (start, end) ->
require(start in 1..size && end in 1..size) {
"$start to $end is off a board of $size cells"
}
require(start != size) { "Nothing may start on the last cell, $start" }
}
}
// Jumps chain, because a ladder can drop you on a snake head. Follow them
// until the cell is quiet. The hop count turns a badly built board into an
// error rather than a program that never returns.
tailrec fun destinationFrom(cell: Int, hops: Int = 0): Int {
check(hops <= jumps.size) { "Jumps loop forever starting at $cell" }
val next = jumps[cell] ?: return cell
return destinationFrom(next, hops + 1)
}
}
package com.androidinterview.snakeandladder.model
class Board(val size: Int, entities: List<BoardEntity>) {
private val jumps = entities.associate { it.start to it.end }
init {
require(jumps.size == entities.size) { "Two entities start on the same cell" }
jumps.forEach { (start, end) ->
require(start in 1..size && end in 1..size) {
"$start to $end is off a board of $size cells"
}
require(start != size) { "Nothing may start on the last cell, $start" }
}
}
tailrec fun destinationFrom(cell: Int, hops: Int = 0): Int {
check(hops <= jumps.size) { "Jumps loop forever starting at $cell" }
val next = jumps[cell] ?: return cell
return destinationFrom(next, hops + 1)
}
}
com.androidinterview.snakeandladder.model.BoardEntity.kt
package com.androidinterview.snakeandladder.model
// One type for both. A snake goes down and a ladder goes up, and that is the
// entire difference. Two classes would carry no extra behaviour and would push
// a snake branch and a ladder branch into the turn loop forever.
data class BoardEntity(val start: Int, val end: Int)
fun snake(head: Int, tail: Int): BoardEntity {
require(tail < head) { "A snake has to go down, $head to $tail" }
return BoardEntity(head, tail)
}
fun ladder(bottom: Int, top: Int): BoardEntity {
require(top > bottom) { "A ladder has to go up, $bottom to $top" }
return BoardEntity(bottom, top)
}
package com.androidinterview.snakeandladder.model
data class BoardEntity(val start: Int, val end: Int)
fun snake(head: Int, tail: Int): BoardEntity {
require(tail < head) { "A snake has to go down, $head to $tail" }
return BoardEntity(head, tail)
}
fun ladder(bottom: Int, top: Int): BoardEntity {
require(top > bottom) { "A ladder has to go up, $bottom to $top" }
return BoardEntity(bottom, top)
}
com.androidinterview.snakeandladder.model.Dice.kt
package com.androidinterview.snakeandladder.model
import kotlin.random.Random
// A die is only something that produces a number, so it is a function type.
// The count is captured in the lambda, which is what makes the two dice
// variant one line instead of a new class.
typealias Dice = () -> Int
fun dice(count: Int = 1, random: Random = Random.Default): Dice =
{ (1..count).sumOf { random.nextInt(1, 7) } }
package com.androidinterview.snakeandladder.model
import kotlin.random.Random
typealias Dice = () -> Int
fun dice(count: Int = 1, random: Random = Random.Default): Dice =
{ (1..count).sumOf { random.nextInt(1, 7) } }
com.androidinterview.snakeandladder.model.Player.kt
package com.androidinterview.snakeandladder.model
// A name and a cell. Everything else about a turn belongs to the game, because
// a player that knows the rules is a player you edit when the rules change.
//
// The cell moves through moveTo and nowhere else, so nothing outside the game
// can teleport a player.
class Player(val name: String) {
var position: Int = 0
private set
fun moveTo(cell: Int) {
position = cell
}
}
package com.androidinterview.snakeandladder.model
class Player(val name: String) {
var position: Int = 0
private set
fun moveTo(cell: Int) {
position = cell
}
}
Watch