algorithm - computer - साक्षात्कार प्रश्न: पूर्णांक की मेगा संख्या से मेडियन का पता लगाएं



algorithm meaning in hindi (6)

एक फ़ाइल है जिसमें पूर्णांक की 10G (1000000000) संख्या है, कृपया इन पूर्णांकों का माध्यिका ज्ञात करें। ऐसा करने के लिए आपको 2G मेमोरी दी जाती है। क्या कोई उचित तरीके से आ सकता है? धन्यवाद!

https://ffff65535.com


  1. पूर्णांक को सॉर्ट करने के लिए फ़ाइल पर एक ऑन-डिस्क बाहरी मर्ज करें (यदि यह पहले से ज्ञात नहीं है तो उन्हें गिना जाए)।
  2. एक बार फ़ाइल को सॉर्ट करने के बाद, मध्य क्रम (विषम स्थिति) की तलाश करें, या औसतन प्राप्त करने के लिए फ़ाइल में दो मध्य संख्याओं (यहां तक ​​कि मामले) का औसत निकालें।

उपयोग की गई मेमोरी मूल फ़ाइल में पूर्णांकों की संख्या से समायोज्य और अप्रभावित है। बाहरी प्रकार की एक चेतावनी यह है कि मध्यवर्ती सॉर्टिंग डेटा को डिस्क पर लिखा जाना चाहिए।

मूल फ़ाइल में n = पूर्णांक की संख्या को देखते हुए:

  • समय चल रहा है: O(nlogn)
  • मेमोरी: O(1) , समायोज्य
  • डिस्क: O(n)

8-बाइट की एक सरणी बनाएं जिसमें 2 ^ 16 प्रविष्टियां हों। अपने इनपुट नंबर लें, नीचे के सोलह बिट्स को शिफ्ट करें, और हिस्टोग्राम बनाएं।

अब आप उस हिस्टोग्राम में गिनती करते हैं जब तक कि आप उन बिन तक नहीं पहुंच जाते जो मूल्यों के मध्य बिंदु को कवर करते हैं।

उन सभी नंबरों को अनदेखा करते हुए फिर से गुजरें, जिनमें शीर्ष बिट्स का एक ही सेट नहीं है, और नीचे के बिट्स का हिस्टोग्राम करें।

उस हिस्टोग्राम के माध्यम से तब तक गिनें जब तक आप उस बिन तक नहीं पहुँच जाते हैं जो मूल्यों के मध्य बिंदु (संपूर्ण सूची) को कवर करता है।

अब आप माध्यिका को O(n) समय और O(1) स्थान (अभ्यास में, 1 एमबी से कम) जानते हैं।

यहाँ कुछ नमूना स्काला कोड है जो ऐसा करता है:

def medianFinder(numbers: Iterable[Int]) = {
  def midArgMid(a: Array[Long], mid: Long) = {
    val cuml = a.scanLeft(0L)(_ + _).drop(1)
    cuml.zipWithIndex.dropWhile(_._1 < mid).head
  }
  val topHistogram = new Array[Long](65536)
  var count = 0L
  numbers.foreach(number => {
    count += 1
    topHistogram(number>>>16) += 1
  })
  val (topCount,topIndex) = midArgMid(topHistogram, (count+1)/2)
  val botHistogram = new Array[Long](65536)
  numbers.foreach(number => {
    if ((number>>>16) == topIndex) botHistogram(number & 0xFFFF) += 1
  })
  val (botCount,botIndex) =
    midArgMid(botHistogram, (count+1)/2 - (topCount-topHistogram(topIndex)))
  (topIndex<<16) + botIndex
}

और यहाँ यह इनपुट डेटा के एक छोटे सेट पर काम कर रहा है:

scala> medianFinder(List(1,123,12345,1234567,123456789))
res18: Int = 12345

यदि आपके पास 64 बिट पूर्णांक संग्रहीत हैं, तो आप इसके बजाय 4 पास में एक ही रणनीति का उपयोग कर सकते हैं।


फ़ाइल के माध्यम से एक पास बनाएं और पूर्णांक और न्यूनतम और अधिकतम पूर्णांक मान की गणना करें।

मिडपॉइंट और अधिकतम का मध्य बिंदु लें, और मिडपॉइंट के दोनों ओर के मानों के लिए गिनती, न्यूनतम और अधिकतम प्राप्त करें - फिर से फ़ाइल के माध्यम से पढ़कर।

विभाजन की गिनती> गिनती => माध्य उस विभाजन के भीतर होता है।

विभाजन के लिए दोहराएं, 'विभाजन के बाईं ओर' (आसान बनाए रखने के लिए) के आकार को ध्यान में रखते हुए, और न्यूनतम = अधिकतम के लिए भी देख रहा है।

यकीन है कि यह विभाजन की एक मनमानी संख्या के लिए भी काम करेगा।


मुझे भी यही सवाल पूछा गया था और मैं एक सटीक उत्तर नहीं बता सका इसलिए साक्षात्कार के बाद मैं साक्षात्कार पर कुछ पुस्तकों के माध्यम से चला गया और यहाँ मुझे क्रैकिंग द कोडिंग साक्षात्कार पुस्तक से क्या मिला है।

उदाहरण: संख्या अनियमित रूप से उत्पन्न होती है और एक (विस्तार) सरणी में संग्रहीत होती है। कैसे होगा माध्यिका का ट्रैक?

हमारी डेटा संरचना मंथन निम्नलिखित की तरह लग सकता है:

• लिंक्ड सूची? शायद ऩही। लिंक किए गए सूचियों तक पहुँचने और छँटाई के साथ बहुत अच्छा नहीं करते हैं।

• एरे? हो सकता है, लेकिन आपके पास पहले से ही एक सरणी हो। क्या आप किसी तरह तत्वों को सुलझा सकते हैं? वह शायद महंगा है। चलिए इस पर पकड़ बनाते हैं और यदि आवश्यक हो तो इसे वापस करते हैं।

• बाइनरी ट्री? यह संभव है, क्योंकि बाइनरी पेड़ ऑर्डर देने के साथ काफी अच्छा करते हैं। वास्तव में, यदि बाइनरी सर्च ट्री पूरी तरह से संतुलित है, तो शीर्ष मंझला हो सकता है। लेकिन, सावधान रहें - यदि तत्वों की एक समान संख्या है, तो माध्यिका वास्तव में मध्य दो तत्वों का औसत है। मध्य दो तत्व दोनों शीर्ष पर नहीं हो सकते। यह शायद एक व्यावहारिक एल्गोरिथ्म है, लेकिन चलो इसे वापस आते हैं।

• ढेर? एक ढेर वास्तव में बुनियादी आदेश और अधिकतम और मिनटों का ट्रैक रखने में अच्छा है। यह वास्तव में दिलचस्प है - यदि आपके पास दो ढेर हैं, तो आप बड़े आधे और छोटे आधे तत्वों का ट्रैक रख सकते हैं। बड़ा आधा एक मिनट के ढेर में रखा जाता है, जैसे कि बड़े आधे में सबसे छोटा तत्व जड़ में होता है। छोटा आधा अधिकतम ढेर में रखा जाता है, जैसे कि छोटे आधे का सबसे बड़ा तत्व जड़ में होता है। अब, इन डेटा संरचनाओं के साथ, आपके पास जड़ों पर संभावित औसत तत्व हैं। यदि ढेर अब समान आकार के नहीं हैं, तो आप एक ढेर को बंद करके और दूसरे पर इसे धकेलकर एक तत्व को तेजी से "असंतुलन" कर सकते हैं।

ध्यान दें कि आप जितनी अधिक समस्याएं करते हैं, उतनी ही आपकी वृत्ति विकसित होगी जिस पर डेटा संरचना लागू होगी। आप अधिक बारीक से बारीक वृत्ति भी विकसित करेंगे क्योंकि इनमें से कौन सा दृष्टिकोण सबसे उपयोगी है।


यदि फ़ाइल पाठ प्रारूप में है, तो आप इसे केवल पढ़े गए पूर्णांकों में परिवर्तित करके मेमोरी में फिट करने में सक्षम हो सकते हैं, क्योंकि पूर्णांक के रूप में संग्रहीत पूर्णांक एक पूर्णांक के रूप में संग्रहीत पूर्णांक की तुलना में अधिक स्थान ले सकता है, जो निर्भर करता है। पूर्णांकों का आकार और पाठ फ़ाइल का प्रकार। संपादित करें: आपने अपने मूल प्रश्न को संपादित किया; मैं अब देख सकता हूं कि आप उन्हें मेमोरी में नहीं पढ़ सकते, नीचे देखें।

यदि आप उन्हें स्मृति में नहीं पढ़ सकते हैं, तो यह वही है जो मैं लेकर आया हूं:

  1. आपके पास कितने पूर्णांक हैं। यह आप शुरू से जानते होंगे। यदि नहीं, तो यह केवल फ़ाइल के माध्यम से एक पास लेता है। बता दें ये एस।

  2. X सबसे बड़े पूर्णांकों को खोजने के लिए अपनी 2G मेमोरी का उपयोग करें (हालांकि बहुत से आप फिट हो सकते हैं)। आप फ़ाइल के माध्यम से एक पास कर सकते हैं, किसी तरह की क्रमबद्ध सूची में x को सबसे बड़ा रखते हुए, बाकी को छोड़ दें जैसे आप जाते हैं। अब आप एक्स-वें सबसे बड़े पूर्णांक को जानते हैं। आप एक्स-वें सबसे बड़े को छोड़कर इन सभी को त्याग सकते हैं, जिसे मैं X1 कहूंगा।

  3. एक और पास से गुजरें, अगले x सबसे बड़े पूर्णांकों को X1 से कम में खोजें, जिनमें से सबसे कम x2 है।

  4. मुझे लगता है कि आप देख सकते हैं कि मैं इसके साथ कहां जा रहा हूं। कुछ पास होने के बाद, आपने (S / 2) -सबसे बड़े पूर्णांक में पढ़ा होगा (आपको यह पता लगाना होगा कि आपने कितने पूर्णांक पाए हैं), जो कि आपका माध्य है। यदि S सम है तो आप दोनों को बीच में ही छोड़ देंगे।


यहाँ जावा में कार्यान्वित @Rex Kerr द्वारा वर्णित एल्गोरिदम है।

/**
 * Computes the median.
 * @param arr Array of strings, each element represents a distinct binary number and has the same number of bits (padded with leading zeroes if necessary)
 * @return the median (number of rank ceil((m+1)/2) ) of the array as a string
 */
static String computeMedian(String[] arr) {

    // rank of the median element
    int m = (int) Math.ceil((arr.length+1)/2.0);

    String bitMask = "";
    int zeroBin = 0;

    while (bitMask.length() < arr[0].length()) {

        // puts elements which conform to the bitMask into one of two buckets
        for (String curr : arr) {
            if (curr.startsWith(bitMask))
                if (curr.charAt(bitMask.length()) == '0')
                    zeroBin++;
        }

        // decides in which bucket the median is located
        if (zeroBin >= m)
            bitMask = bitMask.concat("0");
        else {
            m -= zeroBin;
            bitMask = bitMask.concat("1");
        }

        zeroBin = 0;
    }

    return bitMask;
}

एल्गोरिथ्म के कुछ परीक्षण मामलों और अपडेट here देखे जा सकते here





algorithm