One of my standard interview questions is writing a simplified game of checkers. I focus on the data modelling as required for a few basic operations. Many candidates are not prepared for this question, with a failure rate much higher than I expected. I base the requirements on real-world activities, thus there is no reason you shouldn’t be able to complete it.
Let me take you through the question, step-by-step as I present it in the interview. I’ll mention some common issues I see candidates having, and errors they make in the interview. Get some additional coding practice by following along.
Add pieces to a board
I start with a bit of a preamble about what I’m looking for. This first part of this question focuses on data modelling: how will we represent the checkers game and its pieces. I’m not looking for a complete program and care little about minor syntax errors. I’ll be reviewing it visually only.
- The game is played on an 8x8 grid
- Each cell can be empty, or contain a red or black piece
Given that, I ask the interviewee to create a function to place pieces.
- Create a function that takes a list of pieces, and their locations, and adds them to a board. For example, red at 4,5, or black at 3,7.
- It is an error to place a piece on top of an existing one
- It is an error to place a piece outside of the board
- If there are any errors, the function should fail and the board left unmodified
Board and piece model
I give all these point at once, but the difficulty starts with the first one. I’m expecting the candidate to create an appropriate data model for the board and pieces. The most logical solution is to use a matrix, or multi-dimensional array, depending on what your preferred language supports. There’s no excuse for not knowing these data structures.
Piece representation is where individuals diverge. The preferred approach is an enumeration, or another limited data type. Whenever you have a limited number of options, it’s cleanest to express those options distinctly. Here your enumeration will have Empty, Red and Black values. The enumeration represents the state of each cell.
Another valid approach is using only a Red and Black enumeration with an optional type for each board cell. The enumeration itself is only for the piece, and the cell state is a compound type.
Yet, the most common approach I get is using integer values. Each cell’s state is represented by an integer. There are two significant problems with this approach:
- The board could be corrupt, since a cell can have a nonsense number
- The code is hard to read as there’s no meaning to these numbers
A goal to stable programming is to never have invalid states. Choosing data types that block corruption helps. The readability is also important. With an enumeration you have clean names used throughout the code, like Empty. With integers I see a lot of magical comparisons to 0 or 1.
Some individuals use integers and define constants, essentially an enumeration without special syntax. It’s better than plain integers, but why not use an enumeration? If your language doesn’t any built-in enumeration syntax, you don’t have a choice.
A few candidates had difficulty completing this part. Roughly half of the candidates need help in representing the board and pieces. Note, if they’ve chosen the integer approach I won’t stop them, instead pointing out problems with it later.
Error checking
Candidates who struggle with the modelling tend to forget the error checking. About half require some prompting to add in checks.
The requirements for error checking are simple, at quick glance. Don’t place a piece over an existing one and don’t allow pieces outside of the board. It gives the candidate a good opportunity to demonstrate their clean coding ability.
Take a look at this typical fragment I get.
def place_pieces( self, places)
for place in places:
if place.position.x < 0 or place.position.x > 7 or place.position.y < 0 or place.position.y > 7:
raise ValueError( "location not on board" )
if board[place.position.x][place.position.y] != 0:
raise ValueError( "position already occupied" )
board[place.position.x][place.position.y] = place.piece
Note the != 0 that typifies models using integers, which is but one of the problems with that code. The code has some magic numbers, and at a glance you can’t tell what it’s doing. The clean solution is to make a helper function for the first part, and use an enumeration for the second. A few candidates did this on their first pass.
def position_in_board(self, position ):
return position.x >= 0 and position.x < self.width and
position.y >= 0 and position.y < self.height
def get_cell(self, position):
return self.board[position.x][position.y]
def place_pieces( self, places)
for place in places:
if not position_in_board( place.position ):
raise ValueError( "location not on board" )
if board.get_cell( place.position ) != CellStatus.Empty:
raise ValueError( "position already occupied" )
This reads much better.
Is it worth the effort in an interview? Yes, absolutely. If you’re in a habit of writing code this way it shouldn’t take any additional time. This code clearly communicates with the interviewer. I don’t have to ask questions about the conditional logic, the names tell all. Candidates who code this way do better overall, making it interesting for the interviewer’s evaluation.
Total error checking
What virtually all candidates miss is the requirement not to change anything if any of the items are invalid. For example, if the third piece is in an invalid location, the board should not be modified. Yet, if you do the typical loops above, you’ll have already changed the board at this point.
When pointed out, most candidates will then create a second loop to check for errors first. Yet the second loop doesn’t work, completely. If the input list contains multiple pieces in the same location, the initial loop won’t detect the error. It’s not until you place the pieces you notice the duplicate.
A good solution here is using a cloned board. Stick with the straight-forward initial loops, and if everything is okay, swap the boards out. It’s a common approach.
I don’t judge anybody negatively who doesn’t get this aspect of the question. It is something that comes up in daily coding, and it represents a good practice, but it’s easy to miss without somebody reviewing the code. It does however give experienced candidates a chance to earn bonus points. Otherwise I use it as a teaching opportunity.
Moving a piece
In the second part we will move a checkers piece on the board.
Top comments (0)