देखते हुए एन के साथ एक चक्र के दायरे के बाहर अंक और एक बिंदु एम परिभाषित, मुद्दा यह है कि है एन ओ के सेट के बीच एम के सबसे करीब (logn)

Question

http://www.glassdoor.com/Interview/Google-Interview-RVW2382108.htm

मैं के लिए एक समाधान के साथ आने की कोशिश की है लगता है यह समस्या। लेकिन मैं सफल नहीं हुआ .. क्या कोई मुझे इस समस्या से आगे बढ़ने के लिए संकेत दे सकता है।

मैं दो अंक प्रत्येक के 2 जोड़ी ले जाएगा। यही है, मैं 2 तार बनाऊंगा। उनके लंबवत द्विभाजक का पता लगाएं। उन समद्विभाजक का उपयोग करना, मैं चक्र के केंद्र में पता लगाना होगा ...

इसके अलावा, मैं चक्र के समीकरण के साथ ऊपर आ जाएगा। और सर्कल के साथ बिंदु एम के चौराहे का बिंदु खोजें ... यह निकटतम बिंदु होना चाहिए। हालांकि, उस बिंदु या एन के सेट में मौजूद नहीं हो सकता है कहते हैं

धन्यवाद।

Answer 1

मानते हैं कि सर्कल की परिधि पर बिंदु "इन-ऑर्डर" हैं (यानी सर्कल के केंद्र के कोण से क्रमबद्ध) आप कोण-आधारित बाइनरी खोज का उपयोग कर सकते हैं, जिसे O(log(n)) सीमाएं प्राप्त करनी चाहिए।

1. चक्र के केंद्र इंगित M से कोण A की गणना - O(1)। O(log(n)) -
2. उपयोग द्विआधारी खोज सबसे बड़ा कोण A से भी कम समय के साथ परिधि पर बिंदु I खोजने के लिए।
3. हलकों के बाद से M के लिए निकटतम बिंदु उत्तल रहे हैं या तो I या I+1 है। दोनों की दूरी की गणना करें और न्यूनतम - O(1) लें।

Answer 2

एक बिंदु एम के सबसे करीब के लिए, हम प्लानर कटौती के आधार पर अंक की बाइनरी उन्मूलन करने की ज़रूरत है। जिसके बाद हम एक बिंदु किसी भी बिन्दु एम के सबसे करीब ओ (LGN) समय में प्राप्त कर सकते हैं इनपुट अंकों की एक छोटी सी पूर्व प्रसंस्करण की जरूरत है।

1. की गणना (यदि नहीं दिया) (r, θ) प्रारूप में अंकों की ध्रुवीय प्रतिनिधित्व जहां r केंद्र और θ से दूरी है रेंज (-180,180] में x- अक्ष से कोण है।
2. x- अक्ष से उनके कोण के बढते क्रम में सभी क्रमबद्ध एन अंक।

ध्यान दें कि एक एम के सबसे करीब बिंदु के सरल द्विआधारी खोज यहाँ काम नहीं करेगा, जैसे,

• दिए गए अंक हैं सॉर्ट किया गया कि θ = (-130, -100 , -90, -23, -15,0,2,14,170), फिर θ = -170 के साथ एक बिंदु एम के लिए, बाइनरी खोज -130 (40 डिग्री दूर) को निकटतम बिंदु के रूप में देगी जबकि 170 (20 डिग्री दूर) एम
• का सबसे नज़दीकी बिंदु है अगर हम सॉर्ट करते समय साइन को अनदेखा करते हैं (सोचते हैं कि यह सही आउटपुट उत्पन्न करेगा), हमारी नई सॉर्टेड सरणी θ = (0,2,14,15,23,90,100,130,170) की तरह दिखाई देगी, θ = -6 के साथ एक बिंदु एम के लिए बाइनरी खोज परिणाम उत्पन्न करेगा 2 या 14 होना चाहिए जबकि 0 इस मामले में एम के निकटतम बिंदु है।

प्लानर कटौती का उपयोग कर तलाशी अभियान करने के लिए,

• ढूँढें प्लानर कटौती लाइन चक्र के केंद्र के माध्यम से और बिंदु के साथ चक्र के केंद्र को जोड़ने लाइन करने के लिए खड़ा गुजर एम
• को हटा दें सर्कुलर प्लेन का आधा [9 0 + θ, -90 + θ) या [-90 + θ, 90 + θ) जिस पर विमान एम का आधा हिस्सा है।
• पहले कट के समानांतर प्लानर कटौती करें और पिछले विमान के बीच में बिंदु के माध्यम से गुजरना और विमान के आधे हिस्से में सभी बिंदुओं को एम से आगे तक हटाएं जब तक कि विमान के नजदीकी हिस्से में कोई बिंदु न छोड़े, इस मामले में विमान के करीब आधे को खत्म करें।
• विमानों को काटने पर रखें जब तक कि हम एक बिंदु से नहीं छोड़े जाते। वह बिंदु एम के निकटतम बिंदु है। कुल ऑपरेशन ओ (एलएनजी) चरणों को लेता है।

मामले में डेटा विषम और समान रूप से सर्कल में फैल नहीं है, हम ऐसी है कि प्रत्येक कट उन बिंदुओं की औसत (कोण के आधार पर), जो छोड़ दिया जाता है के माध्यम से गुजरता हमारे प्लानर कटौती अनुकूलन कर सकते हैं खोज ऑपरेशन में।