गतिशील रूप से बदल रहे शब्दों की एक बड़ी फ़ाइल है। हम लगातार इसमें कुछ शब्द जोड़ रहे हैं। आप प्रत्येक पल में शीर्ष 10 प्रवृत्त शब्दों का ट्रैक कैसे रखेंगे?अमेज़ॅन साक्षात्कार प्रोब
मुझे यह प्रश्न ब्लॉग में मिला लेकिन मुझे जवाब समझ में नहीं आया। उत्तर है: हैश तालिका + न्यूनतम-ढेर
मुझे समझ में आता है कि हैशटेबल क्यों नहीं, लेकिन न्यूनतम ढेर भाग नहीं, क्या कोई मेरी मदद कर सकता है?
यदि यह top 10 trending words है तो आपको hash-table के साथ max-heap का उपयोग करना चाहिए।
जब एक नया शब्द फ़ाइल तब से जोड़ा जाता है:
Create एक नए तत्व x.key=word और x.count=1 साथ x।Addxhash-table पर। O(1)।Addxmax-heap पर। O(lgn)।जब एक मौजूदा शब्द फ़ाइल तब से जोड़ा जाता है:
Findhash-table में x। O(1)।Updatex.count से x.count++।जब top 10 trending words तो पुनः प्राप्त करने की आवश्यकता है:
max-heap से
Extract 10 बार। 10*O(lgn)=O(10*lgn)=O(lgn)।जैसा कि आप देख सकते हैं, सभी आवश्यक संचालन अधिकांश O(lgn) पर किए जाते हैं।
आप एक न्यूनतम ढेर का उपयोग करना चाहते हैं: जब एक मौजूदा शब्द जो शीर्ष 10 में नहीं है शीर्ष 10 बन जाता है, मिनट को हटाकर लगातार समय होगा। – aw626
"अधिकतम-ढेर में x.count से x.count ++ अपडेट करें" - क्या यह 'ओ (एन) 'नहीं होना चाहिए? आपको पहले 'अधिकतम-ढेर' में 'x' खोजना होगा, लेकिन आप नहीं जानते कि यह कहां है।एक बार जब आप इसे पा लेते हैं, इसे बढ़ाते हैं और इसे बुलबुला करते हैं तो 'ओ (एलएनजी)' ऑपरेशन होता है। –
@ बी-कॉन: चूंकि 'अधिकतम-ढेर' और 'हैश-टेबल' उसी तत्व 'x' पर इंगित करता है, फिर हैश तालिका में इसे फिर से ढूंढने की आवश्यकता नहीं है। मैं इसे ठीक कर दूंगा, धन्यवाद। –
यदि आप केवल शीर्ष 10 रखना चाहते हैं, तो अधिकतम-ढेर का उपयोग करके ओवरकिल अधिक है। एक क्रमबद्ध सरणी में 10 प्रविष्टियों को रखना सरल और तेज़ होगा।
सॉर्टिंग के लिए, सरणी के नीचे से प्रविष्टि प्रकार का उपयोग करें। आपको उस मामले की जांच करनी होगी जहां उम्मीदवार पहले से ही शीर्ष दस पर अपनी स्थिति को अपडेट कर रहा है।
यदि आप अन्य प्रविष्टियां नहीं रखते हैं, तो कोई भी नई प्रविष्टि इसे शीर्ष 10 तक नहीं बनायेगी। –
@ करोलो हॉर्वथ: जाहिर है कि आपको प्रति प्रविष्टि हिट की गणना करने के लिए अभी भी हैश तालिका की आवश्यकता है। मेरा मुद्दा यह है कि शीर्ष 10 प्रविष्टियों के प्रबंधन के लिए एक मिनी-ढेर का उपयोग करना अधिक है। एक सरल क्रमबद्ध सरणी बेहतर प्रदर्शन करेगी और कार्यान्वयन भी काफी आसान होगा। दरअसल, एक वृद्धिशील रूप से अद्यतन टॉप-एन (और जब तक आपके पास बड़े संबंध नहीं होते हैं) के लिए एक क्रमबद्ध सरणी हमेशा एक मिनी-ढेर से बेहतर प्रदर्शन करेगी। – salva
आप आमतौर पर उच्चतम एन उत्तरों का ट्रैक रखने के लिए एक न्यूनतम ढेर चाहते हैं, क्योंकि प्रत्येक चरण में आपके पास उम्मीदवार का उत्तर होता है और आप जानना चाहते हैं कि यह मिनी-ढेर में सबसे खराब जवाब से बेहतर है या नहीं - अगर यह है , मिनी-ढेर से शीर्ष एन का सबसे खराब जवाब हटाएं और उम्मीदवार को सम्मिलित करें। अंतर्ज्ञानी होने के कारण - अधिकतम-ढेर बहुत अच्छे उत्तर को चुनना बहुत आसान बनाता है, लेकिन यह तय करते समय कि कोई नया उम्मीदवार उत्तर स्वीकार करना है या नहीं, यह वही नहीं है जो आप चाहते हैं। (बस याद रखें कि जब आप अंत में शीर्ष एन उत्तरों निकालते हैं, तो वे पहले उन सबसे खराब एन के साथ आ जाएंगे)। – mcdowella