ड्रॉपबॉक्स दो आयामी पैकेजिंग चुनौती

ड्रॉपबॉक्स ने संभावित नौकरी के उम्मीदवारों के लिए पहेलियाँ प्रकाशित की हैं। कृपया परीक्षण समस्याओं के लिए अपने समाधान jobs@dropbox.com पर भेजें। जैसा कि साइट पर कहा गया है, इन पत्रों के लेखकों के साथ, "हमें कुछ बात करनी है।"



पहला कार्य वस्तुओं के द्वि-आयामी पैकिंग के लिए एक एल्गोरिदम है। एक दिए गए लंबाई और ऊंचाई के आयतों को न्यूनतम क्षेत्र पर रखना आवश्यक है। इनपुट पर, आउटपुट पर लंबाई और चौड़ाई (पूर्णांक) को इंगित करने वाली वस्तुओं की एक सूची, फ़ंक्शन को न्यूनतम आयत का क्षेत्र देना चाहिए जहां उन्हें रखा गया है। वस्तुओं को 90 ° घुमाया जा सकता है। अतिरिक्त बोनस अंक stderr टूल का उपयोग करके विज़ुअलाइज़ेशन के लिए दिए जाते हैं।



प्रारंभिक स्थितियों का एक उदाहरण:

  3
 8 8
 ४ ३
 ३ ४ 

परिणाम:

  88 

विज़ुअलाइज़ेशन (stderr):

  11x8:
 + - - - - - - + + - + 
 |  |  |  | 
 |  |  |  | 
 |  |  + - + 
 |  |  + - + 
 |  |  |  | 
 |  |  |  | 
 + - - - - - - + + - + 

 8x11:
 + - - - - - - + 
 |  |
 |  | 
 |  | 
 |  | 
 |  | 
 |  | 
 + - - - - - - + 
 + - - + + - - + 
 |  |  |  | 
 + - - + + - - + 

 11x8:
 + - + + - - - - - - + 
 |  |  |  | 
 |  |  |  | 
 + - + |  | 
 + - + |  | 
 |  |  |  | 
 |  |  |  | 
 + - + + - - - - - - + 

 8x11:
 + - - + + - - + 
 |  |  |  | 
 + - - + + - - + 
 + - - - - - - + 
 |  | 
 |  | 
 |  | 
 |  | 
 |  | 
 |  | 
 + - - - - - - + 

वैसे, कुछ पहले से ही इस समस्या को हल करने की कोशिश कर चुके हैं: परिणाम देखें। अन्य विचार यहाँ ( पीडीएफ )।



दूसरा कार्य ड्रॉपबॉक्स फ़ाइल सिस्टम में एक इवेंट प्रोसेसिंग एल्गोरिथम है। इनपुट में, आपको ADD / DEL के साथ UNIX समय, फ़ाइल का पथ और सामग्री हैश जैसी घटनाओं की एक सूची दी गई है। आपको उन्हें अंग्रेजी में पठनीय रूप में लाने की आवश्यकता है। जैसा कि बताया गया है, कोई आदर्श समाधान नहीं है, लेकिन व्याख्या के कई तरीके हैं। उन्हें एल्गोरिथ्म की गति, आउटपुट की सुंदरता, अस्पष्ट घटनाओं के प्रसंस्करण, आदि द्वारा आंका जाएगा। नीचे दिया गया उदाहरण सही है, लेकिन परिणाम उपयोगकर्ता के अनुकूल नहीं दिखता है।



प्रारंभिक स्थितियों का एक उदाहरण:

  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/1.txt।
 नामित नाम / परीक्षण -> / test2।