Tableau Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
I think the class itself will contain a 2 dimensional array .
Since the number of mines is input, can we assume that we can randomly put the requisite number of mines ? Or will that be input too (although it's too cumbersome)
Every cell could have multiple states:
1. Unopened , mine ,
2. Unopened, no mine , with a number
3. Unopened, no mine , with no number (can be treated as zero)
4 . Opened,mine, detected (flag)
5. Opened, no mine , with a number
6. Opened, no mine , with no number (can be treated as zero)
We can create a 2 dim-array where each element is a struct and contains 3 elems
a. mine
b. open
c. neighbor_mines
The constructor could do this:
1. Create a 2-dim array with the above structure.For each element, we can set 1 or 0 by using a random function that'll ensure that number of mines are equal to the input. We can even control that by a loop to ensure that we don't put more mines than input.
2. Loop through the 2 dimensional array and
(a) set mine = decode(random(0,1) < prob,1,0)
(b) set open = 0
3. Loop again and set the neighbor for non mine records mines by summing up 'mine' a[x-1] to a[x+1] and a[y-1] to a[y+1]
I think the class itself will contain a 2 dimensional array .
Since the number of mines is input, can we assume that we can randomly put the requisite number of mines ? Or will that be input too (although it's too cumbersome)
Every cell could have multiple states:
1. Unopened , mine ,
2. Unopened, no mine , with a number
3. Unopened, no mine , with no number (can be treated as zero)
4 . Opened,mine, detected (flag)
5. Opened, no mine , with a number
6. Opened, no mine , with no number (can be treated as zero)
We can create a 2 dim-array where each element is a struct and contains 3 elems
a. mine
b. open
c. neighbor_mines
The constructor could do this:
1. Create a 2-dim array with the above structure.For each element, we can set 1 or 0 by using a random function that'll ensure that number of mines are equal to the input. We can even control that by a loop to ensure that we don't put more mines than input.
2. Loop through the 2 dimensional array and
(a) set mine = decode(random(0,1) < prob,1,0)
(b) set open = 0
3. Loop again and set the neighbor for non mine records mines by summing up 'mine' a[x-1] to a[x+1] and a[y-1] to a[y+1]
I think the class itself will contain a 2 dimensional array .
Since the number of mines is input, can we assume that we can randomly put the requisite number of mines ? Or will that be input too (although it's too cumbersome)
Every cell could have multiple states:
1. Unopened , mine ,
2. Unopened, no mine , with a number
3. Unopened, no mine , with no number (can be treated as zero)
4 . Opened,mine, detected (flag)
5. Opened, no mine , with a number
6. Opened, no mine , with no number (can be treated as zero)
We can create a 2 dim-array where each element is a struct and contains 3 elems
a. mine
b. open
c. neighbor_mines
The constructor could do this:
1. Create a 2-dim array with the above structure.For each element, we can set 1 or 0 by using a random function that'll ensure that number of mines are equal to the input. We can even control that by a loop to ensure that we don't put more mines than input.
2. Loop through the 2 dimensional array and
(a) set mine = decode(random(0,1) < prob,1,0)
(b) set open = 0
3. Loop again and set the neighbor for non mine records mines by summing up 'mine' a[x-1] to a[x+1] and a[y-1] to a[y+1]
This is the one of most reasonable ways of implementing constructor
class Minesweeper {
vector<vector<int8_t>> board;
int dim;
int mines;
public:
Minesweeper(int dim, int mines):
dim(dim), mines(mines){}
};
Why didn't I initialize the board? Because good MineSweeper implementation doesn't place mines during the construction, but defers it to the first move of the player. Assuming mines < dim**2 The first cell opened by the player is always empty and mines are randomly distributed among remaining dim**2-1 unopened cells. This improves usability of the game: user never loses with 1st move. Implementation of Minesweeper in Windows behaves like I described.
I assume that z provided is much less than x*y, otherwise this will take lot of time to initialize the board, there can be other approach to initialize the mines other than rand in case if z is large.
class game {
int x;
int y;
public:
static vector<vector<int>> board;
game(int x, int y, int z):x(x), y(y) {
if (z > x*y)
perror("Invlid configuration: %e", -EINVL);
board.resize(y);
board[0].resize(x);
while (z-- > 0) {
int r = 0, c = 0;
while (board[r][c]) {
r = rand() % y;
c = rand() % x;
}
board[r][c] = 1;
}
}
}
My answer
Mine.java
public class Mine {
private int x;
private int y;
public Mine(int x, int y){
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Mine other = (Mine) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
public String toString() {
return "x: " + x + ", y: " + y;
}
}
Game.java
import java.util.*;
public class Game {
private int width;
private int height;
private int numOfMines;
private HashSet<Mine> set = new HashSet<>();
public Game(int width, int height, int numOfMines) {
if(width*height < numOfMines) {
throw new ArithmeticException("Too much mines !!");
}
this.width = width;
this.height = height;
this.numOfMines = numOfMines;
setMines();
}
private void setMines() {
Random rand = new Random();
int i = 0;
while(i != numOfMines) {
int tempX = rand.nextInt(width);
int tempY = rand.nextInt(height);
Mine m = new Mine(tempX, tempY);
if(!set.contains(m)) {
set.add(m);
i++;
}
}
}
public HashSet<Mine> getSet() {
return set;
}
public void printSet() {
Iterator iterator = set.iterator();
while(iterator.hasNext()) {
System.out.println(iterator.next());
}
}
public static void main(String[] args) {
// Mine m = new Mine(1,1);
// System.out.println(m);
// System.out.println(m.equals(m));
Game g = new Game(9,6,12);
g.printSet();
}
}
public class MineSweeper
{
private int[,] _board;
private int _mines;
public MineSweeper(int x, int y, int mines)
{
if (mines > x * y)
throw new Exception("Invalid configuration");
_board = new int[x, y];
_mines = mines;
LoadMines();
}
private void LoadMines()
{
var rowCnt = _board.GetLength(0);
var colCnt = _board.GetLength(1);
for (var i = 0; i < _mines; i++)
{
var emptyCell = true;
while (emptyCell)
{
var row = GetRandomNumInRange(0, rowCnt);
var col = GetRandomNumInRange(0, colCnt);
if (_board[row, col] == 0)
{
_board[row, col] = 1;
emptyCell = false;
}
}
}
}
private int GetRandomNumInRange(int start, int end)
{
var rnd = new Random();
//NOTE, random upper bound is EXCLUSIVE of the given value
return rnd.Next(start, end);
}
public class MineSweeper
{
private int[,] _board;
private int _mines;
public MineSweeper(int x, int y, int mines)
{
if (mines > x * y)
throw new Exception("Invalid configuration");
_board = new int[x, y];
_mines = mines;
LoadMines();
}
private void LoadMines()
{
var rowCnt = _board.GetLength(0);
var colCnt = _board.GetLength(1);
for (var i = 0; i < _mines; i++)
{
var emptyCell = true;
while (emptyCell)
{
var row = GetRandomNumInRange(0, rowCnt);
var col = GetRandomNumInRange(0, colCnt);
if (_board[row, col] == 0)
{
_board[row, col] = 1;
emptyCell = false;
}
}
}
}
private int GetRandomNumInRange(int start, int end)
{
var rnd = new Random();
//NOTE, random upper bound is EXCLUSIVE of the given value
return rnd.Next(start, end);
}
public class MineSweeper
{
private int[,] _board;
private int _mines;
public MineSweeper(int x, int y, int mines)
{
if (mines > x * y)
throw new Exception("Invalid configuration");
_board = new int[x, y];
_mines = mines;
LoadMines();
}
private void LoadMines()
{
var rowCnt = _board.GetLength(0);
var colCnt = _board.GetLength(1);
for (var i = 0; i < _mines; i++)
{
var emptyCell = true;
while (emptyCell)
{
var row = GetRandomNumInRange(0, rowCnt);
var col = GetRandomNumInRange(0, colCnt);
if (_board[row, col] == 0)
{
_board[row, col] = 1;
emptyCell = false;
}
}
}
}
private int GetRandomNumInRange(int start, int end)
{
var rnd = new Random();
//NOTE, random upper bound is EXCLUSIVE of the given value
return rnd.Next(start, end);
}
}
I think the class itself will contain a 2 dimensional array .
- Anonymous September 24, 2015Since the number of mines is input, can we assume that we can randomly put the requisite number of mines ? Or will that be input too (although it's too cumbersome)
Every cell could have multiple states:
1. Unopened , mine ,
2. Unopened, no mine , with a number
3. Unopened, no mine , with no number (can be treated as zero)
4 . Opened,mine, detected (flag)
5. Opened, no mine , with a number
6. Opened, no mine , with no number (can be treated as zero)
We can create a 2 dim-array where each element is a struct and contains 3 elems
a. mine
b. open
c. neighbor_mines
The constructor could do this:
1. Create a 2-dim array with the above structure.For each element, we can set 1 or 0 by using a random function that'll ensure that number of mines are equal to the input. We can even control that by a loop to ensure that we don't put more mines than input.
2. Loop through the 2 dimensional array and
(a) set mine = decode(random(0,1) < prob,1,0)
(b) set open = 0
3. Loop again and set the neighbor for non mine records mines by summing up 'mine' a[x-1] to a[x+1] and a[y-1] to a[y+1]