java - मिलियन संख्याओं में केवल एक बार दोबारा नंबर ढूंढें




algorithm duplicates (2)

एडोब साक्षात्कार में हाल ही में मुझे यह पहेली मांगी गई: - एक सरणी जिसमें अनारक्षित सकारात्मक संख्या शामिल है, जहां सभी तत्व एक नंबर के अलावा अलग हैं, जो वास्तव में दो बार होता है। मकसद यह पता लगाना है कि अधिकतम इष्टतम रास्ते में दो बार बार आना

पी एस बिल्कुल कोई ऑर्डर नहीं / पैटर्न सरणी पर लागू होता है।

साक्षात्कारकर्ता ने किसी भी तरह की संभावना को खारिज कर दिया क्योंकि उसमें बहुत समय लगेगा, वह एक पहेली के रूप में लेना चाहते थे और फिर एक चालाक समाधान प्रस्तावित करते थे


जैसा कि डेटा क्रमबद्ध नहीं है, आपको प्रत्येक संख्या को शेष (एन -1) के विरुद्ध O (n ^ 2) के अनुसार चेक करना होगा। वे ऐसे एल्गोरिथम के लिए पूछ रहे हैं जिसकी समय जटिलता O (n ^ 2) से कम है इसके लिए आपको पेड़ या हैश तालिका की आवश्यकता है यदि आप उस डेटा को सॉर्ट करते हैं और फिर कोई एल्गोरिथम लागू करते हैं तो यह अधिक समय लेने वाली प्रक्रिया होगी। दोनों पेड़ और हैश तालिका के लिए आपको ओ (एन) की आवश्यकता होगी चूंकि वे आंकड़ों को व्यवस्थित करने और डेटा खोजने के लिए श्रेष्ठ हैं।


पहला तरीका सिर्फ सरणी को ठीक करना होगा, तब तक सॉर्ट किए गए डेटा के माध्यम से जाने तक आपको दो समान लगातार संख्याएं नहीं मिलेंगी। यह आसानी से O(n log n) समय और O(1) अंतरिक्ष में किया जा सकता है

यदि साक्षात्कारकर्ता ने तब पूछा कि क्या बेहतर तरीका है, तो आप डेटा पर हो सकता है कि किसी भी सीमाओं पर चर्चा करेंगे (क्रम / पैटर्न आवश्यक रूप से डेटा पर कोई सीमाएं नहीं दर्शाते हैं) आपको उन प्रश्नों को भी पूछना चाहिए जो वास्तव में इष्टतम से होते हैं - शब्द का मतलब किसी भी मात्रा के बिना मापा जा रहा है।

कुछ लोग समय के लिए अनुकूलित करते हैं, अंतरिक्ष के लिए कुछ, कुछ (जैसे मेरे) भी कोड पठनीयता के लिए अनुकूलित :-)

सीमाओं पर चर्चा के संदर्भ में, एक उदाहरण होगा यदि संख्याओं की सीमा कई लाख तक सीमित थी। फिर यह गणना की एक सरणी बनाने और O(n) समय के सभी डेटा की तरह कुछ के साथ प्रक्रिया करने के लिए एक सरल मामला होगा:

dim array[several million] as zero
for each number:
    array[number]++
    if array[number] == 2:
        print number
        stop

यहां तक ​​कि इस तरह की सीमा के बिना , एक 32-बिट संख्या सीमा चार अरब या उससे अधिक बिट (लगभग 500 एम) की एक सरणी का उपयोग कर सकती है, और वह समय के लिए व्यापारिक स्थान का आपका क्लासिक उदाहरण है

ध्यान रखें कि साक्षात्कार के सवाल यह समझने की कोशिश नहीं कर रहे हैं कि अगर आपके पास किसी समस्या का हल है, तो वे साक्षात्कारकर्ता आपकी सोच प्रक्रियाओं को देख सकते हैं। अधिक बार नहीं, आपकी सबसे बड़ी संपत्ति एल्गोरिदम का एक ज्ञानकोश संबंधी ज्ञान नहीं है, आप समस्याओं के बारे में समझदारी से सोचने की क्षमता और उन्हें कैसे हल कर सकते हैं।





puzzle