Clever Geek Handbook

Dropboxの2次元パッケージングの課題

Dropboxは、潜在的な求職者向けのパズルを公​​開しています 。 テストの問題に対する解決策をjobs@dropbox.comに送信してください。 サイトに記載されているように、これらの手紙の著者とともに、「私たちは何か話すことがあります」



最初のタスクは、 オブジェクトの2次元パッキングのアルゴリズムです 。 指定された長さと高さの長方形を最小領域に配置する必要があります。 入力では、長さと幅（整数）を示すオブジェクトのリスト、出力では、関数はそれらが配置される最小の長方形の領域を与える必要があります。 オブジェクトは90度回転できます。 追加のボーナスポイントは、 stderrツールを使用した視覚化に対して付与されます。



初期条件の例： 

  3
 8 8
 4 3
 3 4


結果： 

  88


可視化（stderr）： 

  11x8：
 +------+ +-+ 
 |  |  |  | 
 |  |  |  | 
 |  |  +-+ 
 |  |  +-+ 
 |  |  |  | 
 |  |  |  | 
 +------+ +-+ 

 8x11：
 +------+ 
 |  |
 |  | 
 |  | 
 |  | 
 |  | 
 |  | 
 +------+ 
 +--+ +--+ 
 |  |  |  | 
 +--+ +--+ 

 11x8：
 +-+ +------+ 
 |  |  |  | 
 |  |  |  | 
 +-+ |  | 
 +-+ |  | 
 |  |  |  | 
 |  |  |  | 
 +-+ +------+ 

 8x11：
 +--+ +--+ 
 |  |  |  | 
 +--+ +--+ 
 +------+ 
 |  | 
 |  | 
 |  | 
 |  | 
 |  | 
 |  | 
 +------+


ところで、この問題を解決しようとしている人もいます。 結果をご覧ください。 その他のアイデアはこちら （ PDF ）。



2番目のタスクは、Dropboxファイルシステムのイベント処理アルゴリズムです。 入力時に、UNIX時間、ファイルへのパス、コンテンツのハッシュを含むタイプADD / DELのイベントのリストが表示されます。 英語で読みやすい形式で提出する必要があります。 報告されているように、理想的な解決策はありませんが、いくつかの解釈方法があります。 それらは、アルゴリズムの速度、出力の美しさ、あいまいなイベントの処理などによって判断されます。 以下の例は正しいですが、結果はユーザーフレンドリーではありません。



初期条件の例： 

  6
 ADD 1282352346 /テスト-
 ADD 1282353016 /test/1.txt f2fa762f
 DEL 1282354012 /テスト-
 DEL 1282354012 /test/1.txt f2fa762f
 ADD 1282354013 / test2-
 ADD 1282354013 /test2/1.txt f2fa762f


結果： 

  dir / testを追加しました。
ファイル/test/1.txtを追加しました。
 dir / test-> / test2に名前が変更されました。


More articles:


All Articles