LLD : N X N Tic Tac Toe with O(1) checks

🚀 *The Importance of Low-Level Design (LLD) in Interviews * 🚀

In today's tech interviews, mastering Low-Level Design (LLD) is crucial.

It demonstrates your ability to think through the detailed aspects of system design, ensuring robustness, scalability, and maintainability.

Let's explore how to design a software system for such interviews with an advanced N x N Tic Tac Toe game! 🎉

🔍 Overview:

This project brings a modern twist to the classic Tic Tac Toe game, allowing players to compete on a flexible N x N board.

The first player to align N marks in a row, column, or diagonal wins the game. If the board is filled without any player achieving this, the game ends in a tie.

📝 Game Rules:

1. Players:

• Player 1 ('Bob')

• Player 2 ('Alice')

1. GamePlay:

• Player 1 starts the game by placing a 'Bob' on the board.

• Player 2 follows by placing an 'Alice'.

• Players take turns to place their marks in an empty cell of the board.

• The game continues until a player wins or the board is full.

1. Winning Conditions:

• A player wins by placing N marks consecutively in a row, column, or diagonal.

• If all cells are filled and no player has N consecutive marks, the game is a tie.

💡 Classes:

1. Player:

• Represents a player in the game.

• Can be extended to include additional player attributes and methods.

1. Board:

• Manages the state of the game board.

• Contains the business logic to check for valid moves and determine the game status (win/tie).

1. Game:

• Orchestrates the game flow.

• Interacts with the Player and Board classes to manage turns and check for game completion.

⚙️ Algorithm Design:

• The time complexity for determining whether a player has won, tied, or has more moves left is constant time, O(1).

🎮 Ready to dive in? Check out the GitHub repository and start playing! 🕹️

GitHub Link : https://lnkd.in/gGShtCTF

Reference Video : https://lnkd.in/gr6D5uBG

LowLevelDesign #TicTacToe #Python #GameDevelopment #OOP #DesignPatterns #Coding #SoftwareEngineering #GitHub #Tech #Interviews

---

Comments

[Red Ochsenbein (he/him)]

O(1) seems a bit misleading. It's only O(1) if you ignore the fact that you have to track each played step along the way. It's only O(1) for the current turn, but linear time complexity (O(n) with n being the amount of turns played, which would increase with the size of the board) with respect to the whole game.

This makes me think about determining the current state of a board using bitmasks. Should allow O(1) for boards up to 8x8 and O(n/64) in general (well, still linear time - but on the faster side).