Microsoft Interview Question
SDE-3sCountry: United States
Interview Type: In-Person
using System;
using System.Collections.Generic;
/*
* [ 0, 1, 0 ]
* [ 2, 2, 1 ]
* [ 1, 1, 2 ]
* The solution focuses on finding the number of options for next move
* for player2 which will result in loss of player1
*/
class TicToe
{
static void Main(string[] args)
{
Console.WriteLine("starting ways to lose :)");
int[,] matrix = new int[3, 3] { { 0, 1, 0 }, { 2, 2, 1 }, { 1, 1, 2 } };
PrintMatrix(matrix, "original copy");
var response = WaysToLose(matrix);
Console.WriteLine($"Ways to lose for player 1 is {response}");
Console.ReadLine();
}
//Calculate ways to lose for player1
//Change one empty spot player 2 and see
//if player 2 wins on all 8 combinations to win tic tac toe
private static int WaysToLose(int[,] matrix)
{
if (matrix == null || matrix.GetLength(0) != matrix.GetLength(1))
return 0;
var emptySpots = GetEmptySpots(matrix);
var finalWaysToLose = 0;
foreach (var item in emptySpots)
{
var copiedArray = ArrayCopy(matrix);
copiedArray[item.Item1, item.Item2] = 2;
PrintMatrix(copiedArray, "matrix under test");
//Set all winning possibilities to true and falsify them on each condition
var resultDictionary = new Dictionary<string, bool>()
{
{"row1",true},
{"row2",true},
{"row3",true},
{"column1",true},
{"column2",true},
{"column3",true},
{"diagonal1",true},
{"diagonal2",true}
};
//Check if any rows have same number for 2 to win
for (int i = 0; i < copiedArray.GetLength(0); i++)
{
for (int j = 0; j < copiedArray.GetLength(1); j++)
{
if (copiedArray[i, j] != 2)
{
resultDictionary[$"row{i + 1}"] = false;
}
}
}
//Check if any columns have same number for 2 to win
for (int j = 0; j < copiedArray.GetLength(1); j++)
{
for (int i = 0; i < copiedArray.GetLength(0); i++)
{
if (copiedArray[i, j] != 2)
{
resultDictionary[$"column{j + 1}"] = false;
}
}
}
//Check if any diagonals have same number for 2 to win
for (int i = 0; i < copiedArray.GetLength(0); i++)
{
for (int j = 0; j < copiedArray.GetLength(1); j++)
{
if (i == j && copiedArray[i, j] != 2)
{
resultDictionary[$"diagonal1"] = false;
}
if (i + j == 2 && copiedArray[i, j] != 2)
{
resultDictionary[$"diagonal2"] = false;
}
}
}
foreach (var record in resultDictionary)
{
Console.WriteLine($"{record.Key}:{record.Value}");
if (record.Value)
{
finalWaysToLose++;
}
}
}
return finalWaysToLose;
}
private static IEnumerable<Tuple<int, int>> GetEmptySpots(int[,] matrix)
{
var list = new List<Tuple<int, int>>();
for (int i = 0; i < matrix.GetLength(0); i++)
{
for (int j = 0; j < matrix.GetLength(1); j++)
{
if (matrix[i, j] == 0)
{
Console.WriteLine($"empty spot found at {i},{j}");
list.Add(new Tuple<int, int>(i, j));
}
}
}
return list;
}
private static int[,] ArrayCopy(int[,] matrix)
{
int[,] copyArray = new int[matrix.GetLength(0), matrix.GetLength(1)];
int[] buffer = new int[matrix.GetLength(0) * matrix.GetLength(1)];
Buffer.BlockCopy(matrix, 0, buffer, 0, buffer.Length * sizeof(int));
Buffer.BlockCopy(buffer, 0, copyArray, 0, buffer.Length * sizeof(int));
PrintMatrix(copyArray, "copied Array");
return copyArray;
}
private static void PrintMatrix(int[,] matrix, string message)
{
Console.WriteLine(message);
for (int i = 0; i < matrix.GetLength(0); i++)
{
for (int j = 0; j < matrix.GetLength(1); j++)
{
Console.Write($"{matrix[i, j]} ");
if (j == matrix.GetUpperBound(0))
{
Console.WriteLine();
}
}
}
}
}
# [0, 1, 0]
# [2, 2, 0]
# [1, 1, 2]
import collections
input = [[0, 1, 0],[2, 2, 0],[1, 1, 2]]
# 8 configs for lose from player1
x_counter = collections.Counter()
y_counter = collections.Counter()
# convert all 0's in matrix to 2's
for y_index, y in enumerate(input):
for x_index, x in enumerate(y):
if x == 0:
input[y_index][x_index] = 2
#match against known cases of player2 win
#across, or up-down cases
for y_index, y in enumerate(input):
for x_index, x in enumerate(y):
if x == 2:
y_counter[str(y_index)] += 1
x_counter[str(x_index)] += 1
across_count = list(y_counter.values()).count(3)
vert_count = list(x_counter.values()).count(3)
#diagonal cases
#I'm not using list comprehension because non-python readers wouldn't be able to follow the code flow
#easy case
diag_case_LR = 1
max_index = len(input) - 1
for xy_index in range(0, max_index+1):
if input[xy_index][xy_index] != 2:
diag_case_LR = 0
break
#harder case
diag_case_RL = 1
for y_index in range(0, max_index+1):
x_index = max_index-y_index
if input[y_index][x_index] != 2:
diag_case_RL = 0
break
#return counter
print('across_count:{0}'.format(across_count))
print('vert_count:{0}'.format(vert_count))
print('diag_case_LR:{0}'.format(diag_case_1))
print('diag_case_RL:{0}'.format(diag_case_2))
print('total:{0}'.format(across_count + vert_count + diag_case_1 + diag_case_2))
1) search next 0-spot
- Anonymous February 26, 20182) try build all possible wins (diagonal, vertical, horizontal)
3) goto 1)
Similar to 9-queens