The task for two-dimensional packaging from Dropbox
Dropbox has published puzzles for potential job candidates. Please send your solutions for test problems to jobs@dropbox.com. As stated on the site, with the authors of these letters "we have something to talk about."
The first task is an algorithm for two-dimensional packing of objects . You need to place the rectangles of a given length and height on a minimum area. At the entrance there is a list of objects with an indication of the length and width (integers); at the output, the function should produce the area of the minimum rectangle where they are placed. Objects can be rotated 90 °. Additional bonus points are awarded for visualization by means of stderr .
Example of initial conditions:
Result:
Visualization (stderr):
By the way, some people have already tried to solve this problem: see the result . Other ideas here ( pdf ).
The second task is an algorithm for handling events in the Dropbox file system. At the entrance you are given a list of events like ADD / DEL with indication of UNIX time, the path to the file and the content hash. You need to bring them into a readable form in English. As reported, there is no perfect solution, but there are several ways of interpretation. They will be judged by the speed of the algorithm, the beauty of the output, the processing of ambiguous events, etc. The example below is correct, but the result does not look user-friendly.
')
Example of initial conditions:
Result:
The first task is an algorithm for two-dimensional packing of objects . You need to place the rectangles of a given length and height on a minimum area. At the entrance there is a list of objects with an indication of the length and width (integers); at the output, the function should produce the area of the minimum rectangle where they are placed. Objects can be rotated 90 °. Additional bonus points are awarded for visualization by means of stderr .
Example of initial conditions:
3 8 8 4 3 3 4
Result:
88
Visualization (stderr):
11x8: + - - - - - - + + - + | | | | | | | | | | + - + | | + - + | | | | | | | | + - - - - - - + + - + 8x11: + - - - - - - + | | | | | | | | | | | | + - - - - - - + + - - + + - - + | | | | + - - + + - - + 11x8: + - + + - - - - - - + | | | | | | | | + - + | | + - + | | | | | | | | | | + - + + - - - - - - + 8x11: + - - + + - - + | | | | + - - + + - - + + - - - - - - + | | | | | | | | | | | | + - - - - - - +
By the way, some people have already tried to solve this problem: see the result . Other ideas here ( pdf ).
The second task is an algorithm for handling events in the Dropbox file system. At the entrance you are given a list of events like ADD / DEL with indication of UNIX time, the path to the file and the content hash. You need to bring them into a readable form in English. As reported, there is no perfect solution, but there are several ways of interpretation. They will be judged by the speed of the algorithm, the beauty of the output, the processing of ambiguous events, etc. The example below is correct, but the result does not look user-friendly.
')
Example of initial conditions:
6 ADD 1282352346 / test - ADD 1282353016 /test/1.txt f2fa762f DEL 1282354012 / test - DEL 1282354012 /test/1.txt f2fa762f ADD 1282354013 / test2 - ADD 1282354013 /test2/1.txt f2fa762f
Result:
Added dir / test. Added file /test/1.txt. Renamed dir / test -> / test2.
Source: https://habr.com/ru/post/104282/
All Articles