Microsoft Interview Question Interns
Country: United States
/*
You are given a 2D char matrix representing the game board. 'M' represents an unrevealed mine, 'E' represents an unrevealed empty square, 'B' represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit ('1' to '8') represents how many mines are adjacent to this revealed square, and finally 'X' represents a revealed mine.
Now given the next click position (row and column indices) among all the unrevealed squares ('M' or 'E'), return the board after revealing this position according to the following rules:
If a mine ('M') is revealed, then the game is over - change it to 'X'.
If an empty square ('E') with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.
If an empty square ('E') with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
Return the board when no more squares will be revealed.
Input:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
Click : [1,2]
Output:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'X', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
*/
public class MineSweeper{
public char[][] ClickFunction(char[][] board, int[] click) {
if (board[click[0]][click[1]] == 'M') {
board[click[0]][click[1]] = 'X';
return board;
}
int n = board.length;
int m = board[0].length;
Stack<Integer> rw = new Stack<Integer>();
Stack<Integer> col = new Stack<Integer>();
rw.push(click[0]);
col.push(click[1]);
while(!rw.isEmpty()) {
int curRw = rw.pop();
int curCol = col.pop();
if(board[curRw][curCol] != 'E')
continue;
int adj = check(board, curRw, curCol);
if (adj != 0) {
board[curRw][curCol] = Character.forDigit(adj, 10);
continue;
}
board[curRw][curCol] = 'B';
for(int i = curRw-1; i<= curRw+1; i++) {
for (int j=curCol-1; j<=curCol+1; j++){
if(i >= 0 && i < n && j >=0 && j < m){
if(board[i][j] == 'E') {
rw.push(i);
col.push(j);
}
}
}
}
}
return board;
}
private int check(char[][] board, int rw, int col) {
int count = 0;
int n = board.length;
int m = board[0].length;
for(int i = rw-1; i<= rw+1; i++) {
for (int j=col-1; j<=col+1; j++){
if(i >= 0 && i < n && j >=0 && j < m){
if(board[i][j] == 'M') count++;
}
}
}
return count;
}
}
/*
You are given a 2D char matrix representing the game board. 'M' represents an unrevealed mine, 'E' represents an unrevealed empty square, 'B' represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit ('1' to '8') represents how many mines are adjacent to this revealed square, and finally 'X' represents a revealed mine.
Now given the next click position (row and column indices) among all the unrevealed squares ('M' or 'E'), return the board after revealing this position according to the following rules:
If a mine ('M') is revealed, then the game is over - change it to 'X'.
If an empty square ('E') with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.
If an empty square ('E') with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
Return the board when no more squares will be revealed.
Input:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
Click : [1,2]
Output:
[['B', '1', 'E', '1', 'B'],
['B', '1', 'X', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
*/
public class MineSweeper{
public char[][] ClickFunction(char[][] board, int[] click) {
if (board[click[0]][click[1]] == 'M') {
board[click[0]][click[1]] = 'X';
return board;
}
int n = board.length;
int m = board[0].length;
Stack<Integer> rw = new Stack<Integer>();
Stack<Integer> col = new Stack<Integer>();
rw.push(click[0]);
col.push(click[1]);
while(!rw.isEmpty()) {
int curRw = rw.pop();
int curCol = col.pop();
if(board[curRw][curCol] != 'E')
continue;
int adj = check(board, curRw, curCol);
if (adj != 0) {
board[curRw][curCol] = Character.forDigit(adj, 10);
continue;
}
board[curRw][curCol] = 'B';
for(int i = curRw-1; i<= curRw+1; i++) {
for (int j=curCol-1; j<=curCol+1; j++){
if(i >= 0 && i < n && j >=0 && j < m){
if(board[i][j] == 'E') {
rw.push(i);
col.push(j);
}
}
}
}
}
return board;
}
private int check(char[][] board, int rw, int col) {
int count = 0;
int n = board.length;
int m = board[0].length;
for(int i = rw-1; i<= rw+1; i++) {
for (int j=col-1; j<=col+1; j++){
if(i >= 0 && i < n && j >=0 && j < m){
if(board[i][j] == 'M') count++;
}
}
}
return count;
}
}
#include <random>
#include <vector>
#include <iostream>
const int _RC_EMPTY=0;
const int _RC_EXPOSED=2;
const int _RC_MINE=1;
class Board
{
public:
Board ( size_t r, size_t c, size_t m)
{
std::srand(time(NULL));
_board = std::vector<std::vector<int>>(c,std::vector<int>(r,_RC_EMPTY));
for ( int i= 0; i< m; i++ )
{
_board[rand() %c][rand() % r] = _RC_MINE;
}
}
void PrintBoard( bool final = false )
{
for ( std::vector<int> & v : _board )
{
std::cout << "|";
for ( int i : v )
{
if ( final )
std::cout << (( i == _RC_MINE) ? "*" : " ");
else
std::cout << (( i == _RC_EXPOSED) ? "X" : " ");
std::cout << "|";
}
std::cout << std::endl;
}
}
int get( int r, int c)
{
return _board[r][c];
}
void set( int r, int c, int v)
{
_board[r][c] = v;
}
std::vector<std::vector<int>> _board;
};
class MineSweeper
{
public:
MineSweeper(size_t r, size_t c, size_t m):_board(r,c,m),_sizer(r),_sizec(c)
{
_board.PrintBoard( false );
}
int Play()
{
int r = rand() %_sizer;
int c = rand() %_sizec;
int finished = false;
if ( _board.get(c,r) == _RC_MINE ){
finished = true;
}
else{
finished = false;
_board.set(c,r, _RC_EXPOSED);
}
_board.PrintBoard( finished );
return finished;
}
Board _board;
int _sizer;
int _sizec;
};
int main(int argc, const char * argv[]) {
MineSweeper m(10,6,12);
while ( m.Play() == false );
return 0;
}
MineSweeper game rules are briefed here:
The games is played on a M by N grid of `cells', each of which is either empty or contains an explosive mine. Your task (should you choose to accept it) is to locate all of the mines without causing any of them to explode.
Sounds easy? Well, unfortunately for you the location of the mines is a well-kept secret. In fact, at the beginning of the game you have no information as to whether any given cell contains a mine or not. Your only course of action is to `reveal' the contents of a chosen cell. Should you reveal a mine, the game is over and you have lost. If, however, you reveal an empty cell, two useful things will happen:
The program will indicate how many of the revealed cell's eight neighbours do contain mines.
Any neighbouring empty cells will also be revealed in the same way.
Together these should provide you with enough information to determine where the mines are hidden. The game is over (and you have won) when the number of unrevealed cells is equal to the number of mines on the board (since every unrevealed cell must then contain a mine).
Below are high level classes for the game. There are 2 classes: Board class and the MineSweeper Class.
- R@M3$H.N January 14, 2017public abstract class Board { // Board size protected int width, height; // Number of mines on the board protected int numMines; // Number of cells currently marked protected int numMarked; // Number of cells yet to be revealed protected int numUnknown; // Indicates where the mines are hidden protected boolean[][] mines; // The current state of the board protected int[][] board; // Constants for cell contents. The MINE value might be returned by // reveal(), the others are only used internally but will probably be // required in subclasses. public static final int UNKNOWN = -1; public static final int MARKED = -2; public static final int MINE = -3; public Board(int width, int height, int numMines) { this.width = width; this.height = height; this.numMines = numMines; this.numMarked = 0; this.numUnknown = width * height; // Allocate storage for game board and mines mines = new boolean[width][height]; board = new int[width][height]; // Clear the board for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { mines[i][j] = false; board[i][j] = UNKNOWN; } } // Randomly allocate mines. int cells = width * height; int temp = 0; Random rand = new Random(); while (temp < numMines) { int cell = rand.nextInt(); cell = (cell < 0 ? -cell : cell)%cells; if (!mines[cell%width][cell/width]) { mines[cell%width][cell/width] = true; temp++; } } } public void draw() { //Draw representation of Board } public int reveal(int x, int y) { //Reveal the contents of the cell at position (x, y) on the board. } public boolean mark(int x, int y) //Mark' the cell (x, y), probably to indicate that a player thinks there may be a mine there. } public boolean unmark(int x, int y) { //Unmark the previously marked cell at (x, y). } private int closeMines(int x, int y) { //Work out how many neighbours of cell (x, y) contain mines. Return the //number of explosive neighbours. } } public class MineSweeper { // The game board private Board board; // Tokenizer for commands private StreamTokenizer tok; // Various flags used by play() and doCommand() private boolean done, quit, win; // Contents of last cell revealed private int lastCell; public MineSweeper(int width, int height, int mines) { // Create the game board board = new TextBoard(width, height, mines); // Set up the command tokenizer tok = new StreamTokenizer(new InputStreamReader(System.in)); done = win = quit = false; } public void play() throws IOException { //Game play code goes here. On CLick what should happen } public static void main(String[] args) throws IOException { MineSweeper game; if (args.length < 3) { System.out.println("Usage: java MineSweeper width height mines"); System.exit(0); } else { int width = Integer.parseInt(args[0]); int height = Integer.parseInt(args[1]); int mines = Integer.parseInt(args[2]); game = new MineSweeper(width, height, mines); game.play(); } } }