Dropping Boxes with JavaFX

Dropping Boxes with JavaFX If you want to work for DropBox, they have an interesting programming test which solution must be submitted together with the CV. I’m not considering a position at DropBox, but their test was too fun to ignore: an interesting challenge in algorithms, and another opportunity to exercise JavaFX as any geometric problem surely deserves some GUI. (Don’t read this blog if you actually plan to apply for a job at DropBox.  I don’t think the company would use this problem as its single method of recruitment; this is more valuable for the candidate.) The problem is to find the ideal packing of some number of arbitrary “boxes” (rectangular objects), so the total are is minimized. The boxes can be rotated if necessary, and the area of the smaller rectangular area that contains all packed boxes is the solution. Like most geometric problems, this is easy to solve by sketching some empiric solution and pondering how to translate it to an algorithm. The first, somewhat obvious idea: Sorting the boxes: First place those with bigger areas, to avoid inefficient placement that could happen when trying to place large boxes on a very fragmented free space caused by smallish boxes. I don’t have a formal justification for this heuristic... it's just a reasonable analogy with similar fragmentation problems, from memory allocation to disk filesystems. Partitioning by size is usu...

Date: September, 03 2010
Url: http://www.java.net/blog/opinali/archive/2010/09/03/dropping-boxes-javafx

Others News