Thursday, May 21, 2009

Adobe Interview question

Here's an interview question, apparently from Adobe, posted on the Joel On Software site.

Someone ("d" is his moniker) posted that this was NP-complete. I think in this case the problem is to come up with an imaginative heuristic solution that will sound good to the interviewer :)

Adobe Interview Question

You are given a plotter which can plot points provided to it in the form of 'x' and 'y' coordinates. The plotter hand can move horizontally or vertically only. Your program will be given a list of 'n' coordinates in the form of {(x1,y1), (x2,y2} ... (xn,yn)}. Your program must print a sorted list of all 'n' points that would represent the least cumulative distance for the plotter hand to plot all 'n' points in that sorted order.

No comments:

Post a Comment