4 ms·

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.

filkatron 13y ago
I totally agree with you. I'm taking a discrete mathematics course on college and we were asked to solve this.
VLM 13y ago
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.
- MartinCron 13y ago
  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.
- Crito 13y ago
  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.
  - waps 13y ago
    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.
- pedrosorio 13y ago
  "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#History 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."
- JoeAltmaier 13y ago
  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.
scriby 13y ago
I don't see anything fundamentally wrong with this programming question, except that it might be a little involved for a short interview. The purpose of this question isn't to tell you whether the candidate can program chess boards or not. It could be used to help find candidates who: * Have experience with search algorithms * Specifically have experience with backtracking solutions * Can reason through a complex problem (and communicate while doing so) * Paid attention in school / knowledge retention (for recent grads)
- georgemcbay 13y ago
  "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.
- djhworld 13y ago
  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.

filkatron 13y ago

I totally agree with you. I'm taking a discrete mathematics course on college and we were asked to solve this.

VLM 13y ago

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.

MartinCron 13y ago
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.
Crito 13y ago
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.
- waps 13y ago
  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.
pedrosorio 13y ago
"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#History 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."
JoeAltmaier 13y ago
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.

scriby 13y ago

I don't see anything fundamentally wrong with this programming question, except that it might be a little involved for a short interview. The purpose of this question isn't to tell you whether the candidate can program chess boards or not. It could be used to help find candidates who: * Have experience with search algorithms * Specifically have experience with backtracking solutions * Can reason through a complex problem (and communicate while doing so) * Paid attention in school / knowledge retention (for recent grads)

georgemcbay 13y ago
"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.
djhworld 13y ago
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.