رخامتان ومبنى مكون من 100 طابق

Question

أحد أسئلة مقابلات البرمجة الكلاسيكية تلك...

يتم إعطاؤك قطعتين من الرخام، ويقال لك إنهما سوف تنكسران عند سقوطهما من ارتفاع معين (ومن المفترض ألا تتعرضا لأي ضرر إذا تم إسقاطهما من أقل من هذا الارتفاع).يتم نقلك بعد ذلك إلى مبنى مكون من 100 طابق (من المفترض أن يكون أعلى من الارتفاع المحدد)، ويطلب منك العثور على أعلى طابق يمكنك إسقاط قطعة رخام منه دون كسرها بأكبر قدر ممكن من الكفاءة.

معلومات اضافية

• يجب أن تجد الطابق الصحيح (ليس نطاقًا ممكنًا)
• الكرات الرخامية مضمونة للكسر في نفس الطابق
• افترض أن تغيير الأرضيات لا يستغرق أي وقت - فقط عدد قطرات الرخام هو الذي يهم
• افترض أن الطابق الصحيح موزع عشوائيًا في المبنى

Answer 1

الشيء المثير للاهتمام هنا هو كيف يمكنك القيام بذلك بأقل قدر ممكن من القطرات.سيكون الذهاب إلى الطابق 50 وإسقاط الطابق الأول أمرًا كارثيًا إذا كان الطابق المتكسر هو الطابق 49، مما يؤدي إلى اضطرارنا إلى القيام بـ 50 هبوطًا.يجب علينا إسقاط الرخامة الأولى في الطابق n، حيث n هو الحد الأقصى لكمية القطرات المطلوبة.إذا انكسرت الرخامة عند الأرضية n، فقد نضطر إلى وضع قطرات n-1 بعد ذلك.إذا لم تنكسر الرخامة فإننا نصعد إلى الطابق 2ن-1 وإذا انكسرت هنا علينا إسقاط الرخامة الثانية ن-2 مرات في أسوأ الحالات.نستمر بهذه الطريقة حتى الطابق 100 ونحاول كسرها عند 3ن-2، 4ن-3....
و ن+(ن-1)+(ن-2)+...1 <=100
n=14 هو الحد الأقصى للقطرات المطلوبة

Answer 2

تمت تغطية هذه المشكلة في المشكلة 6.5 من كتاب "تكسير مقابلة الترميز (الخامس)"، مع تلخيص الحلول على النحو التالي:

ملاحظة:

بغض النظر عن كيفية إسقاط Marble1، يجب على Marble2 إجراء بحث خطي.على سبيل المثال ، إذا كسر الرخام 1 بين الطابق 10 و 15 ، فيجب علينا التحقق من كل طابق بين Marble2

---

التقرب:

المحاولة الأولى: لنفترض أننا أسقطنا قطعة رخام من الطابق العاشر، ثم الطابق العشرين، ...

• في أول كسر رخامي عند أول قطرة (الطابق 10)، يكون لدينا على الأكثر إجمالي 10 قطرات.
• إذا كان الرخام الأول يكسر على آخر قطرة (الطابق 100) ، فسيكون لدينا إجمالي 19 قطرات على الأكثر (الطوابق من 1 إلى 100 ، ثم 91 إلى 99).
• هذا أمر جيد جدًا، لكن كل ما نفكر فيه هو أسوأ الحالات على الإطلاق.يجب أن نفعل بعض "موازنة التحميل" لجعل هاتين الحالتين أكثر حتى.

هدف: أنشئ نظامًا لإسقاط Marble1 بحيث تكون معظم القطرات المطلوبة متسقة، سواء انكسر Marble1 في أول قطرة أو في آخر قطرة.

1. سيكون النظام المتوازن المحمل تمامًا نظامًا يكون فيه قطرات Marble1 + من Marble2 هي نفسها دائمًا ، بغض النظر عن مكان اندلاع Marble1.
2. لكي يكون الأمر كذلك ، نظرًا لأن كل قطرة من Marble1 تتخذ خطوة أخرى ، يُسمح لـ Marble2 بخطوة أقل.
3. لذلك ، يجب علينا تقليل عدد الخطوات التي يحتمل أن تكون مطلوبة بواسطة Marble2 بواسطة قطرة واحدة في كل مرة.على سبيل المثال ، إذا تم إسقاط Marble1 على الطابق 20 ثم الطابق 30 ، فمن المحتمل أن يتطلب Marble2 9 خطوات.عندما نسقط Marble1 مرة أخرى، يجب علينا تقليل خطوات Marble2 المحتملة إلى 8 فقط.على سبيل المثال، يجب علينا إسقاط الرخام 1 في الطابق 39.
4. نعلم ، لذلك ، يجب أن يبدأ Marble1 في الطابق X ، ثم يرتفع بأرضيات X-1 ، ثم X-2 ، ... ، حتى يصل إلى 100.
5. حل من أجل X+(X-1)+(X-2)+…+1 = 100.X(X+1)/2 = 100 -> X = 14

نذهب إلى الطابق 14، ثم 27، ثم 39،... ويستغرق ذلك 14 خطوة كحد أقصى.

---

الكود والامتداد:

• لتنفيذ التعليمات البرمجية، يمكنك التحقق من ذلك هنا.

• للتمديد الى N الرخام، M الطوابق، تحقق من الفصل 12:لغز البيض والأرضيات .

Answer 3

ينكسر كل منهما عند سقوطه من نفس الارتفاع، أم أنهما مختلفان؟

إذا كانوا متماثلين، سأذهب إلى الطابق الخمسين وأسقط الرخام الأول.إذا لم ينكسر، أذهب إلى الطابق 75 وأفعل الشيء نفسه، وطالما لم ينكسر، سأستمر في الصعود بنسبة 50٪ مما تبقى.عندما تنكسر، أعود إلى واحدة أعلى مما كنت عليه سابقًا (لذا إذا انكسرت في الطابق 75 أعود إلى الطابق 51) وأسقط الرخامة الثانية وأصعد طابقًا تلو الآخر حتى تنكسر، وعند هذه النقطة أعرف أعلى طابق يمكنني النزول منه دون أن ينكسر الرخام.

ربما ليست الإجابة الأفضل، فأنا أشعر بالفضول لمعرفة كيف يجيب الآخرون.

Answer 4

قم بإسقاط الرخام الأول في الطابق 10، 20، 30، إلخ.حتى ينكسر ثم القفز مرة أخرى إلى آخر معروف جيد الأرضية وابدأ في إسقاط الكرات من هناك طابقًا تلو الآخر.أسوأ الحالات هي أن تكون 99 هي Magic Floor ويمكنك دائمًا العثور عليها في 19 قطرة أو أقل.

Answer 5

أنا شخصياً لست من أشد المعجبين بأسئلة الألغاز هذه، أفضل تمارين البرمجة الفعلية في المقابلات.

ومع ذلك، سيعتمد الأمر أولاً على ما إذا كان بإمكاني معرفة ما إذا كانت مكسورة أم لا من الأرضية التي أسقطها عليها.سأفترض أنني أستطيع ذلك.

كنت سأصعد إلى الطابق الثاني، وأسقط الرخامة الأولى.إذا انكسر سأحاول الطابق الأول.إذا انكسر هذا سأعلم أنه لا يوجد أرضية.

إذا لم ينكسر الأول، سأذهب إلى الطابق الرابع وأنزل من هناك.إذا انكسر ذلك، فسأعود إلى الأسفل وأحصل على الرخام الآخر، ثم أسقط في الطابق الثالث، سواء انكسر أم لا، سأعرف ما هو الحد الأقصى.

إذا لم ينكسر أي منهما، سأذهب للحصول على كليهما، وأقوم بنفس العملية، هذه المرة بدءًا من الطابق السادس.

بهذه الطريقة، يمكنني تخطي كل طابق آخر حتى أحصل على رخام ينكسر.

سيكون هذا هو الأمثل إذا انكسر الرخام مبكرًا ...أفترض أنه من المحتمل أن يكون هناك عدد مثالي من الطوابق التي يمكنني تخطيها للحصول على أقصى استفادة من كل تخطي...ولكن إذا انكسر أحدها، فسأضطر إلى التحقق من كل طابق على حدة بدءًا من الطابق الأول فوق آخر طابق معروف...وهذا بالطبع سيكون مؤلمًا إذا تخطيت عددًا كبيرًا جدًا من الطوابق (آسف، لن أكتشف الحل الأمثل الآن).

من الناحية المثالية، أريد كيسًا كاملاً من الكريات، ثم يمكنني استخدام خوارزمية بحث ثنائية وتقسيم عدد الطوابق إلى النصف مع كل قطرة...ولكن بعد ذلك، لم يكن هذا هو السؤال، أليس كذلك؟

Answer 6

اعتقد ان حقيقي السؤال هو مدى دقة هل تريد الإجابة.لأن كفاءتك ستعتمد حقًا على ذلك.

سوف أتفق مع جاستن إذا كنت تريد دقة 100 ٪ على الرخام ، ثم بمجرد كسر الرخام الأول الذي ستعرفه على الصعود في وقت واحد من آخر الطابق "الجيد" المعروف حتى تكتشف الطابق الفائز." ربما حتى رمي بعض الإحصاءات وابدأ في الطابق الخامس والعشرين بدلاً من الطابق الخمسين حتى تكون أسوأ سيناريو سيكون 24 بدلاً من 49.

إذا كانت إجابتك يمكن أن تكون زائد أو ناقص طابق أو طابقين، فقد تكون هناك بعض التحسينات.

ثانيًا، هل صعود أو نزول الدرج يؤثر على كفاءتك؟في هذه الحالة، قم دائمًا بإسقاط الكرتين والتقاطهما في كل رحلة لأعلى/لأسفل.

Answer 7

أسقط الرخامة الأولى من الطابق الثالث.إذا انكسرت، فاعلم أنه الطابق 1 أو 2، لذا قم بإسقاط الرخام الآخر من الطابق 2.إذا لم ينكسر فقد وجدت أن الطابق 2 هو الأعلى.إذا انكسر، فقد وجدت أن الطابق 1 هو الأعلى.2 قطرات.

إذا لم يؤدي السقوط من الطابق الثالث إلى كسر الرخام، فقم بالهبوط من الطابق السادس.إذا انكسر، فاعلم أن الطابق 4 أو 5 هو الأعلى.أسقط الرخامة الثانية من الطابق الخامس.إذا لم ينكسر فقد وجدت أن الرقم 5 هو الأعلى.إذا حدث ذلك، فإن الطابق 4 هو الأعلى.4 قطرات.

يكمل.

3 طوابق - حد أقصى قطرتين

6 طوابق - بحد أقصى 4 قطرات

9 طوابق - بحد أقصى 6 قطرات

12 طابقًا - بحد أقصى 8 قطرات

إلخ.

3x طوابق - بحد أقصى 2x قطرات

لذلك بالنسبة للمبنى المكون من 99 طابقًا، سيكون لديك 66 نقطة كحد أقصى.وهذا هو الحد الأقصى.من المحتمل أن يكون لديك قطرات أقل من ذلك.و66 هو الحد الأقصى لمبنى مكون من 100 طابق أيضًا.ستحتاج فقط إلى 66 نقطة إذا كانت طابق الاستراحة هو الطابق 98 أو 97.إذا كانت أرضية الاستراحة 100 فستستخدم 34 قطرة.

على الرغم من أنك قلت أن الأمر لا يهم، فمن المحتمل أن يتطلب هذا أقل قدر من المشي ولا يتعين عليك معرفة مدى ارتفاع المبنى.

جزء من المشكلة هو كيفية تعريف الكفاءة.هل من "الأكثر كفاءة" أن يكون لديك دائمًا حل في أقل من x قطرات، أم أنه أكثر كفاءة أن يكون لديك فرصة جيدة للحصول على حل في قطرات y حيث y < x مع التحذير من أنه يمكن أن يكون لديك أكثر من x قطرات ؟

Answer 8

يمكن القيام بذلك بشكل أفضل باستخدام 7 كرات فقط.

إذن، بعد الإجابة التي تم التصويت عليها، لنفترض أن الرخام ينكسر في الطابق 49 على الأقل.

1. الطابق 50 -> فواصل (الإجابة بين 1 إلى 50 شاملة)
2. الطابق 25 -> لا ينكسر (26 إلى 50)
3. الطابق 37 -> لا ينكسر (38 إلى 50)
4. الطابق 43 -> لا ينكسر (44 إلى 50)
5. الطابق 46 -> لا ينكسر (47 إلى 50)
6. الطابق 48 -> لا ينكسر (49 أو 50)
7. الطابق 49 -> الفواصل (الطابق 49، هذه الخطوة مطلوبة بالفعل لأنه ربما كان الحد الأدنى لكسر الرخام يقع عند الطابق 50)

يمكن تخيل ذلك على أنه إجراء بحث ثنائي في مجموعة مرتبة لبعض k، حيث نقوم بنصف مساحة الحل مع كل محاولة.بالنسبة لـ 100 طابق، نحتاج إلى log2 100 = 6.644 (7 محاولات).باستخدام 7 كرات من الرخام، يمكننا التأكد من أن الحد الأدنى للأرضية التي يمكن تقسيمها إلى 128 طابقًا.

Answer 9

أول شيء سأفعله هو استخدام الخوارزمية البسيطة الميتة التي تبدأ من الطابق 1، حيث تقوم بإسقاط الرخام طابقًا تلو الآخر حتى يصل إلى 100 أو ينكسر الرخام.

ثم أود أن أسأل لماذا يجب أن أقضي وقتًا في تحسينه حتى يتمكن شخص ما من إثبات أنه سيكون مشكلة.في كثير من الأحيان ينشغل الناس بالعثور على الخوارزمية المعقدة المثالية في حين أن خوارزمية أبسط بكثير ستحل المشكلة.وبعبارة أخرى، لا تقم بتحسين الأشياء حتى تكون هناك حاجة إليها.

قد يكون هذا سؤالًا خادعًا لمعرفة ما إذا كنت أحد هؤلاء الأشخاص الذين يمكنهم إنشاء جبل من تلة الخلد.