[Liru]

Board states, yes, but in a game of tic-tac-toe, placement order matters as well. There are a total of 9! (362880) possible (but not necessarily valid) game states. With such a low number, it's not hard to brute force the correct answer. Someone more well-versed in combinatorics could probably do it in a more efficient way.

[shhsshs]

I don’t think it is valid to consider two identical boards, arrived at via different sequences of moves, to be different “states”. They did take separate paths to get there, but their state trees have now converged and they are de-facto the same state.

And these are the kind of questions that would (hopefully) come up in the interview!

[jl2718]

Looking at it that way, you can subtract all game states that occur after a win.