duplicates बेसिक हैशटेबल एल्गोरिथ्म-डुप्लिकेट को निकालने



hashtable (1)

मुझे आज सुबह एक साक्षात्कार हुआ था और मुझे "इंटिजर्स की सूची से डुप्लिकेट निकालने के लिए एक एल्गोरिथ्म दें" दिया गया था। यह एक काफी मानक प्रश्न है, इसलिए मैं बहुत आश्वस्त था कि मैं इसका जवाब दे सकता हूं।

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

तो साक्षात्कारकर्ता ने जवाब दिया (फिर से मैं परावर्तन करता हूं) "लेकिन हैशटेबल लुकअप निरंतर समय नहीं हैं, वे निर्भर करते हैं कि इसमें कितने तत्व पहले से मौजूद हैं। आपके द्वारा वर्णित एल्गोरिदम ओ (एन ^ 2) होगा"

तो मैंने जवाब दिया "वास्तव में? मैंने सोचा था कि अगर आपने एक अच्छा हैश-फ़ंक्शन बनाया है, तो यह लगातार समय होगा? इसे ओ (एन) को आमतौर पर"

तो साक्षात्कारकर्ता ने जवाब दिया "तो आप कह रहे हैं कि लुकअप समय कई प्रविष्टियों के साथ हैश तालिका के लिए और कुछ प्रविष्टियों के साथ एक हैशटेबल होगा"

फिर मैंने कहा, "हाँ, अगर यह सही तरीके से तैयार किया गया है।"

तब साक्षात्कारकर्ता ने कहा "यह सच नहीं है"

तो मैं अभी बहुत उलझन में हूँ अगर कोई मुझे बताता है कि मैं गलत कहां हूं, तो मैं बहुत आभारी रहूंगा


अगर कोई मुझे बता सकता है कि मैं गलत कहां हूं

आप बिल्कुल भी गलत नहीं हैं: ठीक से डिज़ाइन किया गया हैश टेबल आपको O(1) की अपेक्षित लुकअप कार्यवाही देते हैं और परिशोधित O(1) में सम्मिलित करते हैं, इसलिए आपका एल्गोरिथ्म O(N) । भारी लोड किए गए हैश तालिका में लुक-अप संभवतः डुप्लिकेट रिजॉल्यूशन के कारण थोड़ा धीमा होता है, लेकिन अपेक्षित लुकअप समय O(1) रहता है। यह वास्तविक समय प्रणालियों के लिए पर्याप्त नहीं हो सकता है जहां "परिशोधित" गिनती नहीं होती है, लेकिन सभी व्यावहारिक स्थितियों में यह पर्याप्त है

बेशक आप उन वस्तुओं के लिए हमेशा एक संतुलित पेड़ का उपयोग कर सकते हैं जिन्हें आपने सबसे खराब-केस O(N*LogN) एल्गोरिथ्म के लिए देखा है, या यदि संख्या में उचित सीमा है (0, 100,000 के बीच में कहें) तो आप बूलियन का उपयोग कर सकते हैं O(1) सबसे खराब स्थिति में सदस्यता का परीक्षण करने के लिए सरणी, और एक छोटे स्थिर गुणक की वजह से हैश तालिका के ऊपर एक संभावित सुधार।