## Booking.com Interview Question for Software Developers

Country: Netherlands
Interview Type: In-Person

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

www(dot)repl(dot)it/Klkv/4

``````import Data.Set (Set)
import qualified Data.Set as Set

-- defining our ADTs & getState signature. also, `Word` is unsigned int32
data State = B | W | E | O deriving (Show, Eq)
data Cord = Cord { x :: Word, y :: Word } deriving (Show, Eq, Ord)

-- getState is a provided function that translates cordination into its state
getState :: Cord -> State

-- and here's where the magic happens (isCaptured is our public API)
isCaptured :: Cord -> Bool
isCaptured cord = selfState `notElem` [O, E] && (isOccupied selfState \$ getStates cord Set.empty)
where selfState = getState cord

surrounding :: Cord -> [Cord]
surrounding (Cord x y) = [Cord (x - 1) y, Cord (x + 1) y, Cord x (y - 1), Cord x (y + 1)]

getStates :: Cord -> Set Cord -> [State]
getStates self visited = cords >>= (\c -> if getState self == getState c then getStates c (Set.insert self visited) else [getState c])
where cords = filter (`Set.notMember` visited) \$ surrounding self

isOccupied :: State -> [State] -> Bool
isOccupied _ [] = False
isOccupied x xs = all (`notElem` [E, x]) xs

-- sample data
getState (Cord 1 1) = B
getState (Cord 2 1) = W
getState (Cord 1 2) = W

getState (Cord 4 3) = B

getState (Cord 7 3) = W
getState (Cord 8 2) = W
getState (Cord 8 3) = B
getState (Cord 8 4) = W

getState (Cord 13 2) = W
getState (Cord 13 3) = W
getState (Cord 13 4) = W
getState (Cord 14 1) = W
getState (Cord 14 2) = B
getState (Cord 14 3) = B
getState (Cord 14 4) = B
getState (Cord 14 5) = W
getState (Cord 15 2) = W
getState (Cord 15 3) = W
getState (Cord 15 4) = W

-- defining defaults and setting a 50x50 board
getState (Cord x y)
| x <= 0 || y <= 0 = O
| x > 50 || y > 50 = O
| otherwise = E

-- and checking if anything here actually works
main :: IO()
main = print [isCaptured \$ Cord 1 1, isCaptured \$ Cord 4 3, isCaptured \$ Cord 8 3, isCaptured \$ Cord 14 2]``````

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

``````class Matrix<T> : IEnumerable<T[]>
{
private int rowsCount;
private int colsCount;
private T[][] data;

public Matrix(int rowsCount, int colsCount)
{
this.rowsCount = rowsCount;
this.colsCount = colsCount;

this.data = new T[rowsCount][];

for (int i = 0; i < this.rowsCount; i++)
{
this.data[i] = new T[colsCount];
}
}

public T[] this[int row]
{
get
{
return this.data[row];
}
}

{
{
return;
}
}

public IEnumerator<T[]> GetEnumerator()
{
foreach (var item in this.data)
{
yield return item;
}
}

IEnumerator IEnumerable.GetEnumerator()
{
foreach (var item in this.data)
{
yield return item;
}
}

public int NumRows { get { return this.rowsCount; } }
public int NumCols { get { return this.colsCount; } }

}
class Program
{
static void Main(string[] args)
{
var n = 5;
var mat = new Matrix<char>(n, n)
{
{'E','E','E','E','E'},
{'E','W','W','W','E'},
{'W','B','B','B','W'},
{'E','W','W','W','E'},
{'E','E','E','E','E'}
};
var visited = new Matrix<bool>(n, n);

var isCaptured = FindIsCaptured(mat, visited, 2, 3);

Console.WriteLine(isCaptured);
}

private static bool FindIsCaptured(Matrix<char> mat, Matrix<bool> visited, int row, int column)
{
if (visited[row][column])
{
return true;
}

visited[row][column] = true;

if (mat[row][column] == 'E')
{
return false;
}

var isOOB = IsRowColumPairOutofBound(mat, row, column);

if (isOOB) return true;

var topCoords = Tuple.Create(row - 1, column);
var bottomCoords = Tuple.Create(row + 1, column);
var leftCoords = Tuple.Create(row, column - 1);
var rightCoords = Tuple.Create(row, column + 1);

var isTopOOB = IsRowColumPairOutofBound(mat, topCoords.Item1, topCoords.Item2);
var isBottomOOB = IsRowColumPairOutofBound(mat, bottomCoords.Item1, bottomCoords.Item2);
var isLeftOOB = IsRowColumPairOutofBound(mat, leftCoords.Item1, leftCoords.Item2);
var isRightOOB = IsRowColumPairOutofBound(mat, rightCoords.Item1, rightCoords.Item2);

var isTopCaptured = isTopOOB || (mat[topCoords.Item1][topCoords.Item2] != 'E' && mat[topCoords.Item1][topCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, topCoords.Item1, topCoords.Item2);
var isBottomCaptured = isBottomOOB || (mat[bottomCoords.Item1][bottomCoords.Item2] != 'E' && mat[bottomCoords.Item1][bottomCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, bottomCoords.Item1, bottomCoords.Item2);
var isLeftCaptured = isLeftOOB || (mat[leftCoords.Item1][leftCoords.Item2] != 'E' && mat[leftCoords.Item1][leftCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, leftCoords.Item1, leftCoords.Item2);
var isRightCaptured = isRightOOB || (mat[rightCoords.Item1][rightCoords.Item2] != 'E' && mat[rightCoords.Item1][rightCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, rightCoords.Item1, rightCoords.Item2);

return isTopCaptured && isBottomCaptured && isLeftCaptured && isRightCaptured;
}

private static bool IsRowColumPairOutofBound(Matrix<char> mat, int row, int column)
{
if (row < 0)
{
return true;
}

if (row >= mat.NumRows)
{
return true;
}

if (column < 0)
{
return true;
}

if (column >= mat.NumCols)
{
return true;
}

return false;
}
}``````

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

Sorry if I misunderstood, the question, it seems fairly straight forward from description, here is some pseudo code
bool IsCaptured(int x, int y) {
if(x < 0 || y <0 || x >= state.GetLength(0) || y >= state.GetLength(1))
{
return false;
}
// or single cell
return true
var currentState = state[x,y];
if(x -1 >=0 && state[x-1, y] == currentState or empty){ return false;}
if(y -1 >=0 && state[x, y-1] == currentState or empty){ return false;}
if(x + 1 < state.GetLength(0) && state[x + 1, y] == currentState or empty){ return false;}
if(y + 1 < state.GetLength(1) && state[x, y + 1] == currentState or empty){ return false;}
}

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

solution should consider the clustered capture situation as described in example #2 (i.e. recursion)

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

solution should be recursive and considered 'clustered' situation (see example #2).

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

@johanson1, thanks for pointing out what I missed (if cell neighboring has like wise state, my code has to check it is not captured as well which is recursive in nature), sorry for my incorrect answer, I will try out dp approach with some memorization to solve it, thinking about it see O(n^2), but may be I am wrong, I will try to work it out, thanks again

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

``````class Matrix<T> : IEnumerable<T[]>
{
private int rowsCount;
private int colsCount;
private T[][] data;

public Matrix(int rowsCount, int colsCount)
{
this.rowsCount = rowsCount;
this.colsCount = colsCount;

this.data = new T[rowsCount][];

for (int i = 0; i < this.rowsCount; i++)
{
this.data[i] = new T[colsCount];
}
}

public T[] this[int row]
{
get
{
return this.data[row];
}
}

{
{
return;
}
}

public IEnumerator<T[]> GetEnumerator()
{
foreach (var item in this.data)
{
yield return item;
}
}

IEnumerator IEnumerable.GetEnumerator()
{
foreach (var item in this.data)
{
yield return item;
}
}

public int NumRows { get { return this.rowsCount; } }
public int NumCols { get { return this.colsCount; } }

}
class Program
{
static void Main(string[] args)
{
var n = 5;
var mat = new Matrix<char>(n, n)
{
{'E','E','E','E','E'},
{'E','W','W','W','E'},
{'W','B','B','B','W'},
{'E','W','W','W','E'},
{'E','E','E','E','E'}
};
var visited = new Matrix<bool>(n, n);

var isCaptured = FindIsCaptured(mat, visited, 2, 3);

Console.WriteLine(isCaptured);
}

private static bool FindIsCaptured(Matrix<char> mat, Matrix<bool> visited, int row, int column)
{
if (visited[row][column])
{
return true;
}

visited[row][column] = true;

if (mat[row][column] == 'E')
{
return false;
}

var isOOB = IsRowColumPairOutofBound(mat, row, column);

if (isOOB) return true;

var topCoords = Tuple.Create(row - 1, column);
var bottomCoords = Tuple.Create(row + 1, column);
var leftCoords = Tuple.Create(row, column - 1);
var rightCoords = Tuple.Create(row, column + 1);

var isTopOOB = IsRowColumPairOutofBound(mat, topCoords.Item1, topCoords.Item2);
var isBottomOOB = IsRowColumPairOutofBound(mat, bottomCoords.Item1, bottomCoords.Item2);
var isLeftOOB = IsRowColumPairOutofBound(mat, leftCoords.Item1, leftCoords.Item2);
var isRightOOB = IsRowColumPairOutofBound(mat, rightCoords.Item1, rightCoords.Item2);

var isTopCaptured = isTopOOB || (mat[topCoords.Item1][topCoords.Item2] != 'E' && mat[topCoords.Item1][topCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, topCoords.Item1, topCoords.Item2);
var isBottomCaptured = isBottomOOB || (mat[bottomCoords.Item1][bottomCoords.Item2] != 'E' && mat[bottomCoords.Item1][bottomCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, bottomCoords.Item1, bottomCoords.Item2);
var isLeftCaptured = isLeftOOB || (mat[leftCoords.Item1][leftCoords.Item2] != 'E' && mat[leftCoords.Item1][leftCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, leftCoords.Item1, leftCoords.Item2);
var isRightCaptured = isRightOOB || (mat[rightCoords.Item1][rightCoords.Item2] != 'E' && mat[rightCoords.Item1][rightCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, rightCoords.Item1, rightCoords.Item2);

return isTopCaptured && isBottomCaptured && isLeftCaptured && isRightCaptured;
}

private static bool IsRowColumPairOutofBound(Matrix<char> mat, int row, int column)
{
if (row < 0)
{
return true;
}

if (row >= mat.NumRows)
{
return true;
}

if (column < 0)
{
return true;
}

if (column >= mat.NumCols)
{
return true;
}

return false;
}``````

}

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

``````#include "stdafx.h"

#include <assert.h>

using namespace std;

typedef enum
{
BLACK = 0,
WHITE,
OUT_OF_BOUNDS,
EMPTY
} STATE;

class Board
{
public:
Board()
{
board = nullptr;
checked = nullptr;
};
~Board()
{
if (board != nullptr)
{
delete board;
board = nullptr;
}

if (checked != nullptr)
{
delete checked;
checked = nullptr;
}
}

STATE getState(int x, int y)
{
int coord = (x - 1)*N + (y - 1);
if (x < 1 || y < 1 || x > N || y > N || coord > N*N)
return OUT_OF_BOUNDS;
return board[coord];
}

void setState(int x, int y, STATE s)
{
int coord = (x - 1)*N + (y - 1);
assert(coord < N*N);
board[coord] = s;
}

void init(int n)
{
N = n;
if (board != nullptr)
{
delete board;
board = nullptr;
}
if (checked != nullptr)
{
delete checked;
checked = nullptr;
}

assert(N >= 1);
board = new STATE[N*N];
checked = new bool[N*N];

for (int x = 1; x <= N; x++)
{
for (int y = 1; y <= N; y++)
{
setState(x, y, EMPTY);
}
}
}

bool isCaptured(int x, int y)
{
memset(checked, false, N*N*sizeof(bool));

bool ret = isCaptured(x, y, checked);

return ret;
}

private:
bool isCaptured(int x, int y, bool* checked)
{
STATE thisState = getState(x, y);
switch (thisState)
{
case WHITE:
case BLACK:
{
// return true if one adjacent is empty
// or if one adjacent 'same color' is not captured
STATE sT = getState(x-1 , y   );
STATE sR = getState(x   , y+1 );
STATE sL = getState(x   , y-1 );
STATE sB = getState(x+1 , y   );

if (sT == EMPTY ||
sR == EMPTY ||
sL == EMPTY ||
sB == EMPTY
)
return false;

assert((x-1)*N + (y-1) < N*N);
// mark this as checked so that we don't enter an infinite loop when testing for a neighbour
checked[(x-1)*N + (y-1)] = true;

if (sT == thisState && checked[(x-2) * N + (y-1)] == false && !isCaptured(x-1, y, checked))
return false;
if (sR == thisState && checked[(x-1) * N + y] == false && !isCaptured(x, y+1, checked))
return false;
if (sL == thisState && checked[(x-1) * N + (y-2)] == false && !isCaptured(x, y-1, checked))
return false;
if (sB == thisState && checked[x*N + (y-1)] == false && !isCaptured(x+1, y, checked))
return false;

return true;
}
break;
default:
break;
}
return false;
}

private:
int N;
STATE* board;
bool* checked;
};

void runAllTests()
{
// 1.
{
Board b;
b.init(1);
assert(b.getState(1, 1) == EMPTY);
}

// 2.
{
Board b;
b.init(2);  // 2x2, all black
for (int i = 1; i <= 2; i++)
{
for (int j = 1; j <= 2; j++)
{
b.setState(i, j, BLACK);
}
}
assert(b.getState(1, 1) == BLACK);
}

// 3.
{
Board b;
b.init(3);
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
b.setState(i, j, BLACK);
}
}
b.setState(2, 2, WHITE);

assert(b.isCaptured(2, 2) == true);
}

// 4.
{
Board b;
b.init(3);
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
b.setState(i, j, BLACK);
}
}
b.setState(2, 2, WHITE);
b.setState(2, 3, WHITE);

assert(b.isCaptured(2, 2) == true);
}

// 5
{
Board b;
b.init(2);
b.setState(1, 1, BLACK);
b.setState(1, 2, WHITE);
b.setState(2, 1, WHITE);

assert(b.isCaptured(1, 1) == true);
}

// 6
{
Board b;
b.init(5);
b.setState(2, 2, WHITE);
b.setState(2, 3, WHITE);
b.setState(2, 4, WHITE);
b.setState(3, 1, WHITE);
b.setState(3, 2, BLACK);
b.setState(3, 3, BLACK);
b.setState(3, 4, BLACK);
b.setState(4, 2, WHITE);
b.setState(4, 3, WHITE);
//b.setState(4, 4, WHITE);

assert(b.isCaptured(3, 2) == false);
assert(b.isCaptured(3, 3) == false);
}
}

int main()
{
runAllTests();
return 0;
}``````

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

Has anyone solved this problem in Java?

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

``````package com.company;

import java.util.HashSet;
import java.util.Set;

public class BoardGame {

// 1 - white
//2  - black
//0 - empty
//-1 out of boarder
private int[][] board;
int size;

private Set<String> examined = new HashSet<>();

public BoardGame(int size) {
this.size = size;
board = new int[size][size];
}

public boolean addWhite(int x, int y) {
if (x - 1 >= size || y - 1 >= size) {
return false;
}
board[y - 1][x - 1] = 1;
return true;
}

public boolean addBlack(int x, int y) {
if (x - 1 >= size || y - 1 >= size) {
return false;
}
board[y - 1][x - 1] = 2;
return true;
}

public boolean isBlocked(int x, int y) {
if (x - 1 >= size || y - 1 >= size) {
return false;
}
int current = getState(x, y);
if (current == 0) {
return false;
}
int opponent = current == 1 ? 0 : 1;
boolean lblocked =
getState(x - 1, y) == opponent || getState(x - 1, y) == -1 || (getState(x - 1, y) == current
&& neighbour(x - 1, y));
boolean rblocked =
getState(x + 1, y) == opponent || getState(x + 1, y) == -1 || (getState(x + 1, y) == current
&& neighbour(x + 1, y));
boolean ublocked =
getState(x, y + 1) == opponent || getState(x, y + 1) == -1 || (getState(x, y + 1) == current
&& neighbour(x, y + 1));
boolean dblocked =
getState(x, y - 1) == opponent || getState(x, y - 1) == -1 || (getState(x, y - 1) == current
&& neighbour(x, y - 1));
return lblocked && rblocked && ublocked && dblocked;
}

private boolean neighbour(int x, int y) {
if (examined.contains(x + ":" + y)) {
return true;
}
return isBlocked(x, y);
}

public int getState(int x, int y) {
if (x - 1 >= size || y - 1 >= size) {
return -1;
}
if (x - 1 < 0 || y - 1 < 0) {
return -1;
}
return board[y - 1][x - 1];
}

public static void main(String[] args) {
BoardGame boardGame = new BoardGame(2);
System.out.printf(String.valueOf(boardGame.isBlocked(1, 1)));

boardGame = new BoardGame(5);

System.out.printf(String.valueOf(boardGame.isBlocked(3, 2)));
}

}``````

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

``````public static boolean isTrapped(char[][] arr, int i, int j, int m, int n , boolean[][] visited) {
int[] xAxis = {-1,0,1,0};
int[] yAxis = {0,1,0,-1};
char sourceChar = arr[i][j];
visited[i][j] = true;
for (int k = 0; k < yAxis.length; k++) {
int x = i + xAxis[k];
int y = j + yAxis[k];
if(isValidMove(arr, x, y, m, n) && !visited[x][y]) {
if(arr[x][y] == sourceChar) {
boolean result = isTrapped(arr, x, y, m, n, visited);
if(result) {
return true;
}
}else if(arr[x][y] == ' ') {
return true;
}
}
}
return false;
}

private static boolean isValidMove(char[][] arr, int x, int y, int m, int n) {
return x >= 0 && y>=0 && x < m && y < n ;
}``````

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

``````public static boolean isTrapped(char[][] arr, int i, int j, int m, int n , boolean[][] visited) {
int[] xAxis = {-1,0,1,0};
int[] yAxis = {0,1,0,-1};
char sourceChar = arr[i][j];
visited[i][j] = true;
for (int k = 0; k < yAxis.length; k++) {
int x = i + xAxis[k];
int y = j + yAxis[k];
if(isValidMove(arr, x, y, m, n) && !visited[x][y]) {
if(arr[x][y] == sourceChar) {
boolean result = isTrapped(arr, x, y, m, n, visited);
if(result) {
return true;
}
}else if(arr[x][y] == ' ') {
return true;
}
}
}
return false;
}

private static boolean isValidMove(char[][] arr, int x, int y, int m, int n) {
return x >= 0 && y>=0 && x < m && y < n ;
}``````

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

``````enum square_state
{
BLACK,
WHITE,
EMPTY,
OUT_OF_BOUND
};

// Suppose board and visited are filled.
vector<vector<square_state>> board;
vector<vector<bool>> visited;

square_state getState(int x, int y)
{
if (x < 0 || x > 3 || y < 0 || y > 3)
return OUT_OF_BOUND;
return board[x][y];
}

bool is_captured(int x, int y)
{
queue<pair<int, int>> q;
q.emplace(x, y);
while (!q.empty())
{
auto cur_cell = q.front();
auto cur_cell_state = getState(cur_cell.first, cur_cell.second);
q.pop();

if (cur_cell_state == EMPTY || cur_cell_state == OUT_OF_BOUND)
return false;

auto up_cell = make_pair(cur_cell.first, cur_cell.second - 1);
auto up_cell_state = getState(up_cell.first, up_cell.second);
if (up_cell_state == EMPTY)
return false;
if (!visited[up_cell.first][up_cell.second] && cur_cell_state == up_cell_state)
q.emplace(up_cell);

auto down_cell = make_pair(cur_cell.first, cur_cell.second + 1);
auto down_cell_state = getState(down_cell.first, down_cell.second);
if (down_cell_state == EMPTY)
return false;
if (!visited[down_cell.first][down_cell.second] && cur_cell_state == down_cell_state)
q.emplace(down_cell);

auto left_cell = make_pair(cur_cell.first - 1, cur_cell.second);
auto left_cell_state = getState(left_cell.first, left_cell.second);
if (left_cell_state == EMPTY)
return false;
if (!visited[left_cell.first][left_cell.second] && cur_cell_state == left_cell_state)
q.emplace(left_cell);

auto right_cell = make_pair(cur_cell.first + 1, cur_cell.second);
auto right_cell_state = getState(right_cell.first, right_cell.second);
if (right_cell_state == EMPTY)
return false;
if (!visited[right_cell.first][right_cell.second] && cur_cell_state == right_cell_state)
q.emplace(right_cell);

visited[cur_cell.first][cur_cell.second] = true;
}

return true;
}``````

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

Java solution with BFS

``````import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class GoGame  {

public static boolean isSurrounded(int x, int y, char[][] board){
int[] root = new int[]{x-1,y-1};
char color = board[x-1][y-1];

List<int[]> queue = new ArrayList<int[]>();

int[][] visited = new int[board.length][board[0].length];

while(!queue.isEmpty()){
int[] cell = queue.remove(0);
int cellX = cell[0];
int cellY = cell[1];
if(visited[cellX][cellY]==1){
continue;
}
visited[cellX][cellY] = 1;

char cellColor = board[cellX][cellY];
if(isEmptyCell(cellColor)){
return false;
}
if(isSameColor(color, cellColor)){
List<int[]> neighbours = getNeighbours(cellX,cellY,board);
for(int i=0; i<neighbours.size();i++){
}
}
}

return true;
}

private static List<int[]> getNeighbours(int x, int y, char[][] board){
List<int[]> neighbours = new ArrayList<int[]>();

int[][] offset = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
for(int i=0; i<offset.length; i++){
int neighbourX = x + offset[i][0];
int neighbourY = y + offset[i][1];

if(neighbourX < 0 ||
neighbourY < 0 ||
neighbourX >= board.length ||
neighbourY >= board[0].length
){
continue;
}
}
return neighbours;
}

private static boolean isEmptyCell(char cell){
return cell == 'E';
}

private static boolean isSameColor(char cell1, char cell2){
return cell1 == cell2;
}

public static void main(String[] args){
char[][] board = new char[][]{
{'E','W','W','W','W','W','W'},
{'E','W','B','W','W','W','W'},
{'E','W','B','W','W','B','W'},
{'E','W','B','B','W','B','B'},
{'E','W','W','B','B','W','W'},
{'E','B','B','B','W','W','W'},
{'E','W','W','W','B','W','W'},
{'E','W','W','W','W','W','W'}

};
System.out.println(GoGame.isSurrounded(1,3,board));
System.out.println(GoGame.isSurrounded(4,4,board));
System.out.println(GoGame.isSurrounded(7,5,board));
System.out.println(GoGame.isSurrounded(4,6,board));
}
}``````

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

Java solution with BFS

``````import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class GoGame  {

public static boolean isSurrounded(int x, int y, char[][] board){
int[] root = new int[]{x-1,y-1};
char color = board[x-1][y-1];

List<int[]> queue = new ArrayList<int[]>();

int[][] visited = new int[board.length][board[0].length];

while(!queue.isEmpty()){
int[] cell = queue.remove(0);
int cellX = cell[0];
int cellY = cell[1];
if(visited[cellX][cellY]==1){
continue;
}
visited[cellX][cellY] = 1;

char cellColor = board[cellX][cellY];
if(isEmptyCell(cellColor)){
return false;
}
if(isSameColor(color, cellColor)){
List<int[]> neighbours = getNeighbours(cellX,cellY,board);
for(int i=0; i<neighbours.size();i++){
}
}
}

return true;
}

private static List<int[]> getNeighbours(int x, int y, char[][] board){
List<int[]> neighbours = new ArrayList<int[]>();

int[][] offset = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
for(int i=0; i<offset.length; i++){
int neighbourX = x + offset[i][0];
int neighbourY = y + offset[i][1];

if(neighbourX < 0 ||
neighbourY < 0 ||
neighbourX >= board.length ||
neighbourY >= board[0].length
){
continue;
}
}
return neighbours;
}

private static boolean isEmptyCell(char cell){
return cell == 'E';
}

private static boolean isSameColor(char cell1, char cell2){
return cell1 == cell2;
}

public static void main(String[] args){
char[][] board = new char[][]{
{'E','W','W','W','W','W','W'},
{'E','W','B','W','W','W','W'},
{'E','W','B','W','W','B','W'},
{'E','W','B','B','W','B','B'},
{'E','W','W','B','B','W','W'},
{'E','B','B','B','W','W','W'},
{'E','W','W','W','B','W','W'},
{'E','W','W','W','W','W','W'}

};
System.out.println(GoGame.isSurrounded(1,3,board));
System.out.println(GoGame.isSurrounded(4,4,board));
System.out.println(GoGame.isSurrounded(7,5,board));
System.out.println(GoGame.isSurrounded(4,6,board));
}
}``````

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

``````/**
* @author Omid Ghiasi Tarzi
*/
static boolean isCaptured(int x,int y){
Set<String> indexes=new HashSet<>();
String currentState=getState(x,y);
return isCaptured(x,y,currentState,indexes);
}

static boolean isCaptured(int x, int y, String desired, Set<String> indexes){
String current=getState(x,y);
if(current.equals("empty")){
return false;
}
if(!current.equals(desired)){
return true;
}
String index=x+","+y;
if(indexes.contains(index)){
return true;
}
return isCaptured(x-1,y,desired,indexes)&&
isCaptured(x+1,y,desired,indexes)&&
isCaptured(x,y-1,desired,indexes)&&
isCaptured(x,y+1,desired,indexes);
}``````

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

Solution in Python
{{
def _is_captured(base_color, r, c, R, C, arr, visited):
check_X_axis = [-1, 1, 0, 0]
check_Y_axis = [0, 0, -1, 1]
status = False
if visited[r][c] is True:
return False
visited[r][c] = True
for i in range(4):
l = check_X_axis[i]
m = check_Y_axis[i]
if r+l < R and r+l >= 0 and c+m < C and c+m >= 0:
if arr[r+l][c+m] == "E":
status = True
elif base_color != arr[r+l][c+m]:
status = False
else:
status = _is_captured(base_color, r+l, c+m, R, C, arr, visited)
if status:
return True
return False

def is_captured(r, c, arr):
R = len(arr)
C = len(arr[0])
visited = [[False]*C for r in range(R)]
color = arr[r][c]
return _is_captured(color, r , c, R, C, arr, visited)

arr = [["E", "W", "W", "W", "E"],
["W", "B", "B", "B", "W"],
["E", "W", "W", "W", "E"]]

is_captured(1, 2, arr)

}}

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

{{def _is_captured(base_color, r, c, R, C, arr, visited):
check_X_axis = [-1, 1, 0, 0]
check_Y_axis = [0, 0, -1, 1]
status = False
if visited[r][c] is True:
return False
visited[r][c] = True
for i in range(4):
l = check_X_axis[i]
m = check_Y_axis[i]
if r+l < R and r+l >= 0 and c+m < C and c+m >= 0:
if arr[r+l][c+m] == "E":
status = True
elif base_color != arr[r+l][c+m]:
status = False
else:
status = _is_captured(base_color, r+l, c+m, R, C, arr, visited)
if status:
return True
return False

def is_captured(r, c, arr):
R = len(arr)
C = len(arr[0])
visited = [[False]*C for r in range(R)]
color = arr[r][c]
return _is_captured(color, r , c, R, C, arr, visited)

arr = [["E", "W", "W", "W", "E"],
["W", "B", "B", "B", "W"],
["E", "W", "W", "W", "E"]]

is_captured(1, 2, arr) }}

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.

### 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.