Все Новый

user:thomas фрагментов создано пользователем

title:mygist gists with given title

filename:myfile.txt gists having files with given name

extension:yml gists having files with given extension

language:go gists having files with given language

topic:homelab gists with given topic

Регистрация

Войти


Все Новый Регистрация Войти

All gists matching topic interview

Свежие сверху по дате создания
Свежие снизу по дате создания
Свежие сверху по дате обновления
Свежие снизу по дате обновления

linkjobai / Design Tic-Tac-Toe in O(1) per Move (LeetCode 348)

0 лайк(-ов)
0 форк(-ов)
1 файл(-ов)
Последняя активность 1794544815
Interview prep notes
interview

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

Новее Позже

Работает на Opengist ⋅ Load: 16ms⋅

Русский
Čeština Deutsch English Español Français Magyar Italiano 日本語 Polski Português Русский Türkçe Українська 中文 繁體中文