साक्षात्कार:

Question

मिलान लोग पर मैं एक फर्म है कि ने कहा कि के लिए हाल ही में इस साक्षात्कार सवाल देखा:

लोगों का समूह है, तो आप i वें व्यक्ति j वें जानता है पूछने के लिए Know(i, j) कॉल कर सकते हैं, वापसी मान true है (i जानता है j) या false (ij नहीं जानता)। उस व्यक्ति को ढूंढें कि हर कोई उसे जानता है लेकिन वह किसी को भी नहीं जानता है।

मैं O(N^2) कार्यान्वयन के बारे में सोच सकता हूं जैसे कि आप हर व्यक्ति के साथ विधि के साथ हर व्यक्ति से मेल खाते हैं, जो किसी को वास्तव में किसी को जानता है। हालांकि मैं इससे तेज कार्यान्वयन के बारे में नहीं सोच सकता।

क्या कोई भी मदद या संकेत दे सकता है?

Answer 1

हम इसे एक सरल एल्गोरिदम के साथ रैखिक समय में कर सकते हैं। दो लुकअप में, हम कम से कम एक उम्मीदवार को खत्म कर सकते हैं - दो व्यक्तियों को चुनें, और iKnow(i,j) या ~Know(j,i) के साथ व्यक्ति को हटा दें।

Answer 2

सभी हम क्या करना है है -

1. एक व्यक्ति जो किसी और को पता नहीं है
2. और फिर जाँच हर किसी को उस व्यक्ति जानता है

चरण 1 जानकारी प्राप्त करें: का पता लगाएं एक ऐसे व्यक्ति को बाहर करें जो किसी और को नहीं जानता। प्रारंभ में हर कोई हमारे उम्मीदवार है। तो चलिए किसी भी एक के साथ वर्तमान नोड के रूप में शुरू करते हैं। सभी उम्मीदवारों पर Iterate जे। यदि जानता है (i, j) गलत है। तब जे हमारे उम्मीदवार नहीं हो सकता है। तो उम्मीदवारों से जे हटा दें। यदि जानता है (i, j) किसी भी जे के लिए सच है, तो मैं हमारे उम्मीदवार नहीं बन सकता, इसलिए वर्तमान नोड को जे अपडेट किया जाएगा, और नोड i को हटा दें। इसे तब तक दोहराएं जब तक हम वर्तमान नोड अपडेट नहीं कर सकते। अंतिम वर्तमान नोड हमारा अंतिम उम्मीदवार है। यह वास्तव में ओ (एन) होगा क्योंकि प्रत्येक चरण में हम वास्तव में एक नोड को हटा रहे हैं, या तो मैं या जे।

चरण 2: हमें एक ऐसा व्यक्ति मिला जो किसी और को नहीं जानता। लेकिन हमें यह सत्यापित करना है कि हर कोई उसे जानता है। हम बस क्या कर सकते हैं सभी नोड्स पर जांच करें और जांचें, जो ओ (एन) है। अगर हमने पाया कि यह हमारा नोड नहीं है, तो ऐसा कोई समाधान नहीं है। क्योंकि कोई दूसरा नोड नहीं हो सकता है, जो समाधान है, क्योंकि मुझे के बारे में पता नहीं है।

हम उम्मीदवारों की सूची संग्रहित करने के लिए एक लिंक सूची का उपयोग कर सकते हैं ताकि उम्मीदवार को हटाया जा सके (1)।

Answer 3

while there are at least two candidate people remaining: 
    if Know(i, j) then 
     i is not the solution - remove from list of candidates 
    else 
     j is not the solution - remove from list of candidates 

पिछले आदमी खड़ा (wo) है समाधान ....

उपयोग में डेटा संरचनाओं यह स्पष्ट है कि "को दूर करने के लिए" एक उम्मीदवार नहीं बनाते हैं, एक सरणी पर एक पाश कर सकते हैं इस्तेमाल किया जा सकता है:

int candidate = 0; 
for (int i = 1; i < n; ++i) 
    if (know(candidate, i)) 
     candidate = i; 
// candidate now holds the solution...