xyz Interview Question Software Developers
Country: United States
Interview Type: Written Test
So my approach is instead of going to each cell and then looking around the cell for mines, since I have a map of all the mines, find each mine and then bump up the value of some other grid that is a 2-D array of 0's.
Implementation in Javascript. Basically no error handling in this code for bad input and such but this is the general idea.
function generateMineMap(grid) {
var minRow = 0;
var minCol = 0;
var maxRow = grid.length;
var maxCol = grid[0].length;
var result = [];
// Generate initial map
for (var i = 0; i < maxRow; i++) {
result.push([]);
for (var j = 0; j < maxCol; j++) {
result[i].push(0);
}
}
for (var i = 0; i < maxRow; i++) {
for (var j = 0; j < maxCol; j++) {
if (grid[i][j] === 1) {
increaseIfPossible(result, i-1, j-1);
increaseIfPossible(result, i, j-1);
increaseIfPossible(result, i+1, j-1);
increaseIfPossible(result, i-1, j);
increaseIfPossible(result, i+1, j);
increaseIfPossible(result, i-1, j+1);
increaseIfPossible(result, i, j+1);
increaseIfPossible(result, i+1, j+1);
}
}
}
return result;
}
function increaseIfPossible(grid, row, col) {
if (grid[row] !== undefined && grid[row][col] !== undefined) {
grid[row][col] += 1;
}
}
var mineGrid = [ [0, 1, 0],
[0, 0, 0],
[1, 0, 0] ];
var mineMap = generateMineMap(mineGrid)
mineMap.forEach(function(row) {
console.log(row.join(' '));
});
Java Implementation:
/**
* Created by Upen on 10/20/2015.
*/
public class CountMines {
/**
* Positive number that represents the number of the grids
*/
private int N;
/**
* This is the array that stores the array read form the stdin. Each element in this
* arry is either 0 or a 1
*/
private int[] mInputArray;
/**
* This is the n*n array that represents the output. Each element in this array represents
* the number of '1' around it.
*/
int[][] mOutputArray;
public CountMines(int[] array, int size){
N = size;
mInputArray = array;
mOutputArray = new int[size][size];
}
public int[][] solveAndGetArray(){
solveProblem();
return mOutputArray;
}
private void solveProblem(){
for (int i=0; i<N; i++){
for (int j=0; j<N; j++){
mOutputArray[i][j] = findSorroundingOnes(i, j);
}
}
}
private int findSorroundingOnes(int i, int j){
return getOneOrZero(i-1, j-1)
+ getOneOrZero(i, j-1)
+ getOneOrZero(i+1, j-1)
+ getOneOrZero(i-1, j)
+ getOneOrZero(i+1, j)
+ getOneOrZero(i-1, j+1)
+ getOneOrZero(i, j+1)
+ getOneOrZero(i+1, j+1);
}
/**
* This is the function that takes x and y position of the 2 by 2 array and
* returns the equivalant position in 1 dimensional array
* @param i The x position of the array
* @param j The y position of the array
*/
private int intoOneDim(int i, int j){
return i*N + j;
}
/**
* This is the method that returns the value in the grid i.e. weather the board has
* 1 or 0. If the given position is not valid we return 0
* @param i The x position in the board
* @param j The y position if the grid
* @return The value (0 or 1) in the given position
*/
private int getOneOrZero(int i, int j){
if (isValidIndex(i, j)){
return mInputArray[intoOneDim(i, j)];
}
return 0;
}
/**
* This is the method that checks if the x and y position are with in the
* bound of indices in the array
* @param i The x index of the array
* @param j The y index of the array
* @return
*/
private boolean isValidIndex(int i, int j){
return i >= 0 && i < N && j < N && j >= 0;
}
public static void main(String[] args) {
CountMines g = new CountMines(new int[]{0, 1, 0, 0, 0, 0, 1, 0, 0}, 3);
int[][] array = g.solveAndGetArray();
for (int i=0; i<array.length; i++){
for (int j=0; j<array.length; j++){
System.out.print("" + array[i][j] + " ");
}
System.out.println();
}
}
}
without using a new array (in place)
O(n), where n=N*N
C#
static public void PrintSurroundingSumInPlace()
{
String input = "3 0 1 0 0 0 0 1 0 0";//Console.ReadLine();
int ind = 0;
//find the first white space to identify N
for (; ind < input.Length; ind++)
{
if (input[ind] == ' ') break;
}
//get N
int N = int.Parse(input.Substring(0, ind));
int matrixStart = ++ind;
for (int row = 0; row < N; row++)
{
for (int col = 0; col < N; col++)
{
int sum = 0;
for (int pRow = row - 1; pRow <= row + 1; pRow++)
{
if ((pRow < N) && (pRow >= 0))
{
for (int pCol = col - 1; pCol <= col + 1; pCol++)
{
if ((pCol < N) && (pCol >= 0))
{
sum += input[matrixStart + 2 * (pRow * N + pCol)] - '0'; ;
}
}
}
}
//Substract self
sum -= input[matrixStart + 2 * (row * N + col)] - '0';
Console.Write("{0}", sum);
if (col != N - 1)
Console.Write(" ");
}
if (row != N - 1)
Console.WriteLine();
}
}
int GetMineMatrix(int** array, int size, int** matrix)
{
if (size <= 0) return 0; // invalid array size
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (array[i][j] == 1)
{
if (i - 1 >= 0)
{
if (j - 1 >= 0)
{
matrix[i - 1][j - 1]++;
}
matrix[i - 1][j]++;
if (j + 1 < size)
{
matrix[i - 1][j + 1]++;
}
}
if (j - 1 >= 0)
{
matrix[i][j - 1]++;
}
if (j + 1 < size)
{
matrix[i][j + 1]++;
}
if (i + 1 < size)
{
if (j - 1 >= 0)
{
matrix[i + 1][j - 1]++;
}
matrix[i + 1][j]++;
if (j + 1 < size)
{
matrix[i + 1][j + 1]++;
}
}
}//end if (array[i][j] == 1)
}
}
return 1;//success
}
void main()
{
int size;
int ** array;
cout << "Enter size of matrix:\n";
cin >> size;
array = new int*[size];
for (int i = 0; i < size; i++)
{
array[i] = new int[size];
}
cout << "Enter the matrix values(only 0 or 1 allowed):\n";
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
cin >> array[i][j];
}
}
//initialize the output matrix
int **matrix = new int*[size];
for (int i = 0; i < size; i++)
{
matrix[i] = new int[size];
}
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
matrix[i][j] = 0;
}
}
int retval = GetMineMatrix(array, size, matrix);
if (retval == 1)
{
cout << "Mine Matrix =\n";
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
}
int GetMineMatrix(int** array, int size, int** matrix)
{
if (size <= 0) return 0; // invalid array size
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (array[i][j] == 1)
{
if (i - 1 >= 0)
{
if (j - 1 >= 0)
{
matrix[i - 1][j - 1]++;
}
matrix[i - 1][j]++;
if (j + 1 < size)
{
matrix[i - 1][j + 1]++;
}
}
if (j - 1 >= 0)
{
matrix[i][j - 1]++;
}
if (j + 1 < size)
{
matrix[i][j + 1]++;
}
if (i + 1 < size)
{
if (j - 1 >= 0)
{
matrix[i + 1][j - 1]++;
}
matrix[i + 1][j]++;
if (j + 1 < size)
{
matrix[i + 1][j + 1]++;
}
}
}//end if (array[i][j] == 1)
}
}
return 1;//success
}
void main()
{
int size;
int ** array;
cout << "Enter size of matrix:\n";
cin >> size;
array = new int*[size];
for (int i = 0; i < size; i++)
{
array[i] = new int[size];
}
cout << "Enter the matrix values(only 0 or 1 allowed):\n";
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
cin >> array[i][j];
}
}
//initialize the output matrix
int **matrix = new int*[size];
for (int i = 0; i < size; i++)
{
matrix[i] = new int[size];
}
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
matrix[i][j] = 0;
}
}
int retval = GetMineMatrix(array, size, matrix);
if (retval == 1)
{
cout << "Mine Matrix =\n";
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
}
int GetMineMatrix(int** array, int size, int** matrix)
{
if (size <= 0) return 0; // invalid array size
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (array[i][j] == 1)
{
if (i - 1 >= 0)
{
if (j - 1 >= 0)
{
matrix[i - 1][j - 1]++;
}
matrix[i - 1][j]++;
if (j + 1 < size)
{
matrix[i - 1][j + 1]++;
}
}
if (j - 1 >= 0)
{
matrix[i][j - 1]++;
}
if (j + 1 < size)
{
matrix[i][j + 1]++;
}
if (i + 1 < size)
{
if (j - 1 >= 0)
{
matrix[i + 1][j - 1]++;
}
matrix[i + 1][j]++;
if (j + 1 < size)
{
matrix[i + 1][j + 1]++;
}
}
}//end if (array[i][j] == 1)
}
}
return 1;//success
}
void main()
{
int size;
int ** array;
cout << "Enter size of matrix:\n";
cin >> size;
array = new int*[size];
for (int i = 0; i < size; i++)
{
array[i] = new int[size];
}
cout << "Enter the matrix values(only 0 or 1 allowed):\n";
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
cin >> array[i][j];
}
}
//initialize the output matrix
int **matrix = new int*[size];
for (int i = 0; i < size; i++)
{
matrix[i] = new int[size];
}
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
matrix[i][j] = 0;
}
}
int retval = GetMineMatrix(array, size, matrix);
if (retval == 1)
{
cout << "Mine Matrix =\n";
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
}
int GetMineMatrix(int** array, int size, int** matrix)
{
if (size <= 0) return 0; // invalid array size
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (array[i][j] == 1)
{
if (i - 1 >= 0)
{
if (j - 1 >= 0)
{
matrix[i - 1][j - 1]++;
}
matrix[i - 1][j]++;
if (j + 1 < size)
{
matrix[i - 1][j + 1]++;
}
}
if (j - 1 >= 0)
{
matrix[i][j - 1]++;
}
if (j + 1 < size)
{
matrix[i][j + 1]++;
}
if (i + 1 < size)
{
if (j - 1 >= 0)
{
matrix[i + 1][j - 1]++;
}
matrix[i + 1][j]++;
if (j + 1 < size)
{
matrix[i + 1][j + 1]++;
}
}
}//end if (array[i][j] == 1)
}
}
return 1;//success
}
void main()
{
int size;
int ** array;
cout << "Enter size of matrix:\n";
cin >> size;
array = new int*[size];
for (int i = 0; i < size; i++)
{
array[i] = new int[size];
}
cout << "Enter the matrix values(only 0 or 1 allowed):\n";
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
cin >> array[i][j];
}
}
//initialize the output matrix
int **matrix = new int*[size];
for (int i = 0; i < size; i++)
{
matrix[i] = new int[size];
}
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
matrix[i][j] = 0;
}
}
int retval = GetMineMatrix(array, size, matrix);
if (retval == 1)
{
cout << "Mine Matrix =\n";
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
for (int i = 0; i < size; i++)
{
delete[] array[i];
}
delete[] array;
for (int i = 0; i < size; i++)
{
delete [] matrix[i];
}
delete[] matrix;
}
def file2array(textfile):
""" Given a text file, extracts the matrix to a 2D
array and returns the array plus the number of lines
in the file
"""
file = open(textfile)
line_count = 0
array = []
for line in file:
array.append(line.split())
line_count = line_count + 1
return array, line_count
def count_mines(file):
minearray, line_count = file2array(file)
#initialize an array of apt size with all zeroes
result = [[0 for a in range(line_count)] for b in range(line_count)]
#going through each element of mine array
for i in range(0, line_count):
for j in range(0, line_count):
#I have strings of 1 and 0 in minearray from file2array function
if minearray[i][j] == '1':
for p in range(-1,2):
for q in range(-1,2):
#checking for all the edge cases and the element itself
if p != 0 or q != 0:
if 0 <= i+p <= line_count-1 and 0 <= j+q <= line_count-1:
result[i+p][j+q] += 1
return result
print count_mines('mines.txt')
This is an O(n^2) approach..
#include <bits/stdc++.h> using namespace std; int neighbours[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; int main() { int n; scanf("%d",&n); int a[n][n]; int ans[n][n]; for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) scanf("%d",&a[i][j]); } int count = 0; for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { count = 0; for(int k = 0;k < 8;k++) { if(i+neighbours[k][0] >= 0 && i+neighbours[k][0] < n && j+neighbours[k][1] >= 0 && j+neighbours[k][1] < n) { if(a[i+neighbours[k][0]][j+neighbours[k][1]] == 1) count++; } } ans[i][j] = count; } } for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { printf("%d ",ans[i][j]); } printf("\n"); } return 0; }For each element, count number of 1's in surrounding cells and update ans[][].
- vinayawsm October 20, 2015