4 ms·
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
by 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 agoThe 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 agoBecause 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 agoPlus 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 agoLots 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.