Last active 1794544815

Interview prep notes

linkjobai revised this gist 1794544815. Go to revision

1 file changed, 55 insertions

tictactoe.md(file created)

@@ -0,0 +1,55 @@
1 + # Design Tic-Tac-Toe in O(1) per Move (LeetCode 348)
2 +
3 + "Design Tic-Tac-Toe" looks trivial, but the follow-up, *"can you check for a winner faster than O(n²) per move?"*, is what the interviewer is really after.
4 +
5 + ## Naive approach
6 +
7 + After each move, scan the move's row, its column and both diagonals: O(n) per move. Fine for 3x3, but the interviewer will push for better on an n x n board.
8 +
9 + ## O(1) idea: running sums
10 +
11 + Give player 1 the value 1 and player 2 the value -1. Keep:
12 +
13 + - `rows[i]`: the sum of the values in row i
14 + - `cols[j]`: the sum of the values in column j
15 + - `diag` and `anti`: the sums of the two diagonals
16 +
17 + A player wins when any of these reaches ` n` or `-n`.
18 +
19 + ```python
20 + class TicTacToe:
21 + def __init__(self, n):
22 + self.n = n
23 + self.rows = [0] * n
24 + self.cols = [0] * n
25 + self.diag = self.anti = 0
26 +
27 + def move(self, r, c, player):
28 + v = 1 if player == 1 else -1
29 + self.rows[r] = v
30 + self.cols[c] = v
31 + if r == c:
32 + self.diag = v
33 + if r c == self.n - 1:
34 + self.anti = v
35 + n = self.n
36 + if n in (abs(self.rows[r]), abs(self.cols[c]),
37 + abs(self.diag), abs(self.anti)):
38 + return player
39 + return 0
40 + ```
41 +
42 + O(1) time per move and O(n) space, because we never store the board itself.
43 +
44 + ## Assumptions to state
45 +
46 + The problem guarantees valid moves (no overwriting a cell, no moves after a win). In a real game class you'd keep the board too, to validate moves and to render it.
47 +
48 + ## Extending the design (OOD follow-ups)
49 +
50 + - `Player`, `Board` and `Game` classes, with `Game` owning turn order and win state.
51 + - Connect-K on a bigger board: the running-sum trick no longer works directly, so count consecutive pieces from the last move in each of four directions (still O(k)).
52 + - Undo: store the move history and subtract values when undoing.
53 +
54 + ---
55 + *Disclosure: I'm part of the [Linkjob AI](https://www.linkjob.ai/) team (an AI interview assistant).*
Newer Older