Course4all

Design Tic-Tac-Toe

Expert Answer & Key Takeaways

# 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)O(1) read and O(N)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)O(1) caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - HashMap: Provides O(1)O(1) lookups for keys to their corresponding nodes. - DLL: Provides O(1)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)O(1), and "flipping" elements to another stack happens only when necessary, averaging O(1)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×nn \times n grid. You may assume the following rules:
  1. A move is guaranteed to be valid and is placed on an empty block.
  2. Once a winning condition is reached, no more moves will be allowed.
  3. A player who succeeds in placing nn of their marks in a horizontal, vertical, or diagonal row wins the game.

Goal

move(row, col, player) must run in O(1)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×nn \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)
StepMoveGrid StateResult
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(N2)O(N^2) to O(N)O(N).
⏱ O(N) per move.💾 O(N^2) to store the grid.

Detailed Dry Run

Input: n=3, move(1,1,1)
ScanElementsResult
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)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 nn, 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)
StepMoveRows CountCols CountDiagAnti-DiagResult
1(0,0,1)[1,0,0][1,0,0]100
2(1,1,1)[1,1,0][1,1,0]200
3(2,2,1)[1,1,1][1,1,1]301 (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));
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionLRU Cache
Next Question →Implement Stack using Queues