टीएल;डीआर

  • समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
  • दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ६.८: दो अंडे और १०० मंजिलों से क्रांतिक मंजिल ढूँढो, सबसे खराब स्थिति में गिरावटें कम से कम रखो। घटते अंतराल से हर रास्ता बराबर करो और समीकरण x(x+१)/२ >= १०० हल करो।
  • जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

एक इमारत में १०० मंजिल हैं। तुम्हारे पास दो अंडे हैं। कोई क्रांतिक मंजिल F है: F या उससे ऊपर से गिरा अंडा फूटता है, F से नीचे से बच जाता है। बचे अंडे फिर गिरा सकते हो। फूटे गए खत्म। F पता नहीं (१ से १०० तक, या मॉडल के अनुसार "कभी नहीं फूटता")। लक्ष्य: F ढूँढो और सबसे खराब स्थिति में गिरावटों की संख्या कम से कम रखो।

यह रणनीति का पहेली है, दो अंडों के लिए साफ बंद रूप के साथ। चाल बाइनरी खोज नहीं। गिरावट की मंजिलें चुनो ताकि हर परिणाम का रास्ता बाकी बजट बराबर जलाए। यह पोस्ट शुरुआती लोगों के लिए मूल शिक्षण है, जावा में इष्टतम गिरावट संख्या और मंजिल अनुसूची निकालने के साथ। इंटरव्यू वाली अंडा-गिरावट प्रश्नों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ६, गणित और तर्क, समस्या ६.८।

१. रोज़मर्रा की उपमा

काँच के फोन कवर सीढ़ियों से गिराकर जाँच रहे हो। दो नमूने। एक फट गया तो वह नमूना खत्म। फिर भी वह सबसे निचला पायदान चाहिए जहाँ फटना शुरू होता है।

नीचे से एक-एक पायदान चढ़ोगे तो नमूना नहीं बरबाद, पर सबसे खराब दिन सौ चढ़ाइयाँ।

आधे पर कूदोगे, फिर आधे पर, जल्दी फटने पर आखिरी सुरक्षित जगह और फटने के बीच हर पायदान एक बचे नमूने से रेंगना पड़ता है। वह रेंगना लंबा हो सकता है। बाइनरी खोज तब चमकती है जब नमूने मुफ्त हों। यहाँ नमूने कम हैं।

इसलिए कोच की तरह निश्चित समय सीमा से योजना बनाओ। "सबसे खराब रास्ते पर ज्यादा से ज्यादा x गिरावटें।" हर पहला कूद नीचे इतने पायदान छोड़ता है कि दूसरा नमूना खत्म कर सके, और ऊपर इतने कूद अगर नमूना बचे। बाकी समय घटते ही कूद छोटे होते जाते। पूरी बात यही है।

२. समस्या सादे शब्दों में

सेटअप:

  • n मंजिलों वाली इमारत (क्लासिक: n = 100)।
  • k अंडे (क्लासिक: k = 2)।
  • क्रांतिक मंजिल F: F और ऊपर फूटता, F से नीचे बचता।
  • एक गिरावट = एक मंजिल से एक अंडा।
  • बचे अंडे फिर गिरा सकते हो। फूटे नहीं।
  • F पहचानो (या साबित करो कोई मंजिल पर नहीं फूटता)।

लक्ष्य: ऐसी रणनीति चुनो जो सबसे खराब स्थिति में गिरावटें कम करे। औसत नहीं। "काश अंडा न फूटे" नहीं।

इंटरव्यू में स्पष्ट करो:

  • क्या मंजिल १ क्रांतिक हो सकती है? (हाँ। कभी F को ० से n तक मॉडल करते हैं: ० मतलब मंजिल १ से भी फूटता, n+1 मतलब कभी नहीं।)
  • क्या "F ढूँढना" में कभी-न-फूटना शामिल? (अपना मॉडल बताओ। क्लासिक कथन में १०० मंजिल का मतलब अक्सर १०० संभावनाओं में सीमा अलग करना।)
  • सबसे खराब स्थिति या समान F पर औसत? (इस समस्या में सबसे खराब।)
  • कितने अंडे? २ पर रहो जब तक वे सामान्य डीपी न खोलें।

सहायक कोड के हस्ताक्षर:

// smallest max drops D such that 2 eggs can cover n floors
int minDropsTwoEggs(int floors);

// first-drop floors for a plan with D drops (1-based floor numbers)
int[] dropSchedule(int floors, int drops);

छोटी संख्या झलक (तैयार जवाब):

सबसे छोटा x चाहिए जहाँ:

x(x + 1) / 2 >= 100

13 * 14 / 2 = 91   < 100
14 * 15 / 2 = 105  >= 100

इसलिए १०० मंजिल और २ अंडों के लिए सबसे खराब गिरावट संख्या १४ है।

३. पहले सोचो

एक अंडे से रैखिक स्कैन (या पहला फूटने के बाद)

एक अंडा बचा तो विकल्प नहीं: आखिरी सुरक्षित मंजिल से एक-एक ऊपर चलो। छोड़ोगे तो फूटने पर खाली जगह नहीं सुलझती।

मंजिल १ से शुद्ध रैखिक का सबसे खराब: १०० गिरावटें। सही, उबाऊ, और अंडा १ फूटने पर यहीं लौटते हो।

सादी बाइनरी खोज क्यों इष्टतम नहीं

बाइनरी खोज सीमा आधी करती है। असीमित अंडों पर ठीक। दो पर:

  • पहली गिरावट मंजिल ५०। फूटा तो अंडा २ को १..४९ रैखिक। सबसे खराब: 1 + 49 = 50।
  • बचा तो ऊपर दो अंडे, पर बाद के बाइनरी कट पर जल्दी फूटना फिर बड़ा रैखिक टुकड़ा छोड़ता है।

बाइनरी-जैसी कटों का सबसे खराब लगभग ५०, १०० से बेहतर, इष्टतम से दूर। समस्या असममित लागत है: फूटना एक अंडा खर्च कर नीचे रैखिक थोपता है; बचना सिर्फ एक गिरावट। बराबर अंतराल इसे नजरअंदाज करते हैं।

बाकी सबसे खराब स्थिति बराबर करो

बजट D चुनो: "कोई रास्ता D से ज्यादा गिरावट न ले।"

२ अंडे और D गिरावटें बचीं तो पहली गिरावट ऐसी मंजिल से:

१. फूटा: D - 1 गिरावट और १ अंडा। नीचे ज्यादा से ज्यादा D - 1 मंजिल (रैखिक)। इसलिए पहली गिरावट मंजिल (D - 1) + 1 = D पर। २. बचा: D - 1 गिरावट और २ अंडे। उसी तर्क को उस मंजिल के ऊपर दोहराओ।

दोनों अंडे रहते हुए लगातार कोशिशों के बीच अंतराल:

D, then D-1, then D-2, ..., then 1

बजट D से ढकी मंजिलें:

sum = D + (D - 1) + ... + 1 = D(D + 1) / 2

सबसे छोटा D ढूँढो जहाँ D(D + 1) / 2 >= n।

n = 100 के लिए:

डी डी(डी+१)/२ काफी?
१२ ७८ नहीं
१३ ९१ नहीं
१४ १०५ हाँ
१५ १२० हाँ, पर सबसे खराब बड़ा

उत्तर: १४।

उदाहरण अनुसूची (मंजिलें, १-आधार)

D = 14 पर, दोनों अंडे जीवित रहते पहली कोशिश मंजिलें (संचयी):

14,
14 + 13 = 27,
27 + 12 = 39,
39 + 11 = 50,
50 + 10 = 60,
60 + 9  = 69,
69 + 8  = 77,
77 + 7  = 84,
84 + 6  = 90,
90 + 5  = 95,
95 + 4  = 99,
99 + 3  = 102  (clamp to 100; you only need 100 floors)

१०० की कवरेज काफी, सैद्धांतिक १०५ स्लॉट हैं, इसलिए आखिरी अंतराल सिकुड़ सकते या १०० पर रुकें। सबसे खराब रास्ता फिर भी १४ से ऊपर नहीं जाता।

काम किया रास्ता

मानो F = 32 (३२ से फूटना शुरू)।

१. १४ पर गिरावट: बचा। २. २७ पर गिरावट: बचा। ३. ३९ पर गिरावट: फूटा। एक अंडा। आखिरी सुरक्षित = २७। ४. रैखिक: २८, २९, ३०, ३१, ३२ (३२ पर फूटा)।

गिरावटें: दो-अंडा कोशिशें प्लस २८ से ३२ तक रैखिक। बोर्ड पर गिनती सावधानी से; बात यह कि हर शाखा १४ से न बढ़े, इसी नाप से बनी थी।

सामान्यीकरण (अगर पूछें)

k अंडे और D गिरावटों पर क्लासिक पुनरावृत्ति:

floors(D, k) = 1 + floors(D - 1, k - 1)  // break
             + floors(D - 1, k)          // survive

आधार: floors(0, *) = 0, floors(*, 1) = D (रैखिक), floors(D, 0) = 0। k = 2 पर ऊपर वाले त्रिभुजीय अंकों में सिमटता है। इंटरव्यू ६.८ को २ अंडों का बंद रूप चाहिए; डीपी बोनस है।

४. जावा समाधान (इष्टतम गिरावटें गिनो)

तर्क पहेली सुलझाता है। कोड दिखाता है D निकाल सकते हो, अनुसूची लिख सकते हो, और बड़े n पर D खोज सकते हो।

त्रिभुजीय कवरेज वाला सबसे छोटा डी

/** Sum 1+2+...+d. Careful with overflow for huge d. */
static long triangular(int d) {
    return (long) d * (d + 1) / 2;
}

/**
 * Minimal worst-case drops for 2 eggs and {@code floors} floors.
 * Smallest d with d*(d+1)/2 >= floors.
 */
static int minDropsTwoEggs(int floors) {
    if (floors <= 0) {
        return 0;
    }
    int d = 1;
    while (triangular(d) < floors) {
        d++;
        // optional guard for absurd inputs
        if (d > floors) {
            return floors; // linear is always enough
        }
    }
    return d;
}

१०० मंजिल पर यह १४ लौटाता है।

बंद रूप (वैकल्पिक, तेज)

d(d+1)/2 >= n को द्विघात सूत्र से:

d ≈ ceil( (-1 + sqrt(1 + 8n)) / 2 )

static int minDropsTwoEggsClosed(int floors) {
    if (floors <= 0) {
        return 0;
    }
    // ceil( (-1 + sqrt(1+8n)) / 2 )
    double d = Math.ceil((-1.0 + Math.sqrt(1.0 + 8.0 * floors)) / 2.0);
    int ans = (int) d;
    // float safety: bump until coverage holds
    while (triangular(ans) < floors) {
        ans++;
    }
    while (ans > 1 && triangular(ans - 1) >= floors) {
        ans--;
    }
    return ans;
}

बोर्ड पर लूप या "१३ फिर १४" तालिका काफी। प्रभाव जमाना हो तो बंद रूप बताओ।

पहली-गिरावट अनुसूची बनाओ

/**
 * Floors (1-based) where you attempt while both eggs remain,
 * for a plan with {@code drops} budget covering {@code floors}.
 * Stops at or before {@code floors}.
 */
static int[] dropSchedule(int floors, int drops) {
    if (floors <= 0 || drops <= 0) {
        return new int[0];
    }
    java.util.ArrayList<Integer> list = new java.util.ArrayList<>();
    int floor = 0;
    int step = drops;
    while (floor < floors && step >= 1) {
        floor = Math.min(floors, floor + step);
        list.add(floor);
        if (floor >= floors) {
            break;
        }
        step--;
    }
    int[] out = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        out[i] = list.get(i);
    }
    return out;
}

त्वरित जाँच

static void demo() {
    int n = 100;
    int d = minDropsTwoEggs(n);
    System.out.println("min worst-case drops = " + d); // 14
    System.out.println("coverage = " + triangular(d)); // 105

    System.out.println(minDropsTwoEggs(91));  // 13
    System.out.println(minDropsTwoEggs(92));  // 14
    System.out.println(minDropsTwoEggs(1));   // 1
    System.out.println(minDropsTwoEggs(0));   // 0

    int[] plan = dropSchedule(n, d);
    System.out.println(java.util.Arrays.toString(plan));
    // [14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100] style sequence
}

एक अंडा और अनंत अंडे (इंटरव्यू बात)

// 1 egg: must linear scan
static int minDropsOneEgg(int floors) {
    return Math.max(floors, 0);
}

// unlimited eggs: binary search worst case
static int minDropsUnlimitedEggs(int floors) {
    if (floors <= 0) {
        return 0;
    }
    return (int) Math.ceil(Math.log(floors + 1) / Math.log(2)); // rough model; state your floor numbering
}

२ अंडों पर तुम इन छोरों के बीच हो: रैखिक से बेहतर, शुद्ध बाइनरी से कमजोर, और गणित त्रिभुजीय।

५. जटिलता तालिका

तरीका सबसे खराब गिरावटें (न=१००, २ अंडे) नोट
मंजिल १ से रैखिक १०० सिर्फ १ अंडा हो तो इष्टतम
बाइनरी पहला कट, फूटने पर रैखिक ~५० असममित लागत अनदेखी
आकार स के बराबर अंतराल लगभग न/स + स समायोज्य, घटते कदमों से अक्सर बदतर
घटते अंतराल डी, डी-१, ... १४ २ अंडों के लिए इष्टतम
सामान्य क अंडे का डीपी क पर निर्भर क्लासिक ६.८ के लिए ज्यादा

D गिनने का समय while से: ओ(वर्गमूल(न)) पुनरावृत्ति क्योंकि D ~ O(sqrt(n))। बंद रूप: ओ(१) अंकगणित प्लस छोटा सुधार। अनुसूची बनाना ओ(डी)।

इंटरव्यू मापदंड सबसे खराब गिरावटें है, योजनाकार का प्रोसेसर समय नहीं।

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर ये छूते हैं:

  • न = १: उत्तर १। एक मंजिल, एक गिरावट बताती फूटा या नहीं।
  • न = ०: उत्तर ०।
  • ठीक त्रिभुजीय: n = 91 को १३ चाहिए, १४ नहीं। असमानता पर एक-की-गलती आम।
  • न = १००: १४ ही। कोई १३ कहे तो कवरेज सिर्फ ९१ मंजिल।
  • पहला अंडा फूटने के बाद: रैखिक मजबूर। एक अंडे से मंजिल छोड़ना सख्त फेल।
  • समान F पर औसत अनुकूलन: दूसरा लक्ष्य। यह समस्या सबसे खराब।
  • एफ = ०..न बनाम १..न: कितने अलग नतीजे चाहिए बताओ। त्रिभुजीय तर्क "बजट डी से कितनी मंजिल जानकारी" खरीदते हो, यही ढकता है।
  • तीन अंडे: पुनरावृत्ति पूछ सकते। बिना दोबारा गिने १४ मत ठहरो।

आम गलतियाँ:

१. बाइनरी खोज को इष्टतम कहना क्योंकि "लॉग १०० लगभग ७।" यह अंडे मुफ्त मानता है। २. निश्चित अंतर १० (१०, २०, ३० पर गिरावट): सबसे खराब १० + ९ = १९ जब १० पर फूटे और १..९ स्कैन, या वैसा। १४ से बदतर। ३. x² = १०० → x = १० हल कर रुकना। x(x+1)/2 चाहिए, x² नहीं। ४. अंतराल सिकुड़ते भूलना। स्थिर कदम देर के रास्ते सस्ते और जल्दी-फूट महंगे छोड़ता है; पुनर्संतुलन करो। ५. सिर्फ पहले अंडे की गिरावटें गिनना और सबसे खराब में दूसरे के रैखिक खंड को छोड़ना। ६. बड़े न पर d * (d + 1) में पूर्णांक ओवरफ्लो अगर लापरवाही से int। गुणनफल में long।

न्यूनतम धुआँ:

assert minDropsTwoEggs(100) == 14;
assert minDropsTwoEggs(91) == 13;
assert minDropsTwoEggs(92) == 14;
assert triangular(14) == 105;
assert minDropsTwoEggsClosed(100) == 14;

७. दोस्त को समझाने वाला सार

दो अंडे, १०० मंजिल, सबसे खराब दिन कम करो।

१. एक अंडा बचा तो एक-एक मंजिल चलो। कभी मत छोड़ो। २. बाइनरी खोज सबसे खराब बिगाड़ती है क्योंकि बड़ी आधी में फूटना लंबा रेंगना थोपता है। ३. गिरावट बजट D तय करो। कोशिशें इस तरह फैलाओ कि फूटना और बचना दोनों D कुल गिरावट में खत्म हों। ४. इससे अंतराल D, D-1, ..., 1। कवरेज त्रिभुजीय संख्या D(D+1)/2। ५. D(D+1)/2 >= 100 वाला सबसे छोटा D १४ है (९१ कम, १०५ काफी)। ६. जावा में d ऊपर बढ़ाओ जब तक त्रिभुज n ढके, या द्विघात बंद रूप प्लस सुरक्षा समायोजन।

अगर बिना रटाए रुमाल पर "क्यों १४" निकाल सको, समस्या ६.८ तुम्हारी। सीरीज़ में आगे: तालों वाली शुद्ध गिनती पहेली।

श्रृंखला