Microsoft Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

For 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)

- whitenoise April 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- KGhatak June 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a

- K June 27, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More