Microsoft Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: In-Person
First, in such a game, the first player will always win (if played correctly). Wondering if in reality such a game makes any sense.
Anyway, my thought is to use a Linked-Map (let's call it LM) and a Kd-tree (let's call it T).
The LM has key= position e.g. string representation of "i,j" and value could include at least the player-id. For a move, an entry would take O(1) to be added to the map. For each move, to test if the game is over we need to test at most 9 cases relative to current move at [i,j]. This test can be done in O(1) time as well.
The LM is made linked in the sense that we're maintaining ordering of the moves as well so that if needed we can keep undoing the moves.
The need for a Kd-tree is for a display reason. If I assume that two players keep on playing on this infinite board which will be dragged in all directions (similar to how we move a map in google-map) as and when the player wishes, then we need a function that given the boundary of the view port (rectangle window for example), the function must returns all points in that visible portion of the board. A kd-tree would come handy here I believe.
Since the service need to track only the player moves and subsequent state changes, the board size (infinity) does not matter. Another reason why the infinite expanse of the board does not matter is this: since the player who gets the 3 consecutive/contiguous blocks win, the other play will be forced to play in the same vicinity as the first player. he players can start anywhere on the board, as long as the service maintains a log of moves and the state changes.
- whitenoise April 26, 2013For a player to win, she must play at least 4 moves for a 3 in a row state. Sometimes, she will need 5 moves or perhaps higher in this case. So evidently, we will need to track the blocks marked by the players in each move. I am thinking of using a stack for each player. Popping the stack every 4th move for each player, check each moves, meaning the cells for their adjacency. This is O(1) time efficient.
The adjacency is proved by:
1. If rows match across the moves (row match)
2. If cols match across the moves (column match)
3. If rows and cols both increase or decrease (diagonal match)
(agreed i need to elaborate on this)
if not match is found, discard the stack, start again.
(There are gaps in this approach, but would be happy to hear other alternatives)