Java LLD: O (1) Move Resolution으로 뱀과 사다리 디자인하기

Java LLD: Designing Snakes and Ladders with O(1) Move Resolution

Designing Snakes and Ladders is a classic LLD (Low-Level Design) interview question that tests your ability to write clean, maintainable, and highly performant code. While the rules are simple, naive implementations quickly fall apart under scale, concurrency, or changing business requirements.

Want to go deeper? javalld.com — machine coding interview problems with working Java code and full execution traces.

The Mistake Most Candidates Make

• Expensive Runtime Scans: Iterating through lists of snakes and ladders on every single move, turning an $O(1)$ lookup into a slow $O(N)$ search.
• Violating SRP: Hardcoding board mechanics, game loops, and dice rolling logic inside a single monolithic class.
• Tight Coupling: Binding player movement directly to the dice, making it incredibly difficult to introduce custom game rules (e.g., crooked dice or extra turns).

The Right Approach

• Core mental model: Treat the board as a flat, pre-computed $O(1)$ lookup array where each index represents a cell and its value represents the final destination.
• Key entities/classes: Board, Jump (representing Snakes/Ladders), Player, Dice, Game, and MovementStrategy.
• Why it beats the naive approach: It decouples board setup from game loop execution, turning expensive runtime lookups into instantaneous array access.

The Key Insight (Code)

public class Board {
    private final int[] board; // Pre-computed jump destinations

    public Board(int size, List<Jump> jumps) {
        this.board = IntStream.range(0, size + 1).toArray();
        jumps.forEach(j -> board[j.start()] = j.end()); // Precompute O(1) lookups
    }

    public int resolvePosition(int current, int roll) {
        int next = current + roll;
        return next < board.length ? board[next] : current;
    }
}

Enter fullscreen mode Exit fullscreen mode

Key Takeaways

• DP-Style Precomputation: Pre-populating a lookup array transforms runtime search complexity from $O(N)$ to $O(1)$ time complexity per turn.
• Open-Closed Principle (OCP): Abstracting the movement logic via a MovementStrategy interface allows you to add features (like “crooked dice” or “extra turn on 6”) without modifying core classes.
• Data Structure Optimization: Avoid heavy object graphs for simple cell traversals; a primitive array is highly cache-friendly and performant.

Full working implementation with execution trace available at https://javalld.com/problems/snakes-ladders