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
Новее
Позже