Learning on Web Dev Open is free for all.

Interview Prep · Low Level DesignDesign an N×N board game
← Low Level Design

Design an N×N board game

Easy30 minFree, no account

The naive win check is O(n²) per move. Making it O(1) is the question.

The question

Design tic-tac-toe generalised to an N×N board with K players, where a win is N in a row, column or diagonal.

Checking for a win after each move must be O(1), not a scan of the board.

Functional
  • Place a mark; reject illegal moves with a reason.
  • Detect a win or a draw immediately after the move that causes it.
  • Undo the last move.
  • Support more than two players.
Non-functional
  • Win detection in O(1) per move.
  • Memory proportional to N, not N².
30:00Commit to an answer before you open the solution. Reading it first teaches you to recognise good answers, which is not the skill being tested.

Stuck?

0 of 3 hints taken

The worked solution

written by a person · not a grade

Score yourself

0 of 5 marked
  • O(1) win detection from running line counts35
  • Generalised correctly to more than two players20
  • Stated the invariants and rejected illegal moves with reasons20
  • Undo restores the counters as well as the cell15
  • Said what changes for K-in-a-row10

We run no AI here and nothing on this page grades you. The score is yours, and the useful number is the one you get on the same problem a month from now, cold.

kept in this browser only