फ़ाइल में दो पंक्तियां खोजें जो

Question

मुझे इस प्रश्न को अमेज़ॅन साक्षात्कार में पूछा गया था।

आपके पास कई लाइनों वाली एक फ़ाइल है लेकिन दो पंक्तियां समान हैं। उन दो लाइनों को खोजें। मैंने स्पष्ट उत्तर दिया जो एन^2 समय में भाग गया। तब मैं एक जवाब के साथ आया जिसने एक हैश टेबल का उपयोग किया, लेकिन उन्हें उस जवाब को पसंद नहीं आया क्योंकि वे कहते हैं कि यह फ़ाइल काम नहीं करेगा अगर फ़ाइल गीगाबाइट्स में थी। एक और जवाब जो मैं आया था, हैश परिणाम को स्मृति में संग्रहीत करने के बजाय, हैश वैल्यू के समान नाम वाली फ़ाइल बनाएं, और फ़ाइल में उसी ही हैश मान के साथ लाइनों को स्टोर करें। या तो वे मेरे समाधान को समझ नहीं पाए थे या उन्हें यह पसंद नहीं आया।

कोई विचार?

धन्यवाद

लाइनों और प्रत्येक पंक्ति का गणना लंबाई के माध्यम से

Answer 1

मैं इस समस्या के समाधान के दो आवश्यक वर्गों के बारे में सोच सकते हैं:

1. संभाव्य में स्मृति समाधान। आप मुख्य स्मृति में फ़ाइल की लाइनों का सारांश संग्रहीत करके इस समस्या को हल करने का प्रयास कर सकते हैं। फिर आप संभावित डुप्लिकेट की पहचान करने के लिए मुख्य स्मृति में गणना कर सकते हैं, फिर डिस्क पर वापस देखकर प्रत्येक संभावित डुप्लिकेट जांचें। ये समाधान शायद सबसे अच्छे हैं, क्योंकि उनके पास कम मेमोरी उपयोग, उच्च दक्षता, और डिस्क एक्सेस को कम करना है। इस श्रेणी में समाधानों में

   1. फ़ाइल की प्रत्येक पंक्ति के हैश की गणना करें, फिर हैश स्टोर करें। हैश टकराव वाली कोई भी रेखाएं लाइनों की एक संभावित जोड़ी का प्रतिनिधित्व करती हैं जो टकरा सकती है, और केवल उन पंक्तियों का पता लगाया जा सकता है।
   2. फ़ाइल की सभी पंक्तियों को स्टोर करने के लिए ब्लूम फ़िल्टर का उपयोग करें, फिर ब्लूम फ़िल्टर में टकराने वाले जोड़े को चेक करें। यह अनिवार्य रूप से एक भिन्नता है (1) जो अधिक अंतरिक्ष-कुशल है।

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

   1. फ़ाइल सॉर्ट करने के लिए एक बाहरी छंटाई एल्गोरिथ्म (बाहरी quicksort, बाहरी मूलांक प्रकार, आदि) का उपयोग करें, फिर डुप्लिकेट तत्वों की एक जोड़ी के लिए यह खोज रैखिक शामिल हैं।
   2. सभी डिस्क पर बी-पेड़ की तरह ऑन-डिस्क डेटा संरचना बनाएं, फिर बी-पेड़ से पूछें। इसमें बहुत से प्रीप्रोकैसिंग समय लगते हैं, लेकिन फ़ाइल पर भविष्य के संचालन को बहुत तेज बनाता है।
   3. डेटाबेस में सब कुछ डालें और डेटाबेस से पूछें।

आशा है कि इससे मदद मिलती है!

Answer 2

भागो। आप कुछ के साथ समाप्त हो जाएंगे:

0: 4 
1: 6 
2: 10 
3: 4 
.... 

समान लंबाई वाली थूज़ लाइनों की तुलना करें। इस तरह के इंडेक्स के साथ काम करना और अनुकूलित किया जा सकता है (उदाहरण के लिए एक फ्लैट सरणी में सबकुछ संग्रहित नहीं करना, लेकिन किसी प्रकार के पेड़ में, या जो भी हो)।

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

http://en.wikipedia.org/wiki/Bloom_filter

तो फिर तुम पता लगा सकते हैं लाइनों कि दोहराया जाता है (कुछ गलत परिणामों की) स्मृति में तो स्टोर, और उसके बाद एक बार फिर से फ़ाइल के माध्यम से जाना:

Answer 3

आप एक ब्लूम फिल्टर का उपयोग कर सकते हैं। फ़ाइल, बहुत कम स्मृति के उपयोग के माध्यम से

दो गुजरता, सुंदर