CodeFights Solves It: chessQueen

CodeFights Solves It: chessQueen

Our latest Interview Practice Task of the Week was chessQueen, which has been asked in technical interviews at Adobe. This question might seem fairly easy at first: Given the location of a queen piece on a standard 8 × 8 chess board, which spaces would be safe from being attacked by the queen? But as with any “easy” technical interview question, it’s imperative that you think it through fully, watch out for potential traps, and be able to explain your reasoning as you solve it!

This question is a variation on a classic problem, Eight Queens. It’s very possible that you’ve encountered Eight Queens or a common variation, nQueens, in computer science classes or interviews in the past. Chess-based problems like this one come up a lot in interviews, there’s a good reason for that! If you think about a chess board, what does it look like? A grid. And chess pieces follow specific rules, making chess scenarios a great framework for questions that test your basic problem-solving and implementation skills.

If you haven’t solved chessQueen yet, now’s the time! Once you’ve written your own solution, head back here. I’ll discuss my solution, and why I chose it over other possible solutions to the problem.

Ready? Great, let’s get started!

The technical interview problem

chessQueen gives us the location of the queen in standard chess notation (e.g. “d4”). Our solution needs to return a list of all the locations on the board that are safe from the queen. The diagram below shows the locations that the queen could move to on her next move, which means that these cells are not safe from the queen.

position of the queen in Adobe technical interview question
Queen at D4

In this example, we’d need to have our function chessQueen("d4") return the following list:

Keep in mind that the output above has been formatted nicely to help us visualize the solution when looking at the diagram. The native output would put line breaks at locations dictated by the size the window.

What can the queen attack?

Remember that in chess, a queen can move any number of squares vertically, horizontally, or diagonally.

The rows are already numbered, so let’s number the columns as well. Internally, we can think of column A as ‘0’, column B as ‘1’, etc. We will call the queen’s location (qx,qy). Then the queen can take any location (x,y) that is:

  1. Anything in the same row (i.e. qy == y)
  2. Anything in the same column (i.e. qx == x)
  3. Anything on the up-and-right diagonal from the queen’s location. (i.e. slope 1 lines though the queen’s location: qx - qy == x - y)
  4. Anything on the down-and right diagonal from the queen’s location. (i.e. slope -1 lines though the queen’s location: qx + qy == x + y)

Any other location on the board is safe from the queen.

Our strategy

We see that we have to report and return all the squares that are safe from the queen for our solution. If we think of the chess board as N × N, we see that there are N squares excluded from the row, N excluded from the column, and at most N excluded from each of the diagonals. We are expected to return O(N^2) elements, so we know that we aren’t going to find a solution shorter than O(N^2).

The creative parts of this solution will be how you choose to map between the column letters and the numbers – basically, how you do the arithmetic! My choice below was to use the hard-coded string "abcdefgh", where the position in the string maps to the index. I’ll mention some alternatives below, as well as their advantages and disadvantages.

Other approaches to this coding challenge

My approach to translating between the column’s names and the numbers won’t be everyone’s favorite way. My approach to listing the elements isn’t elegant, but it gets the job done! And a lot of times, that’s exactly that an interviewer needs to see.

Here are some alternatives, and why I didn’t choose them:

  • Using the built-in string library
    We can get rid of the hardcoded string by writing

You have to be a little careful that people running different locales will still have the same “first 8 characters” that you have! Note that you can use cols = list(string.ascii_lowercase[:8]) instead to be safe, but at that point I’d rather be explicit about the letters I’m using.

  • Using “ASCII math”
    We can find the column numbers by subtracting the character code a from the letter. In Python, ord('a') will return the code for the letter ‘a’ (97 in ASCII). In C, the function casting the character to an integer does the same thing. So we can actually write code that is a lot smaller:

Because we aren’t relying on the position in the list, and have a direct translation between the column letters and numbers, we’re able to remove the column directly, instead of having to use the continue keyword. I avoided this because I get nervous doing encoding math (what about the locales?!) but the Python documentation assures me I’d actually be fine!

  • Using a dictionary for the conversion
    If I wanted to be fully explicit, I could make a dictionary {'a':0,'b':1, ..., 'h':7} to encode the values, and a separate dictionary to decode. This is a very flexible approach, but I would worry about what my interviewer might read into me setting up two hash tables for something that really only needed a little arithmetic! This is probably the easiest version to internationalize, so if you have a technical interview at a company that works in many different character sets, you could use this flexible code as a selling point. (“Oh, you want the names of the columns in Chinese? No problem, I just have to change the keys in this dictionary…”)

Tell us…

As you’ve seen, this is a challenge that can be solved in a number of different ways! How did you tackle it? How would you describe your reasoning for taking that approach to an interviewer? Let us know over on the CodeFights forum!

Comments are closed.