linkjobai / Design Tic-Tac-Toe in O(1) per Move (LeetCode 348)
0 喜欢
0 派生
1 文件
最后活跃于
Interview prep notes
Design Tic-Tac-Toe in O(1) per Move (LeetCode 348)
"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.
Naive approach
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.
O(1) idea: running sums
上一页
下一页