Close

Checkers Interview Question: Moving a Piece

Using the previously modelled checkers board, we can now move pieces around the board. This part of the exercise uses some basic grid-movement logic, and error checking. It’s presented in two parts: a simple move and a jump. I expect candidates to finish both parts.

A function that moves a piece

Now that we have the board, it is possible to move a piece from one location to another. The requirements for the new function are:

  • A piece can move one space, horizontally, vertically, or diagonally — to one of the 8 adjacent spots
  • There must be a piece at the source location
  • The destination must be empty

I do not mention again that the locations have to be on the board. It’s an implied requirement now that we’re working on an established data model. Several candidates do not check this and write code that will fail. Those that wrote helper functions before typically don’t have to worry about it, since they already perform the checks.

Many candidates will duplicate the checks — redundant code is terrible. This is a great chance to see the candidate’s experience and approach to writing code. Do they notice the redundancy? Do they decide to write a new function to merge this code and the old check?

On occasion, and thankfully it’s rare, I encounter defensive people at this point. When I point out the redundant code, they’ll start ranting about why it’s okay. Show your positive side and graciously accept the criticism.

Code duplication can also happen with the function arguments. We’re referring repeatedly to board positions, so I’m expecting a type that encapsulates a location. Types are something candidates should be familiar with, regardless of the language. Even in in a weakly typed language, like JavaScript, they can still use a tuple or anonymous structure. I’ve seen that being comfortable creating logical data types is common among good coders.

def move_piece(self, from : Position, to : Position ):
	if not self.valid_location( from ) or not self.valid_location( to ):
		raise ValueError( Bad position )

Checking the move

Checking whether the move is one space away is the key part of the problem solving. Interviewees are diverse in their performance. Some walk right through this check without even pausing, others hit significant blocks, with a few even failing to come up with a solution on their own.

I often see tables of allowed moves created: an array listing all the relative positions that a piece can be moved to. This is combined with a for-loop that checks if the destination is any of those allowed pieces. It’s not a good solution, but, it is a solution. In an interview you want to always press forward, with whatever idea you have. This table based approach is better than no approach at all. I will review it with the candidate, point out the problems, and suggest an alternative.

Delta based comparisons are an easy answer. Delta values come up a lot while working on grids, maps, or anything with distances. And as grid-based questions are common in interviews, you should be familiar with the concept.

The code below takes the delta value for both x and y and checks if the move is a logical distance of 1.

dx = to.x - from.x
dy = to.y - from.y

valid_move = abs(dx) <= 1 and \
	abs(dy) <= 1 and \
	dx + dy != 0

That last bit, dx + dy != 0 is a bit of a trick to test the total distance. I’ve never seen a candidate use it. More likely is a negative comparison, and not (dx ==0 and dy == 0).

Adding a jump

With the basic move in place, I add another option. It’s possible to jump over another piece, moving a distance of two in any of the eight directions. The requirements are:

  • A jump is a move of two spaces in any of the eight directions from the current position
  • It is allowed only if there is a piece in between the current and target position
  • The move function should be changed to allow a jump

How candidates approach this change can reveal their habits. I appreciate when people create a whole new function and say they’ll figure out how to combine it with the previous one later. This allows them to think clearly and write code specific to the jump.

Others start with a delta test in the move code, and when a jump is detected write a whole new branch. This is logically similar to a new function. It saves a bit on overhead, but adds some complexity.

An unfortunate group of candidates attempts to hammer in these new requirements directly into the existing move code. It involves some complex conditions, odd variables, and usually plenty of errors. People taking this approach fare the worst. They are the least likely to solve the problem in time. It’s also difficult to give any partial credits, since until completed, neither the old behaviour, nor the new one works.

Isolating a problem is key to coding, not only in an interview, but in your daily work. Start with a clean separation and merge the code together afterwards. It’s how I do my coding. I don’t mind starting with a bit of redundancy, so long as I know I’m going to get rid of it.

I’ll leave the logic of testing a valid jump as an exercise for you. Think about the delta movement.

Extended Bit

The jump has extra requirements. I used to mention them immediately, but it added complexity without gaining more insight into the candidate’s abilities. Instead, I tack them on the end as a kind of cool down exercise.

  • If a piece jumps over a piece of the same colour, the existing piece remains
  • If a piece jumps over a piece of another colour, the other piece is removed

This is the core mechanism to a real checkers game. You want to remove the other player’s pieces.

Advanced Extensions

As with my card question, I like to have advanced requirements ready. A few candidates have plenty of time left after implementing the jump. Since they’ve already passed the basic interview, I don’t mind asking a difficult question.

  • Find a valid black move on the board

That is, write a function that returns a source and destination position that represent a valid move. Valid meaning the values could be passed to the move function.

I’ve never had somebody write this code. It’s too much and has lots of finagley details. Instead I’m satisfied with a verbal description of how the algorithm might work.

So far, one person has given me a good answer. One other person had a good idea, and though didn’t quite get it, appreciated the challenge.

Evaluating the candidate

I’ve created this interview challenge to evaluate candidates. The progression of requirements gives me insight into how the individual approaches their coding, and their weaknesses. The combination of data modelling and error handling gives the candidate a lot to think about, with no tricky requirements.

It’s the data modelling aspect that appears to make this harder than my card game question. The focus on the data structure, over logic flow, appears to be a weak point for a lot of candidates. Knowing this, it’s absolutely something I’d question all candidates on before hiring them. It’s an essential skill for programming.

Due to this challenge, I often reserve this question for screening candidates with more experience. While a junior should be able to do this, it usually requires more help, and we run out of time. Adapting my questions to the expectations of the candidate is important for interviewing, especially in the early stages.

I recommend you try writing this code. Pay attention to all the things mention. Ensure you can create custom types and know how to use them for arguments. Watch for redundant code and think about how to remove it. Learn about grid-based questions, as they come up often in interviews.

Edaqa Mortoray

An avid writer and expert programmer. He’s been on both sides of the interview table countless times and enjoys sharing his experiences. https://edaqa.com/