जॉब इंटरव्यू एल्गोरिथम?
अद्यतन करें: क्या कोई मेरी अंतिम टिप्पणी का उत्तर दे सकता है। 'सर्वनाम' का उत्तर?
कृपया ध्यान दें: मैंने पहले भी यह पूछा है लेकिन यह पूरी तरह से गड़बड़ था इसलिए मैं इसे अधिक विवरण और मूल रूप में लिख रहा हूं।
सवाल:
मैं एन प्रतिभागियों के बीच एक वोट प्रणाली का प्रबंधन कर रहा हूं (प्रत्येक 1 से एन तक अनुक्रमित) जहां मैं निम्नलिखित कार्यों का समर्थन करना चाहता हूं:
- Init (N) - डेटा संरचना को प्रारंभ करें। -O (1)
- वोट (j, i) - परिणाम तालिका में उस व्यक्ति को जोड़ें जिसे मैंने व्यक्ति को वोट दिया था (वास्तव में 1) - जहां यह किसी को खुद को वोट करने की अनुमति नहीं है। -O (1)
- मतदाता (i) - मुझे वोट किए गए लोगों की संख्या लौटाएं। -O (1)
- उत्पत्ति (जे) - जो व्यक्ति दूसरों को दिया वोटों की संख्या लौटाएं। -O (1)
- इष्ट (के) - प्रिंट शीर्ष प्रतिभागियों (अवरोही क्रम में) उन्हें मिले वोटों की संख्या के अनुसार। -ठीक)
- परहेज () - सभी प्रतिभागियों को प्रिंट करें जिन्हें कोई वोट नहीं मिला। -ओ (आर) जहां आर मुद्रित प्रतिभागियों की संख्या है
इस प्रश्न में अंतरिक्ष की जटिलता O (N) होनी चाहिए ।
केवल सरणियों के उपयोग की अनुमति है, और (दोगुनी) लिंक की गई सूचियाँ।
मैंने क्या किया? मैंने 1-4 को इतनी आसानी से हल कर दिया कि एक ऐरे को घोषित कर दिया जिसका आकार N है और प्रत्येक सेल में मान शामिल हैं; gotऔर sent। जब iकरने के लिए वोट jमैं के लिए मूल्य मिल बढ़ jऔर के लिए मूल्य भेजा iएक एक करके।
फिर भी मुझे नहीं पता कि आवश्यक जटिलता में 5 और 6 को कैसे हल किया जाए।
नोट: मैं एक वास्तविक कोड के बजाय एल्गोरिथ्म / विचार की तलाश कर रहा हूं।
जवाब
ध्यान दें कि प्रत्येक ऑपरेशन के लिए, जिस उम्मीदवार को वोट दिया गया, उसने अपने स्कोर को बिल्कुल एक करके बढ़ा दिया।
यह एक नई रणनीति को खोलता है - एक उम्मीदवार को अपने स्कोर की मैपिंग करने के बजाय, इस स्कोर के साथ उम्मीदवारों की सूची में एक अंक मैप करें।
इसे सूची के उम्मीदवारों की सूची के रूप में काफी सरलता से लागू किया जा सकता है: (सिंटैक्स जैसे टेम्पलेट में list<list<Candidate>>)।
इसके अलावा, प्रत्येक अभ्यर्थी संख्या को वास्तविक Candidateतत्व के सूचक तक मैप करते हुए एक सरणी रखें ।
0 वाले उम्मीदवारों की सूची, प्रारंभिक रूप से सभी उम्मीदवारों के लिए सेट की जाएगी, इसी तरह से आप O (1) में एक सरणी को इनिशियलाइज़ करते हैं ।
- जब वोट डाला जाता है:
- आप संदर्भ से उम्मीदवार पाते हैं: O (1)
- आप इसे इसकी वर्तमान सूची से हटाते हैं, और इसे अगली सूची में जोड़ते हैं: O (1)
- समर्थन करने के लिए
Avoided()मेंO(r): "0" सूची में तत्वों की संख्या आधे से भी छोटा होता है, तो इसके बजाय एक नियमित रूप से सूची होने के लिए बदल जाते हैं। - यदि किसी स्कोर का प्रतिनिधित्व करने वाले पिछले तत्व के पास अब कोई उम्मीदवार नहीं है, तो उसे छोड़ें, और पिछले स्कोर को अगले एक से सीधे लिंक करें, (यानी यदि स्कोर 3 के साथ कोई उम्मीदवार नहीं है, तो कनेक्ट करें
2<->4) यहO(n)बहुत खाली सूची नोड्स नहीं होने के कारण स्थान सुनिश्चित करता है।
- TopK प्राप्त करना अब आसान है और
O(k)अंत से शुरू करने के लिए स्कोर सूची को पुन: व्यवस्थित करके (kउम्मीदवारों के उत्पादन के बाद रोक ) O(n) = O(r)टाल दिया जाता है अब अगर आधे से अधिक उम्मीदवारों को टाला गया, याO(r)अन्यथा प्रविष्टि में अनुकूलन (3) के लिए धन्यवाद।
यहाँ से बचने के लिए एक वैकल्पिक तरीका लागू किया गया है ()। प्रत्येक व्यक्ति के साथ दो नंबर संबद्ध करें, जिसे वोट दिया गया है, स्टार्ट-ऑफ़-रन और एंड-ऑफ़-रन। प्रारंभ में सभी तत्व Noneओ (1) सरणी आरंभीकरण चाल के साथ सेट किए जा सकते हैं।
जब व्यक्ति mको पहली बार वोट दिया जाता है, तो अपडेट startOfRunऔर endOfRunसरणियाँ:
if startOfRun[m-1] != None and startOfRun[m+1] == None
endOfRun[startOfRun[m-1]] = m
else if startOfRun[m-1] == None and startOfRun[m+1] != None
startOfRun[endOfRun[m+1]]
else if startOfRun[m-1] != None and startOfRun[m+1] != None
endOfRun[startOfRun[m-1]] = endOfRun[m+1]
startOfRun[endOfRun[m+1]] = startOfRun[m-1]
else
startOfRun[m] = m
endOfRun[m] = m
(बढ़त की स्थिति संक्षिप्तता के लिए छोड़ दी गई)।
अब आपके पास ऐसे व्यक्तियों के रन हैं जिन्हें वोट दिया गया था, और आप प्रत्येक रन के अंत में शुरू से अंत तक आसानी से प्राप्त कर सकते हैं। रनों के अंदर नंबर सभी गलत हैं, लेकिन हम उनके बारे में परवाह नहीं करते हैं। O (r) रन हैं, इसलिए आप उन सभी को छोड़ सकते हैं जिन्हें O (r) में वोट दिया गया था।
यहां इष्ट () लागू करने का एक वैकल्पिक तरीका है। दो सरणियाँ हैं, (1) स्कोर के आधार पर छांटे गए व्यक्तियों का एक विस्तार सरणी है, और (2) पहले अंक में अंतिम व्यक्ति के सूचकांक के स्कोर से एक नक्शा है जिसमें स्कोर उससे कम नहीं है (यदि ऐसा कोई व्यक्ति नहीं है, तो None) । प्रारंभ में पहला सरणी खाली है और दूसरे में Nones है। उदाहरण:
(array 1)
(index) 1 2 3 4 5 6 7 8 9
person 3 6 5 1 4 2 8 9 7
score 7 7 7 5 5 3 2 2 2
(array 2)
score 1 2 3 4 5 6 7 8 9
index in 1st 9 9 6 5 5 3 3 - -
एक बार जब किसी व्यक्ति को पहली बार वोट दिया जाता है, तो इसे 1 के स्कोर के साथ सरणी के अंत में जोड़ा जाता है, और array2[1]इसे अपडेट किया जाता है। एक बार जब व्यक्ति को फिर से वोट दिया जाता है, तो उसे उसी स्कोर वाले पहले व्यक्ति के साथ स्वैप किया जाता है, स्कोर बढ़ाया जाता है, और दूसरा सरणी अपडेट किया जाता है (हमें केवल एक तत्व को अपडेट करने की आवश्यकता है, वह जो नए से मेल खाता है स्कोर)।