Компания Dropbox опубликовала головоломки для потенциальных кандидатов на работу. Свои решения для тестовых задач просьба высылать на jobs@dropbox.com. Как сказано на сайте, с авторами этих писем «нам есть о чём поговорить».
Первая задача — алгоритм двумерной упаковки объектов. Нужно разместить прямоугольники заданной длины и высоты на минимальной площади. На входе перечень объектов с указанием длины и ширины (целые числа), на выходе функция должна выдавать площадь минимального прямоугольника, куда они помещаются. Объекты можно поворачивать на 90°. Дополнительные бонусные очки выдаются за визуализацию средствами stderr.
Пример начальных условий:
Результат:
Визуализация (stderr):
Кстати, кое-кто уже попробовал решить эту задачу: см. результат. Другие идеи здесь (PDF).
Вторая задача — алгоритм обработки событий в файловой системе Dropbox. На входе вам дают список событий типа ADD/DEL с указанием времени UNIX, путём к файлу и хэшем контента. Нужно привести их в удобочитаемый вид на английском языке. Как сообщается, здесь нет идеального решения, зато существует несколько способов интерпретации. Судить будут по скорости работы алгоритма, красоте вывода, обработке неоднозначных событий и т.д. Пример ниже является корректным, но результат не выглядит user-friendly.
Пример начальных условий:
Результат:
Первая задача — алгоритм двумерной упаковки объектов. Нужно разместить прямоугольники заданной длины и высоты на минимальной площади. На входе перечень объектов с указанием длины и ширины (целые числа), на выходе функция должна выдавать площадь минимального прямоугольника, куда они помещаются. Объекты можно поворачивать на 90°. Дополнительные бонусные очки выдаются за визуализацию средствами stderr.
Пример начальных условий:
3 8 8 4 3 3 4
Результат:
88
Визуализация (stderr):
11x8: + - - - - - - + + - + | | | | | | | | | | + - + | | + - + | | | | | | | | + - - - - - - + + - + 8x11: + - - - - - - + | | | | | | | | | | | | + - - - - - - + + - - + + - - + | | | | + - - + + - - + 11x8: + - + + - - - - - - + | | | | | | | | + - + | | + - + | | | | | | | | | | + - + + - - - - - - + 8x11: + - - + + - - + | | | | + - - + + - - + + - - - - - - + | | | | | | | | | | | | + - - - - - - +
Кстати, кое-кто уже попробовал решить эту задачу: см. результат. Другие идеи здесь (PDF).
Вторая задача — алгоритм обработки событий в файловой системе Dropbox. На входе вам дают список событий типа ADD/DEL с указанием времени UNIX, путём к файлу и хэшем контента. Нужно привести их в удобочитаемый вид на английском языке. Как сообщается, здесь нет идеального решения, зато существует несколько способов интерпретации. Судить будут по скорости работы алгоритма, красоте вывода, обработке неоднозначных событий и т.д. Пример ниже является корректным, но результат не выглядит user-friendly.
Пример начальных условий:
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
Результат:
Added dir /test. Added file /test/1.txt. Renamed dir /test -> /test2.
