This question revolves around a Go board, and involves calculating the liberty of a given chain of go pieces.

From wikipedia, each chain has a degree of liberty the liberty of a chain is determined by the number of immediately adjacent empty squares. Diagonals are ignored.

These are the only rules needed to solve the question.

Approach 1:

Gather up the connected coordinates of the chain into a collection, and count the available neighbors for each. The downside being that certain free squares that were bordered by two or more peices of the chain would be counted more than once.

This problem could be elimnated by gathering all the available neighbors into a hashset, and then counting the number of members, but the interviewer asking the question insisted I solve the problem in a single pass.

My instincts were all overkill. In the end, the solution is easy to fit on a whiteboard.

I left out the Coordinate class definition. The interviewer suggested that, for time purposes, I didn't bother defining needed classes or types, unless they were especially complex. Coordinate in this case is just a container for an X,Y pair.

Click anywhere on the grid to choose a starting point, then step through the processing, or simply hit "PLAY"

uninitialized:not defined

uninitialized:null

uninitialized:null

uninitialized:null

uninitialized:null

uninitialized:null

uninitialized:not defined

uninitialized:null

public int getLiberty(int xPos, int yPos, int[,] board) { int retValue = 0; //bounds check: if (board == null || xPos < 0 || yPos < 0 || xPos >= board.GetLength(0) || yPos >= board.GetLength(1)) { return -1; //-1 signifies an invalid request, since 0 is a valid answer } int CurrentColor = board[xPos,yPos]; if (CurrentColor == 0) { return -1;//-1 signifies an invalid request, since 0 is a valid answer } bool[,] visited = new bool[board.GetLength(0), board.GetLength(1)]; Stack<Coordinate> stack = new Stack<Coordinate>(); stack.Push( new Coordinate(xPos, yPos)); Coordinate coords; while (stack.Count > 0) { coords = stack.Pop(); if(!visited[coords.x, coords.y]) { if (board[coords.x,coords.y] == 0) { retValue++; } else if (board[coords.x,coords.y] == CurrentColor) { //add all the neighbors to the party. if ((coords.x - 1) >= 0 && !visited[coords.x - 1, coords.y]) { stack.Push( new Coordinate( coords.x - 1, coords.y )); } if ((coords.x + 1) < board.GetLength(0) && !visited[coords.x + 1, coords.y]) { stack.Push(new Coordinate(coords.x + 1, coords.y)); } if ((coords.y - 1) >= 0 && !visited[coords.x, coords.y - 1]) { stack.Push(new Coordinate(coords.x , coords.y - 1)); } if ((coords.y + 1) < board.GetLength(1) && !visited[coords.x, coords.y + 1]) { stack.Push(new Coordinate(coords.x , coords.y + 1)); } } //mark current position as evaluated visited[coords.x, coords.y] = true; } } return retValue; }