Cracking The Coding Interview Together – Problem 7.8: Othello

When interviewers ask you to design a board game like Othello (also known as Reversi), they aren't merely testing if you know how to iterate through a 2D array. They want to see how you model complex real-world rules, separate concerns, handle cascading state transitions, and build extensible domain abstractions. Othello seems deceivingly simple on the surface: an 8x8 grid, two colors, and a flipping rule. However, handling directional raycasting for flips, turn-skipping logic, edge-case score validation, and cleanly decoupling game orchestration from state representation can quickly turn into a messy web of spaghetti code if approached without a plan.

In this post, we are going to walk through the complete Object-Oriented Design (OOD) of Othello step-by-step. By the end of this guide, you will have a deep, practical understanding of how to architect clean, production-ready data structures for Othello that any interviewer would praise.

Problem Statement

Design the data structures and class relationships for playing a game of Othello. Your design must satisfy the following core requirements:

• Represent an 8x8 grid board holding Black and White game pieces.
• Enforce standard Othello setup: board starts with four center pieces placed diagonally (2 Black, 2 White).
• Validate candidate moves: a move is legal if placing a piece traps one or more opponent pieces in a continuous straight line (horizontally, vertically, or diagonally) between the new piece and an existing piece of the player's color.
• Execute flips: placing a piece automatically flips all trapped opponent pieces to the current player's color across all valid directions.
• Manage turn flow: toggle turns between Black and White, automatically pass turn if a player has no valid moves, and terminate the game when neither player can move or the board is full.
• Track game state and score cleanly at all times.

Analyze the Problem Together

Let's dissect the operational constraints and core challenges before touching any code. In Othello, state mutation occurs in multiple directions simultaneously from a single point of interaction. When a player places a piece at coordinate (r, c), we must project rays out in all 8 compass directions (North, South, East, West, NW, NE, SW, SE) to find lines of contiguous enemy pieces flanked by a piece of the current player's color.

A naive approach often bundles all logic inside a massive GameManager class containing nested for loops, array mutations, and direct console printing mixed together. This creates fragile code where modifying board logic requires changing game control code. Instead, we want to establish clear boundaries:

The key "Aha!" insight is using directional coordinate offsets to handle board traversal dryly and dynamically. By defining direction vectors as (dr, dc) pairs, a single helper function can validate or flip pieces across all 8 directions effortlessly.

Questions for the Interviewer

In a real technical interview, asking clarifying questions demonstrates seniority and attention to requirements. Here are four essential questions you should ask:

1. Board Flexibility: Is the board strictly fixed at 8x8, or should our data structures support custom dimensions (e.g., 6x6 or 10x10) for variant games?
2. Player Types: Do we need to support automated AI players, or are we designing exclusively for local human-versus-human interaction?
3. Game State Persistence: Do we need to support undo/redo capabilities, move logging, or board state serialization for network play?
4. Turn Forfeiture: Should the system automatically detect when a player has no legal moves and pass the turn, or rely on manual player input?

Think About the Solution

Let's map out our object model and system architecture cleanly:

• PieceColor: Enum representing BLACK and WHITE, with a utility method to return the opposite color.
• Position: An immutable record encapsulating row and column coordinates (row, col).
• Direction: A record or offset pair (dRow, dCol) defining the 8 spatial search vectors.
• Board: Encapsulates the grid matrix, initial setup, score tracking, move validation, and piece flipping.
• Player: Abstract base class or concrete model containing player identity, color, and move selection capability.
• GameManager: Orchestrates turn cycles, validates move availability, handles turn passing, tracks game completion, and determines the winner.

Write Code and Explain

Here is our complete, production-ready implementation in Java. We leverage modern Java features like records and clean enum design for clarity and encapsulation.

package com.thedevlearnings.othello;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;

public class OthelloSystem {

    public enum PieceColor {
        BLACK, WHITE;

        public PieceColor opposite() {
            return this == BLACK ? WHITE : BLACK;
        }
    }

    public record Position(int row, int col) {}

    public record Direction(int dRow, int dCol) {
        public static final List<Direction> ALL = List.of(
            new Direction(-1, 0),  // North
            new Direction(1, 0),   // South
            new Direction(0, 1),   // East
            new Direction(0, -1),  // West
            new Direction(-1, 1),  // North-East
            new Direction(-1, -1), // North-West
            new Direction(1, 1),   // South-East
            new Direction(1, -1)   // South-West
        );
    }

    public static class Board {
        private final int size;
        private final PieceColor[][] grid;
        private int blackCount;
        private int whiteCount;

        public Board(int size) {
            if (size % 2 != 0 || size < 4) {
                throw new IllegalArgumentException("Board size must be an even integer >= 4.");
            }
            this.size = size;
            this.grid = new PieceColor[size][size];
            initializeBoard();
        }

        private void initializeBoard() {
            int mid = size / 2;
            grid[mid - 1][mid - 1] = PieceColor.WHITE;
            grid[mid][mid] = PieceColor.WHITE;
            grid[mid - 1][mid] = PieceColor.BLACK;
            grid[mid][mid - 1] = PieceColor.BLACK;
            this.blackCount = 2;
            this.whiteCount = 2;
        }

        public int getSize() {
            return size;
        }

        public PieceColor getPiece(Position pos) {
            return grid[pos.row()][pos.col()];
        }

        public boolean isWithinBounds(int row, int col) {
            return row >= 0 && row < size && col >= 0 && col < size;
        }

        public boolean isValidMove(Position pos, PieceColor color) {
            if (!isWithinBounds(pos.row(), pos.col()) || grid[pos.row()][pos.col()] != null) {
                return false;
            }
            for (Direction dir : Direction.ALL) {
                if (countFlipsInDirection(pos, color, dir) > 0) {
                    return true;
                }
            }
            return false;
        }

        public List<Position> getValidMoves(PieceColor color) {
            List<Position> validMoves = new ArrayList<>();
            for (int r = 0; r < size; r++) {
                for (int c = 0; c < size; c++) {
                    Position pos = new Position(r, c);
                    if (isValidMove(pos, color)) {
                        validMoves.add(pos);
                    }
                }
            }
            return validMoves;
        }

        public boolean placePiece(Position pos, PieceColor color) {
            if (!isValidMove(pos, color)) {
                return false;
            }

            grid[pos.row()][pos.col()] = color;
            int totalFlipped = 0;

            for (Direction dir : Direction.ALL) {
                totalFlipped += flipInDirection(pos, color, dir);
            }

            if (color == PieceColor.BLACK) {
                blackCount += 1 + totalFlipped;
                whiteCount -= totalFlipped;
            } else {
                whiteCount += 1 + totalFlipped;
                blackCount -= totalFlipped;
            }

            return true;
        }

        private int countFlipsInDirection(Position start, PieceColor color, Direction dir) {
            int r = start.row() + dir.dRow();
            int c = start.col() + dir.dCol();
            int count = 0;
            PieceColor opponent = color.opposite();

            while (isWithinBounds(r, c) && grid[r][c] == opponent) {
                r += dir.dRow();
                c += dir.dCol();
                count++;
            }

            if (count > 0 && isWithinBounds(r, c) && grid[r][c] == color) {
                return count;
            }
            return 0;
        }

        private int flipInDirection(Position start, PieceColor color, Direction dir) {
            int flips = countFlipsInDirection(start, color, dir);
            for (int i = 1; i <= flips; i++) {
                int r = start.row() + (dir.dRow() * i);
                int c = start.col() + (dir.dCol() * i);
                grid[r][c] = color;
            }
            return flips;
        }

        public int getScore(PieceColor color) {
            return color == PieceColor.BLACK ? blackCount : whiteCount;
        }
    }

    public static class Player {
        private final String name;
        private final PieceColor color;

        public Player(String name, PieceColor color) {
            this.name = Objects.requireNonNull(name);
            this.color = Objects.requireNonNull(color);
        }

        public String getName() { return name; }
        public PieceColor getColor() { return color; }
    }

    public static class GameManager {
        private final Board board;
        private final Player player1;
        private final Player player2;
        private Player currentPlayer;
        private boolean isGameOver;

        public GameManager(Player p1, Player p2) {
            this.board = new Board(8);
            this.player1 = p1;
            this.player2 = p2;
            this.currentPlayer = p1.getColor() == PieceColor.BLACK ? p1 : p2;
            this.isGameOver = false;
        }

        public Board getBoard() { return board; }
        public Player getCurrentPlayer() { return currentPlayer; }
        public boolean isGameOver() { return isGameOver; }

        public boolean makeMove(Position pos) {
            if (isGameOver) return false;

            if (!board.placePiece(pos, currentPlayer.getColor())) {
                return false; // Invalid move
            }

            advanceTurn();
            return true;
        }

        private void advanceTurn() {
            Player opponent = (currentPlayer == player1) ? player2 : player1;

            if (!board.getValidMoves(opponent.getColor()).isEmpty()) {
                currentPlayer = opponent;
            } else if (board.getValidMoves(currentPlayer.getColor()).isEmpty()) {
                // Neither player has valid moves
                isGameOver = true;
            } else {
                // Opponent skipped, turn stays with current player
                System.out.println("Opponent has no valid moves. Turn passes back to " + currentPlayer.getName());
            }
        }

        public Player getWinner() {
            if (!isGameOver) return null;
            int p1Score = board.getScore(player1.getColor());
            int p2Score = board.getScore(player2.getColor());
            if (p1Score > p2Score) return player1;
            if (p2Score > p1Score) return player2;
            return null; // Draw
        }
    }
}

Step-by-Step Code Walkthrough

• PieceColor & Direction: Enums and Records keep spatial offsets immutable and easy to traverse. Notice how Direction.ALL contains all 8 vector directions.
• countFlipsInDirection: This helper method steps along a ray starting from the targeted coordinate. It verifies that we cross 1 or more contiguous enemy pieces and land on a piece of our own color before declaring valid flips.
• Incremental Score Counter: Instead of re-scanning the entire $N \times N$ grid after every single move to count scores, the Board tracks blackCount and whiteCount continuously as pieces are placed and flipped.
• advanceTurn: Implements the true Othello pass-rule state machine. It checks if the opponent can move; if not, it checks if the current player can move. If neither can move, the game naturally transitions to `isGameOver = true`.

Time & Space Complexity

Let's analyze the algorithmic performance of key operations on an $N \times N$ board (where $N = 8$ for standard Othello):

• Move Validation (isValidMove): We check up to 8 directions. In each direction, we travel at most $N$ cells. Therefore, checking a single position takes $O(N)$ time. For an 8x8 board, $N = 8$, making this effectively $O(1)$ constant time.
• Generating All Legal Moves (getValidMoves): We check all $N^2$ positions on the board. For each cell, we test validation taking $O(N)$ time. Total complexity is $O(N^3)$. For $N = 8$, $8^3 = 512$ operations, which executes instantaneously.
• Placing a Piece & Flipping (placePiece): Traverses at most $N$ cells in 8 directions. Time complexity is $O(N)$. Score update is $O(1)$.
• Space Complexity: The grid stores an $N \times N$ array of references, taking $O(N^2)$ space memory.

Why This Problem Matters (The Senior Perspective)

From an enterprise engineering standpoint, Othello is a masterclass in clean architecture and domain-driven design:

• Model-View-Controller (MVC) Alignment: Notice how our Board acts strictly as the Domain Model, exposing stateless domain logic (validation, piece flipping). The GameManager acts as the Controller orchestrating rules. The rendering layer (CLI, UI, or REST API) can sit cleanly on top without corrupting core logic.
• Concurrency & Thread Safety: In multi-player network games, multiple clients might submit move requests concurrently. Encapsulating state mutations within `GameManager` allows easy synchronization using mutexes, synchronized blocks, or actor models (e.g., Akka/Java Virtual Threads).
• AI Integration & State Copying: If we want to build a Minimax or Alpha-Beta pruning AI bot, the AI must evaluate hundreds of prospective future moves. Our design allows us to easily add a `clone()` or `copy()` method to `Board`, enabling high-speed tree search without mutating the live game state.

Final Thoughts

Designing Othello is a fantastic interview problem because it tests whether you can break down complex conditional rules into elegant, extensible domain components. By avoiding monolithic methods and decoupling directional logic with vector offsets, we built a robust architecture that handles turn passes, score tracking, and victory conditions effortlessly.

Want to take this further? Try adding a deep-copy constructor to the Board class and implementing a basic Minimax AI player! Happy coding, and keep building solid systems!