كيفية حل اللغز الخاص بموظفي Google حول رمي البيض من أحد المباني

هناك الكثير من الألغاز الرائعة لبرمجة المقابلات الوظيفية. تُعرف أيضًا المفضلة الخاصة بي كواحدة من المفضلات بين مستخدمي Google:

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

يمكننا تقديم بعض الافتراضات:

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

معظم الناس يكتبون بعض الخوارزميات لحل هذا اللغز (وسنفعل ذلك أيضًا) ، ولكن يوجد بالفعل حل سهل.

أبسط إجابة

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

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

إجابة بديهية

وبهذه الطريقة ، يجب استخدام بيضتنا الأولى لتقسيم نطاق 100 طابق إلى نطاقات أصغر كفاءة قدر الإمكان. وبالتالي ، فإن الإجابة سهلة الاستخدام والشعبية هي رمي البويضة الأولى من 1 / n-th من الطوابق للتحقق. على سبيل المثال 1/3. ستظهر الخوارزمية كما يلي:

  • رمي البيض من الطابق 33. إذا تحطمت ، فإننا نتحقق من أول 32 طابقًا باستخدام البويضة الثانية.
  • خلاف ذلك ، فإننا نلقي البيض من 33 + (67 * 1/3) = الطابق 55. إذا تحطمت ، فإننا نتحقق من الطوابق من 34 إلى 55 باستخدام البويضة الثانية.
  • ...

سيناريو الحالة الأسوأ بالنسبة لـ 1/3 هو الحد الأقصى (33 ، 24 ، ...) = 33. وبهذه الطريقة قد نجد n مثاليًا يحسن عدد الرميات باستخدام بعض البرمجة الديناميكية. هذا هو الحل القيم الذي يقدم التفكير في البرمجة ، لكنه ليس حلاً مثاليًا.

الحل الأمثل

لفهم الحل الأمثل ، نحتاج إلى فهم التوازن الذي يتم استخدامه لحساب عدد الرميات في أسوأ سيناريو:

حيث F (n) هو الطابق التالي الذي نرمي منه البويضة الأولى

إذا قدمنا ​​المتغير التالي:

ثم التوازن هو التالي:

الحل الأمثل هو عندما تكون جميع وسيطات هذه الدالة max متساوية. كيف يمكننا تحقيق ذلك؟ إذا نظرنا من النهاية ، ستكون آخر D (ن) 1 ، لأننا سنصل أخيرًا إلى النقطة التي لا يوجد فيها سوى طابق واحد للبيضة الأولى. لذلك يجب أن تكون D (n-1) تساوي 2 لأنها تحتوي على رمية واحدة أقل من البويضة الأولى.

نرى حينها أنه يجب إلقاء البويضة الأولى أخيرًا من الطابق 99 ، سابقًا من 99-2 = 97 ، سابقًا من 97-3 = 94 ، 90 ، 85 ، 79 ، 72 ، 64 ، 55 ، 45 ، 34 ، 22 و الطابق التاسع هذا هو الحل الأمثل! وبهذه الطريقة ، نحتاج إلى 14 رمية في أسوأ السيناريوهات (أصغر الفرق هو 13 ، ولكن كان علينا أن نرمي مرة أخرى في الطابق التاسع).

معادلة بسيطة للعثور على الجواب هي التالية:

حيث f هو عدد الطوابق. هذا يمكن تبسيطه إلى:

هذا يساوي:

التحقق من

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

متعة maxThrows (floorLeft: Int، nextFloor: Int): Int =
  إذا كانت (floorLeft <= 2)
  else maxOf (nextFloor ، bestMaxThrows (floorLeft - nextFloor) + 1)

لقد استخدمنا هنا وظيفة bestMaxThrows. إنها وظيفة افتراضية تقوم بإرجاع عدد من الرميات بافتراض أن القرارات التالية مثالية. هذه هي الطريقة التي يمكننا تعريفها:

bestMaxThrows متعة (floorLeft: Int): Int =
  maxThrows (floorLeft ، bestNextStep (floorLeft))

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

val bestNextStep (floorLeft: Int): Int =
  إذا كان (floorLeft <= 2) 1
  آخر (1. الزهور)
        .لإدراج()
        .minBy {maxThrows (floorsLeft، it)} !!

لاحظ أن هذه الوظيفة تستخدم الدالة maxThrows ، لذلك نتعامل مع التكرار. إنها ليست مشكلة ، لأنه عندما يستدعي bestNextStep maxThrows ، فإنه يستدعي ذلك دائمًا بقيمة أصغر ثم floorLeft (لأن nextFloor يكون دائمًا أكبر من 0). قبل أن نستخدمها سنضيف التخزين المؤقت لتسريع العمليات الحسابية:

val bestNextStep: (Int) -> Int = memorize {floorsLeft ->
  إذا كان (floorLeft <= 2) 1
  آخر (1. الزهور)
        .لإدراج()
        .minBy {maxThrows (floorsLeft، it)} !!
}

متعة maxThrows (floorLeft: Int، nextFloor: Int): Int =
  إذا كانت (floorLeft <= 2)
  else maxOf (nextFloor ، bestMaxThrows (floorLeft - nextFloor) + 1)


val bestMaxThrows: (Int) -> Int = احفظ {floorsLeft ->
  maxThrows (floorLeft ، bestNextStep (floorLeft))
}

متعة  حفظ (f: (V) -> T): (V) -> T {
    val map = mutableMapOf  ()
    إرجاع {map.getOrPut (it) {f (it)}}
}

أولاً ، يمكننا التحقق مما إذا كانت تُرجع نفس النتيجة التي قمنا بحسابها:

متعة الرئيسية (args: Array ) {
    print (bestMaxThrows (100)) // المطبوعات: 14
}

الجواب جيد :) دعنا نتحقق من خطواتنا التالية:

متعة الرئيسية (args: Array ) {
    فار الكلمة = 0
    بينما (الكلمة <100) {
        فال الطوابق اليسرى = 100 - الكلمة
        val nextStep = bestNextStep (floorLeft)
        الكلمة + = nextStep
        طباعة ("الكلمة الدنيا")
    }
}

نتيجة:

9 ، 22 ، 34 ، 45 ، 55 ، 64 ، 72 ، 79 ، 85 ، 90 ، 94 ، 97 ، 99 ، 100 ،

فقط كيف حسبنا! لطيف: د

الصورة الاكبر

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

استنتاج

أنت الآن مستعد بشكل أفضل لمقابلة Google الخاصة بك ، ولكن الأهم من ذلك أنك الآن أفضل استعدادًا للتفكير الحسابي العام. قدمت هذه الخوارزمية مقاربة وظيفية لطيفة. يمكن استخدام نهج مشابه للعديد من المشكلات المختلفة في وظائفنا اليومية.

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