Design Tic-Tac-Toe

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

Design Tic-Tac-Toe

Design a Tic-Tac-Toe game that is played on an $n \times n$ grid. You may assume the following rules:

A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves will be allowed.
A player who succeeds in placing $n$ of their marks in a horizontal, vertical, or diagonal row wins the game.

Goal

move(row, col, player) must run in $O(1)$ time complexity.

Medium

Examples

Input: n = 3, move(0, 0, 1), move(0, 2, 2), move(2, 2, 1), move(1, 1, 2), move(2, 0, 1), move(1, 0, 2), move(2, 1, 1)
Output: 1

Approach 1

Level I: Brute-Force Grid Scan

Intuition

Maintain the actual $n \times n$ grid. For every move, scan the entire row, column, and two diagonals to check if all elements belong to the current player.

⏱ O(N) per move.💾 O(N^2).

Detailed Dry Run

Input: n=3, move(0,0,1)

Step	Move	Grid State	Result
1	`(0,0,1)`	`[[1,0,0],...]`	0 (No win yet)

java

import java.util.*;

class TicTacToe {
    private int[][] grid; private int n;
    public TicTacToe(int n) { grid = new int[n][n]; this.n = n; }
    public int move(int r, int c, int p) {
        grid[r][c] = p;
        boolean win = true;
        for (int i=0; i<n; i++) if (grid[r][i] != p) win = false;
        if (win) return p;
        win = true; for (int i=0; i<n; i++) if (grid[i][c] != p) win = false;
        if (win) return p;
        if (r == c) {
            win = true; for (int i=0; i<n; i++) if (grid[i][i] != p) win = false;
            if (win) return p;
        }
        if (r + c == n - 1) {
            win = true; for (int i=0; i<n; i++) if (grid[i][n-1-i] != p) win = false;
            if (win) return p;
        }
        return 0;
    }
    public static void main(String[] args) {
        TicTacToe game = new TicTacToe(3);
        System.out.println(game.move(0, 0, 1)); // 0
    }
}

Approach 2

Level II: Optimized Grid Scan

Intuition

Instead of re-scanning everything, we only check the specific row, column, and diagonals that the current move affected. This reduces the work from $O(N^2)$ to $O(N)$ .

⏱ O(N) per move.💾 O(N^2) to store the grid.

Detailed Dry Run

Input: n=3, move(1,1,1)

Scan	Elements	Result
Row 1	`[0,1,0]`	No Win
Col 1	`[0,1,0]`	No Win
Diag 1	`[1,1,0]`	No Win
Diag 2	`[0,1,0]`	No Win

java

class TicTacToe {
    private int[][] grid; private int n;
    public TicTacToe(int n) { this.grid = new int[n][n]; this.n = n; }
    public int move(int r, int c, int p) {
        grid[r][c] = p;
        if (checkRow(r, p) || checkCol(c, p) || checkDiag(r, c, p) || checkAntiDiag(r, c, p)) return p;
        return 0;
    }
    private boolean checkRow(int r, int p) { for(int i=0; i<n; i++) if(grid[r][i] != p) return false; return true; }
    private boolean checkCol(int c, int p) { for(int i=0; i<n; i++) if(grid[i][c] != p) return false; return true; }
    private boolean checkDiag(int r, int c, int p) {
        if (r != c) return false;
        for(int i=0; i<n; i++) if(grid[i][i] != p) return false;
        return true;
    }
    private boolean checkAntiDiag(int r, int c, int p) {
        if (r + c != n - 1) return false;
        for(int i=0; i<n; i++) if(grid[i][n-1-i] != p) return false;
        return true;
    }
}

Approach 3

Level III: Counter Arrays (Optimal)

Intuition

To achieve $O(1)$ time, we stop storing the grid entirely. Instead, we maintain count arrays for rows and columns, and two variables for the diagonals. For player 1, we add 1; for player 2, we subtract 1. If any count's absolute value reaches $n$ , we have a winner.

⏱ O(1) per move.💾 O(N) to store row/col/diag counts.

Detailed Dry Run

Input: n=3, move(0,0,1)

Step	Move	Rows Count	Cols Count	Diag	Result
1	`(0,0,1)`	`[1,0,0]`	`[1,0,0]`	1	0
2	`(1,1,1)`	`[1,1,0]`	`[1,1,0]`	2	0
3	`(2,2,1)`	`[1,1,1]`	`[1,1,1]`	3	1 (Win!)

java

import java.util.*;

class TicTacToe {
    private int[] rows, cols; private int diag, antiDiag, n;
    public TicTacToe(int n) { this.n = n; rows = new int[n]; cols = new int[n]; }
    public int move(int r, int c, int p) {
        int val = (p == 1) ? 1 : -1;
        rows[r] += val; cols[c] += val;
        if (r == c) diag += val;
        if (r + c == n - 1) antiDiag += val;
        if (Math.abs(rows[r]) == n || Math.abs(cols[c]) == n || Math.abs(diag) == n || Math.abs(antiDiag) == n) return p;
        return 0;
    }
    public static void main(String[] args) {
        TicTacToe game = new TicTacToe(3);
        System.out.println(game.move(0,0,1));
    }
}

← Previous QuestionLRU Cache

Next Question →Implement Stack using Queues

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.