One more reason why this is terrible question: many people solved it in the past as part of a programming course, many didn't. If you want to test which school they went to you can look at the resume. If you want to see how they handle writing solvers for simple games/puzzles under pressure of the interview come up with one that is guaranteed (or almost) to be new for the interviewee.
> I do have to say that as someone who sometimes conducts technical interviews, I'm not sure I would actually give this question to an interviewee, unless I was leaving him or her alone to work for a couple of hours, because of how long it would probably take to reach an answer
It can actually be done fairly quickly if you really only ask for 8x8 instead of a general NxN solver, and the person realizes one key thing: computers have gotten ridiculously fast, so that if you just bang out the first dumb thing that comes to mind, you can probably be done and have the answers before the people with the clever, general, efficient solutions get their solutions coded or even designed.
For instance, this brute force, ridiculously ugly, un-clever, only-works-for-8x8 solution took about 5 minutes or so to write, with half that spent deciding how to number the diagonals and looking at a couple of squares on a chessboard to see how rank/file maps to my diagonal numbering:
#include <stdio.h>
int main(void)
{
unsigned long pos;
for (pos = 0; pos <= 077777777; ++pos)
{
unsigned long tmppos = pos;
unsigned long taken = 0;
int rank;
int file;
for (file = 0; file < 8; ++file)
{
unsigned long mask;
rank = tmppos & 07;
mask = (1L << file) | /* file */
(1L << (rank + 8)) | /* rank */
(1L << (23 + file - rank)) /* diagonal */
| (1L << (45 - file - rank)); /* other diagonal */
if (taken & mask)
goto fail;
taken |= mask;
tmppos >>= 3;
}
printf("%lo\n", pos);
fail: ;
}
return 0;
}
It takes under 0.5 seconds on my 2009 Mac Pro when compiled without optimization, and about half that with optimization.
(To be completely honest, I rarely write C nowadays, so although it only took a few minutes to write, the damn thing took half an hour to debug. I wrote "1 <<" instead of "1L <<" because I thought for some reason that int was 64 bit nowadays).
Not sure if you're aware of this, but the technique of representing a chess board as a 64-bit bitmap is in fact the method used by pretty much all chess engines these days. These 64-bit unsigned long longs are known as "bitboards".
Never had a job where programming chess boards was a requirement. So unless you have one don't ask this. It's not a programming question it's a puzzle.
That's the unfortunate part of it. You could have an interesting conversation about strategy. Its an interesting puzzle because the ultimate crude brute force implementation, if my math estimates are correct, is a "couple day" project for a "several hundred" sized parallel cluster, but a slightly smarter algo would be much quicker. There's only 64!/56! possible board configs for 8 pieces ignoring symmetry speedups, and a couple 1E9/second class machines would only take a couple hundred machine*days.
The funniest thing about puzzle interviews as an observer is I can't stop thinking ... "and if he gets the job he's going to spend 12 hour days writing a boring frameworked CRUD app" ... "this poor noob probably thinks real on the job programming is like solving chessboard puzzles all day long LOL".
The unfortunate part about the abstract puzzle fad is almost no one is paid to solve abstract puzzles but no one is tested on real puzzles. "Yes I know quite well traveling salesman is infeasible for 48 states, I'm asking you to solve it for 5 sites because we only have 5 warehouses" etc.
"Yes I know quite well traveling salesman is infeasible for 48 states, I'm asking you to solve it for 5 sites because we only have 5 warehouses"
http://en.wikipedia.org/wiki/Travelling_salesman_problem#His...
"In 2006, Cook and others computed an optimal tour through an 85,900-city instance given by a microchip layout problem, currently the largest solved TSPLIB instance. For many other instances with millions of cities, solutions can be found that are guaranteed to be within 2-3% of an optimal tour."
The unfortunate part about the abstract puzzle fad is almost no one is paid to solve abstract puzzles but no one is tested on real puzzles.
Once you're discussing real things, they aren't puzzles anymore. One of my favorite things to do in interviews is to just actually have a discussion, as peers, about a real-world technical problem with multiple potential tradeoffs and no one right answer.
Because there is such a straightforward though intractable brute force solution, but several straightforward improvements that can be made on it, I think this is actually a fairly reasonable interview question.
If they can't get the naive brute force solution in a few minutes, that indicates something pretty bad. If they treat it as a permutation question and get the n! brute force answer, that is much better (and is still something that can be done in about the same amount of time. If you treat the problem as numbered permutations then checking for diagonals even becomes non-tedious, making it easier to write out on a whiteboard than the naive brute force solution).
If they get a proper solution in only a few minutes, you know that they either have their act together, or that they have seen the problem before and remember the solution. That in itself is a good indicator, though if they get a proper solution right away there should be some follow-up questions to get a handle on how exactly they were able to solve it that quickly.
Plus even if they know the solution, that proves practical knowledge of search strategies (having coded at least 1). Even if it only proves you know the naive one, that's good.
Real world problems just aren't practical in interviews, you'll never get to the point where their programming chops are really being tested.
Lots of programming problems are puzzles. They just have so much context, you can't describe them quickly in an interview situation. So you use simple games instead. Its fair, its a reasonable way to get at algorithm, you can tell if the interviewee is used to thinking about the fundamental problem instead of lost in the APIs.
"Can reason through a complex problem (and communicate while doing so)"
This was a real problem for me as a programmer early in my career and a source of great anxiety on interviews. I've gotten better at it later in life almost solely because I needed to do so for interviewing purposes, but to be honest, I don't think it is a real world problem if someone isn't great at simultaneously reasoning through a complex problem and communicating while doing so. I suspect there is a large group of people like me who are very experienced and knowledgeable programmers who may come off poorly in whiteboard-coding interviews because actively focusing on complex problems makes it difficult for them to interact in the real world.
I do think being able to communicate is key for developers, but even when I had issues with this I could very clearly communicate how I went about solving the complex problem after I had finished it (or at least was convinced I was on the right track with one or two solutions and my mind wasn't running through the problem on dozens of different threads anymore) and it never impacted any real world collaboration because it is extremely rare that you ever sit around with a bunch of other programmers trying to reason through exactly the same algorithm at the same time, and even when that does happen, IME it is better to just get a few independent solutions and then communicate about the pros and cons of each rather than just "brainstorm" in real-time.
I would totally understand this question if you're interviewing for say, someone programming AI in games or other things where AI is required, as these sorts of problems tend to crop up quite regurly.
However, I'd be pissed off if the job turns out to be like 99% of most jobs, writing boring CRUD enterprise apps.
I did this in about 20 minutes in Python in an interview.
The trick to solving things fast is to use the structure of the problem to make your problem solving procedure less general. That is, you do premature optimization, except instead of trading readability for runtime speed, your are trading readability for program length.
With real problems, there is a similar tradeoff, so I think this is a useful skill to demonstrate. But it does take practice to find the tradeoff that works best for interview questions, which is not the same as for real life coding.
In my solution, I use mutable state to reduce the amount of code. board is mutated to avoid the boilerplate of copying objects. valid is mutated as a kind of optimization, but the real reason is it makes the program simpler.
def complete_board(board, l):
"""If possible, completes a board (whose first l rows
have been filled with 1 queen per row). Returns
true if this is possible, false otherwise
board is a list of ints representing the position
(0-based) of each queen"""
N = len(board)
if l == N:
return True
# determine the valid positions for a queen in the r'th row
valid = [True] * N
for row, col in enumerate(board[:l]):
valid[col] = False
s = l - row
if col + s < N:
valid[col + s] = False
if col - s >= 0:
valid[col - s] = False
for col, v in enumerate(valid):
if v:
board[l] = col
if complete_board(board, l + 1):
return True
return False
This question seems totally unreasonable for the length of any technical interview I have taken or conducted. Most interviews run under an hour and focus on multiple topics. Its rare you can focus on one question more than 10 minutes. The rule of thumb I use is that if I'm picking a question as an interviewer, I make sure I can answer that question in 1/3 the time I plan to give to the candidate. Given the pressure that they are under, I expect to owe that that much.
I do have to say that as someone who sometimes conducts technical interviews, I'm not sure I would actually give this question to an interviewee, unless I was leaving him or her alone to work for a couple of hours, because of how long it would probably take to reach an answer.
So it appears they are aware of that problem. I'm of the opinion that some "non-classical" problem is probably a better indication of skill and reasoning. Work through a known problem you had at work (which the candidate is hopefully not too familiar with, otherwise abort and try another), and see how they reason out the problem, then ask for some code that might fix it.
Agreed. However simplified variants on problems like these are actually really effective interview questions. A few years ago, I was asked to solve the N-Rook-Kings (pieces that attack like kings and rooks at the same time) problem, for 1 < N < 16, in half an hour.
The catch was that I had to only count the solutions, not find them. The very inexperienced engineer that I was, wrote a highly-optimized (bit boards) solution that could solve N=12 in 6 seconds. But I got this solution after the fact, and it took me hours to write it. A more qualified software engineer would have found a proper combinatorial solution in minutes.
In general, giving an actual NP-Complete problem in an interview question and expecting a good solution is unrealistic. However hiding an easy problem in a hard-looking one seems pretty effective.
I don't think it would be too difficult to find a candidate who could at least talk through or whiteboard out an imperative solution to this. If a candidate couldn't come up with at least an outline of a solution, I probably wouldn't want to hire them.
This particular problem lends itself really well to functional or constraint logic solutions, though (e.g. http://www.cs.nott.ac.uk/~rxq/files/8nQueenModel.pdf) -- I'd give bonus points to a candidate who could identify that this problem is well suited to one of those toolsets instead of immediately whipping out ruby, python, or js.
I'd give bonus points for pointing out some implementation decisions:
-when searching is it better to use copy-make or move/undo approach ? (copy make is faster on modern pc's, at least for things like 8Q's, it's also much easier to implement as you don't need any code for undoing moves)
-what is the best way to check if given move (placing the queen) is valid ? (you need three 0-1 arrays for rows and diagonals in both direction this a neat trick, very difficult to come up with but which speeds the whole thing immensely)
-how do you break out of the recursion if the task is changed to find one solution ?
I know all those things because I am a hobbyist who wrote a lot of solvers and dabbled into chess programming. I am probably in top 0.1% of people if I get question like this. I am incompetent when it comes to things needed in most commercial applications as I've never worked on big commercial projects.
This question filters for people like me. I can't imagine how this a good thing for anything practical (unless the task is to produce the best chess program or something).
1)having only one board and make/undo moves on it. So every time you put a new queen on the board you add it to the representation of the board and every time you go back in recursion you need to do an undo before exiting the function (so you new branch won't have queens placed on the board from previous branch)
2)storing as many boards as many steps deep in the recursion you are (max 8 in 8 queens problem) so every time you go deeper into recursion you create new board then you copy current state there and then you make a move (place a queen) on this new board; this way when you go back in recursion you do nothing as this new board is taken care of by stack pointer going back.
The cost of copy make is memory (you need memory for new board representation for every step deeper into recursion) but it's usually not much of a problem. The benefit is that you don't need to code undo logic (which in case of some games is quite complicated) and undo is much faster which usually outweights costs of copying the memory.
Some top chess programs are move/undo and some are copy/make, chess board representation usually takes about 200 bytes and variations may go as deep as 100 half moves which means you may need like 20kb additional memory for every thread doing searching. In case of 8 queens it's of course trivial though.
Some more information (for chess, so way more advanced):
> I do have to say that as someone who sometimes conducts technical interviews, I'm not sure I would actually give this question to an interviewee, unless I was leaving him or her alone to work for a couple of hours, because of how long it would probably take to reach an answer.
This is a great point that I realized that when I sat down to write up a solution myself. The video-explanation-version of coding it up for the CFI course ended up being 60 minutes long.
Suspect when it does get asked in an interview context they might only want to see some of your problem solving process and algorithm devising, not a full code-up.
This programming problem was what actually got me interested in compilers in the first place.
When I was 16 and learning how to program in Java, there was an online competition for high schoolers, and this was one of the introductory programming questions. Your program had to execute in under a time limit (5 seconds, N=13), and I had come up with the best solution I could and was still at 7 seconds. It took me the rest of the month spending hours a day reading on speed optimizations in order to cut down every unnecessary instruction, and remove every intermediate variable. Eventually, the program executed in 4.9 seconds.
While quite interesting, the problem only took an afternoon to implement the algorithm. What differentiated my chops from my competitors was that I could improve my program beyond the first implementation.
it is sort of confusing... do you really consider it a hard problem? I am first year maths student at Uni Warsaw and we literally had this problem in the first month, and solution was found by most people in just a few minutes. It sometimes amazes me how people here at HN find some hard for me problems easy and vice versa
Frankly i've been programming for a few years i would not be able to solve the problem in 20 mins. Maybe in 3/4 hours but 20 mins no way. I could come with an idea to solve it though.
But that's a very good exercice.
> I am first year maths student at Uni Warsaw
then Math is your major discipline. Please write down how you would express the solution in a pure mathematical form.
You might be surprised at how many people show up to a developer interview and are unable to have an intelligent conversation about the problem, let alone solve it. This is a weedout question, that's all.
Bear in mind that the objective isn't to weed out people who can't solve it. There are plenty of people who are fine coders who wouldn't quickly hit the solution for any number of reasons, including nervousness. The objective is to weed out the charlatans and amateurs who managed to get past the HR resume filter, so that as little time as possible is wasted.
Given function that checks if given string is a word accepted by the game or a sorted good words list, I think I would be able to. It's a very similar algorithm to queens problem. I'll try doing this and tell you!
Back in grad school, I took a configurable computing course where we were to solve the N-Queens problem on an FPGA. My short write-ups are here: http://people.cs.vt.edu/~scschnei/ece5530/
This was a computer engineering course, and I was a computer science student with no background in Verilog or VHDL. I think it took me about 30 hours to get a working solution. However, my solution is very limited, and shows how unfamiliar I was with thinking in hardware terms; other students in the course produced solutions which did not have my limitations, and they did it with much less effort. When I mentioned that to another student in the course, he looked surprised. When I mentioned I was a CS student with no prior experience with FPGAs, Verilog or VHDL, he said, oh, that's pretty good!
Here is a solution I wrote when I was an undergrad TA that uses only bit arrays and can check for a valid solution using bitwise logic operations. That said what a horrible interview question. The hard part about the problem is figuring out how to convert a x/y position on the board to a diagonal dx/dy coordinate. Once you figure that out the coding is simple but I remember it taking me a day of mulling over in the back of my head before the solution came to me in my sleep.
If I got that question, I'd probably spend most of my time worrying about whether or not I should count solutions that are rotations/reflections of other solutions as unique.
A quick solution involves starting at a corner, and placing each queen one horizontal and two vertical (a constrained knight's move, basically) away from the previous one. This works for an 8x8 board, but does not generalize to an NxN board (it is easy to see that this won't work when N is divisible by 3). Determining which N's it exactly works for is a math, not a programming puzzle, however. :)
If I took this as a "Question to prepare yourself for an interview" and not a "Question you might be asked during an interview" I think it's great.
As prep it's a concise problem you can do on your own time to get your brain working over basic things that you may not have been thinking about lately.
As a question to actually give someone (or receive) during an interview? Seems way to long.
I work with someone whose go-to question is the 8 Queens problem. I think it's an interesting exercise, but like you said it's quite long - can easily consume most of the interview. It's also very poorly aligned with the kind of work we do and code we write (for example, I can't think of a single place in our code using recursion) and so I'm not a fan of it as part of an interview.
Right! I did that solution in response to a Byte magazine contest years ago. It ran in 20 minutes in Basic on an HP2000.
The tricky part is permuting the array. I used a recursive swap routine, swapping to the right and testing if the array were valid to the left of i then recursing i+1. If it fails you don't have to recurse, you can pop, trimming the search tree drastically. There were 8 or 9 solutions if I remember right, less if you eliminate rotations and mirrors.
{edit: 12 solutions}
I really don't understand writing a program to solve this problem. Granted I play chess casually but I had a solution before I even finished reading the problem.
I think it's an interesting puzzle, but I don't think that makes it a good interview question.
Then, given any particular NxN board with M queens in first M columns that is a solution to M-queens, we can generate the list of possible new boards with (M+1) queens. We try all possible row positions for the new column excepting the rows where queens already exist.
attempts :: Int -> Board -> [Board]
attempts n (Board queens) =
map (\r -> Board (r : queens)) ([0 .. n - 1] \\ queens)
And we prune out the ones where the new queen has a diagonal conflict.
valid :: Board -> Bool
valid (Board []) = True
valid (Board (q:cols)) =
and $ map (\(n, c) -> abs (q - c) /= n) (zip [1..] cols)
-- this is a bit clever, as we walk back through
-- the previous columns, if the absolute difference
-- between the row position of the new queen and
-- an old queen is ever the count of the column
-- we're in, then it must be in a diagonal line
-- from the new queen
All of the above is pretty standard, but the fun part is using the list monad to structure a search. Each bind (<-) in do-notation can be thought of as non-deterministically setting a particular choice from the right side to the name on the left
queens :: Int -> [Board]
queens n = search n [emptySolution] where
search 0 boards = boards -- no more queens to add
search k boards = do
board <- search (k - 1) boards -- find a smaller solution
filter valid (attempts board) -- try all possible extensions,
-- remove the bad ones
>>> length (queens 8)
92
Finally, the pattern of `search` is really common, it's just iterating the generation of attempted solutions. We can write it with the built-in function `Control.Monad.foldM` or another common utility combinator, `iterateM`
iterateM :: Monad m => (a -> m a) -> a -> [m a]
iterateM f x = iterate (f =<<) (return x)
queens n = iterateM (filter valid . attempts n) emptySolution !! n
Finally, it's worth noting that there's nothing special about the list monad's implementation. It's easy to rewrite it without using the typeclass.
-- this is the list monad definition
instance Monad [] where
return a = [a]
xs >>= f = concat (map f xs)
iterateList :: (a -> [a]) -> a -> [[a]]
iterateList f x = iterate (concat . map f) [x]
How I'd approach it by hand, demonstrated on a 4x4 grid (other
than 1x1, smallest grid with a solution).
I'll go column by column, noting symmetry that also means I only
need to check half the rows for the first queen, and with
symmetry and the squares she eliminates I'll have fewer options
to consider on each subsequent column.
+---+---+---+---+
| Q | X | X | X |
+---+---+---+---+
| | X | | |
+---+---+---+---+
| | | X | |
+---+---+---+---+
| | | | X |
+---+---+---+---+
First queen placed, add the second we only have two options so
I'll try the top one.
+---+---+---+---+
| Q | X | X | X |
+---+---+---+---+
| | X | X | |
+---+---+---+---+
| | Q | X | X |
+---+---+---+---+
| | | X | X |
+---+---+---+---+
Oops, gotta move the second queen:
+---+---+---+---+
| Q | X | X | X |
+---+---+---+---+
| | X | Q | X |
+---+---+---+---+
| | | X | X |
+---+---+---+---+
| | Q | X | X |
+---+---+---+---+
Uh oh, can't place the 4th. Moving the first queen since we've
exhausted all placements of the 3rd and 2nd queen with the 1st in
the upper corner.
+---+---+---+---+
| | X | | |
+---+---+---+---+
| Q | X | X | X |
+---+---+---+---+
| | X | | |
+---+---+---+---+
| | | X | |
+---+---+---+---+
+---+---+---+---+
| | X | Q | X |
+---+---+---+---+
| Q | X | X | X |
+---+---+---+---+
| | X | X | Q |
+---+---+---+---+
| | Q | X | X |
+---+---+---+---+
I placed the remainder at once because there was only one legal
placement in each column.
Extending this approach to 8x8 isn't difficult if the challenge is merely to find a solution.
EDIT: I found it in 3 attempts on the 8x8. Going to the column with the most constraints (fewest options) to minimize my branching.
Each row must have a queen, and each row must have the queen in a different position. Therefore there are 8 rows and we just need to find a correct permutation of them.
Number each row 0 through 7. Generate permutations of these numbers.
To check for diagonal collisions between permutation indices x and y: abs(perm[x]-perm[y]) == abs(x-y)
(In other words, if rows 2 and 4 cannot be two places apart, rows 6 and 7 cannot be one place apart.)
Check for diagonal collisions as you're writing out possible valid permutations by hand. Doesn't take long to generate solutions since you don't have to actually draw or mentally picture a board to work out diagonal collisions. You just need to keep 8 single digit numbers in your head.
queens n = foldM (\y _ -> [ x : y | x <- [1..n], safe x y 1]) [] [1..n]
safe x [] n = True
safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]
import Control.Monad
queens n = foldM (\y _ -> [ x : y | x <- [1..n], safe x y 1]) [] [1..n]
safe x [] n = True
safe x (c:y) n = and [ x /= c, x /= c + n, x /= c - n, safe x y (n+1)]
main = mapM_ print $ queens 8
Hm. And maybe that's why Haskell isn't catching on. That looks little better than terminal scripting languages. Its concise, sure. But maybe that's not as helpful as you might think, in communicating a problem solution.
But you're right, examples like this are extremely poor marketing for Haskell. It's really not how you'd write most Haskell programs. A lot of the Haskell code on sites like Rosetta Code is deliberately terse to show off.
I changed the indentation a little bit, to make it more clear:
queens n = foldM
(\y _ -> [x:y | x <- [1..n], safe x y 1])
[]
[1..n]
safe x [] n = True
safe x (c:y) n = and [ x /= c
, x /= c + n
, x /= c - n
, safe x y (n+1)
]
main = mapM_ print $ queens 8
'queens' is essentially a for loop that concatenates the elements between 1..n that are safe, and 'safe' is a function that returns true if it's given an empty list, or if the input satisfies all of the predicates in the other list (notice the recursion that's possible because of laziness.) The function 'and' that it calls takes a list of bools and returns true if all of them are true. 'main' prints each list that results from running 'queens 8'
There is some syntax and convention you have to learn, e.g. what the _ in mapM_ means, what a list comprehension is, or what : means, etc. but once you have it's a fairly elegant solution (compare to the code snippets from imperative languages.)
thanks for the link , it's great , by the way i would buy a book that gather algorithms like that in any 'major' programming language (Java,C,C++, C#, Ruby, Python, javascript,whatever...) with a little explanation note for each algorithm.
