File: root - text - article - 2020 - 02 - design-tic-tac-toe.txt
Tags: 每日算法题, 算法, 数据结构, 面试题, Daily Interview Problem, Data Structures and Algorithms, Computer Programming, Python, | English | Home Page | Category: Computing | 666 Views, 22073 Search Bots | 261 Words
| Browse | Archive
Tags: 每日算法题, 算法, 数据结构, 面试题, Daily Interview Problem, Data Structures and Algorithms, Computer Programming, Python, | English | Home Page | Category: Computing | 666 Views, 22073 Search Bots | 261 Words
| Browse | Archive
Hi, here's your problem today. This problem was recently asked by Google:
Design a Tic-Tac-Toe game played between two players on an n x n grid. A move is guaranteed to be valid, and a valid move is one placed on an empty block in the grid. A player who succeeds in placing n of their marks in a horizontal, diagonal, or vertical row wins the game. Once a winning condition is reached, the game ends and no more moves are allowed. Below is an example game which ends in a winning condition:
Given n = 3, assume that player 1 is "X" and player 2 is "O"
board = TicTacToe(3);
board.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | | // Player 1 makes a move at (0, 0).
| | | |
board.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 2 makes a move at (0, 2).
| | | |
board.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 1 makes a move at (2, 2).
| | |X|
board.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 2 makes a move at (1, 1).
| | |X|
board.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 1 makes a move at (2, 0).
|X| |X|
board.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| | // Player 2 makes a move at (1, 0).
|X| |X|
board.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| | // Player 1 makes a move at (2, 1).
|X|X|X|
Here's a starting point:
Tags: 每日算法题, 算法, 数据结构, 面试题, Daily Interview Problem, Data Structures and Algorithms, Computer Programming, Python, | English | Home Page | Cateogry: Computing | 666 Views, 22073 Search Bots | 261 Words Design a Tic-Tac-Toe game played between two players on an n x n grid. A move is guaranteed to be valid, and a valid move is one placed on an empty block in the grid. A player who succeeds in placing n of their marks in a horizontal, diagonal, or vertical row wins the game. Once a winning condition is reached, the game ends and no more moves are allowed. Below is an example game which ends in a winning condition:
Given n = 3, assume that player 1 is "X" and player 2 is "O"
board = TicTacToe(3);
board.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | | // Player 1 makes a move at (0, 0).
| | | |
board.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 2 makes a move at (0, 2).
| | | |
board.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 1 makes a move at (2, 2).
| | |X|
board.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 2 makes a move at (1, 1).
| | |X|
board.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 1 makes a move at (2, 0).
|X| |X|
board.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| | // Player 2 makes a move at (1, 0).
|X| |X|
board.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| | // Player 1 makes a move at (2, 1).
|X|X|X|
Here's a starting point:
class TicTacToe(object):
def __init__(self, n):
# Fill this in.
def move(self, row, col, player):
# Fill this in.
board = TicTacToe(3)
board.move(0, 0, 1)
board.move(0, 2, 2)
board.move(2, 2, 1)
board.move(1, 1, 2)
board.move(2, 0, 1)
board.move(1, 0, 2)
print(board.move(2, 1, 1))
Related Articles
- Daily Interview Puzzle: Falling Dominoes
- Algorithm Interview: Make the Largest Number
- Number of Ways to Climb Stairs
- Daily Interview Problem: Largest BST in a Binary Tree
- Daily Interview Problem: Largest Product of 3 Elements I
- Algorithm Interview: Smallest Number that is not a Sum of a Subset of List
- Palindrome Integers
- Consecutive Ones
- Daily Interview Problem:Create a balanced binary search tree
- Daily Interview Puzzle: Intersection of Linked Lists
©2006~2024 SteakOverCooked - 0.01265 Seconds(s) - 2003.146 KB/s - 33 Online Memory: 498.71 KB
18:54:01 up 13 days, 18:33, 2 users, load average: 0.98, 0.86, 0.73 - Server PHP Version: 7.4.33
How to Cook a Perfect Steak? | <meta name="robots" content="index, follow">
18:54:01 up 13 days, 18:33, 2 users, load average: 0.98, 0.86, 0.73 - Server PHP Version: 7.4.33
Comments (0)
Read & Write - Normal - Mini - Post - All Comments - Statistics
Be the first one to comment this page !