किसी लिंक्ड सूची में भ्रष्टाचार ढूँढना

Question

मेरे पास डेवलपर की स्थिति के लिए आज एक साक्षात्कार था और मुझे एक दिलचस्प तकनीकी सवाल पूछा गया कि मुझे इसका जवाब नहीं पता था। मैं यह देखने के लिए यहां पूछूंगा कि कोई मुझे मेरी जिज्ञासा के लिए समाधान प्रदान कर सकता है या नहीं। यह एक बहु-पक्ष प्रश्न है:

1) आपको 100 तत्वों (पूर्णांक और अगले नोड के लिए एक सूचक) के साथ एकमात्र लिंक की गई सूची दी गई है, यह पता लगाने का एक तरीका ढूंढें कि क्या लिंक के माध्यम से ब्रेक या भ्रष्टाचार आधा है सूची? आप लिंक की गई सूची के साथ कुछ भी कर सकते हैं। ध्यान दें कि आपको इसे सूची में करना चाहिए क्योंकि यह पुनरावृत्त है और यह सत्यापित करने से पहले यह सत्यापन है कि सूची में इसके साथ कोई समस्या है।

मान लीजिए कि लिंक्ड सूची में ब्रेक 50 वें तत्व पर है, पूर्णांक या यहां तक ​​कि पॉइंटर अगले नोड (51 वें तत्व) पर एक कचरा मूल्य को इंगित कर सकता है जो आवश्यक रूप से एक अमान्य पता नहीं है।

2) ध्यान दें कि यदि लिंक की गई सूची में भ्रष्टाचार है, तो आप डेटा हानि को कम कैसे करेंगे?

Answer 1

"दूषित" पूर्णांक के परीक्षण के लिए, आपको यह जानना होगा कि मान्य मानों की सीमा क्या है। अन्यथा, यह निर्धारित करने का कोई तरीका नहीं है कि किसी भी दिए गए (हस्ताक्षरित) पूर्णांक में मान अमान्य है। इसलिए, मान लें कि आपके पास int के लिए वैधता परीक्षण है, तो आप हमेशा अगले तत्व को पुन: प्रारंभ करने से पहले उस मान की जांच करेंगे।

दूषित पॉइंटर के लिए परीक्षण करना कठिन है - शुरुआत के लिए, आपको यह करने की आवश्यकता है कि आप इसे संदर्भित करने का प्रयास करने से पहले पॉइंटर के मूल्य को अगले तत्व में जांचें, और सुनिश्चित करें कि यह एक वैध ढेर पता है। वह एक सेगमेंटेशन गलती से बच जाएगा। अगली बात यह सत्यापित करना है कि पॉइंटर पॉइंट वास्तव में एक वैध लिंक्ड सूची नोड तत्व है - यह थोड़ा सा ट्रिकियर है? शायद पॉइंटर को सूची तत्व वर्ग/संरचना में संदर्भित करें, और int और "अगला" पॉइंटर की वैधता का परीक्षण करें, यदि वे भी अच्छे हैं, तो यह सुनिश्चित हो सकता है कि पिछला नोड भी अच्छा था।

2), एक दूषित नोड की खोज करने के बाद, [यदि अगला पॉइंटर दूषित हो गया है] आपको क्या करना चाहिए, उसे पिछले नोड के "अगले सूचक" को तुरंत 'न्यूल' पर सेट करना है, इसे इसे अंत के रूप में चिह्नित करना सूची, और अपनी त्रुटि आदि लॉग इन आदिअगर भ्रष्टाचार केवल पूर्णांक मान के लिए था, लेकिन "अगले" तत्व सूचक के लिए नहीं, तो आपको उस तत्व को सूची से हटा देना चाहिए और इसके बजाय पिछले और निम्नलिखित नोड्स को एक साथ जोड़ना चाहिए - बाकी सूची को दूर करने की आवश्यकता नहीं है उस स्तिथि में!

Answer 2

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

या कुछ लिंक जानकारी डबल करें, यानी प्रत्येक नोड में अगले नोड के बाद नोड का पता संग्रहीत करें, जैसे कि यदि कोई लिंक टूटा हुआ हो तो आप पुनर्प्राप्त कर सकते हैं।

एकमात्र समस्या यह है कि मुझे लगता है कि आपको सेगमेंटेशन दोषों से बचना है।

Answer 3

चूंकि तत्वों की संख्या (100) ज्ञात है, 100 वें नोड में एक शून्य सूचक होना चाहिए। यदि ऐसा होता है, तो कुछ अच्छी संभावना के साथ सूची मान्य है (इसकी गारंटी नहीं दी जा सकती है, उदाहरण के लिए, 99 वां नोड दूषित है और सभी शून्यों के साथ कुछ स्मृति स्थान को इंगित करता है)। अन्यथा, कुछ समस्या है (इसे एक तथ्य के रूप में वापस किया जा सकता है)।

upd: इसके अलावा, यह संभव करने के लिए, एक हर कदम कुछ संरचनाओं अगर सूचक दिया delete का प्रयोग करेंगे देखो हो सकता है,, लेकिन delete का उपयोग कर के बाद से ही किसी भी अर्थ में सुरक्षित नहीं है, इसलिए ऐसा करना होने जा रहा है विशिष्ट।

Answer 4

पहले भाग के लिए - नए ऑपरेटर को अधिभारित करें। जब कभी भी एक नया नोड आवंटित किया जाता है तो नोड के पहले और बाद में कुछ अतिरिक्त स्थान आवंटित किया जाता है और वहां कुछ ज्ञात मान डालते हैं। ट्रैवर्सल में प्रत्येक नोड को चेक किया जा सकता है यदि यह ज्ञात मानों के बीच है।

Answer 5

यदि आप लिंक की गई सूची में कुछ भी कर सकते हैं, तो आप प्रत्येक तत्व के चेकसम की गणना करने और इसे तत्व पर संग्रहीत करने के लिए क्या कर सकते हैं। इस तरह आप भ्रष्टाचार का पता लगाने में सक्षम होंगे भले ही यह तत्व पर एक छोटी सी त्रुटि हो।

डेटा हानि को कम करने के लिए शायद आप पिछले तत्व में अगली पीआरटी को संग्रहीत करने पर विचार कर सकते हैं, इस तरह यदि आपका वर्तमान तत्व दूषित हो गया है, तो आप हमेशा पिछले तत्व का स्थान हमेशा से ढूंढ सकते हैं।

Answer 6

यह एक आसान सवाल है, और कई संभावित उत्तर हैं। प्रत्येक दक्षता के साथ मजबूती से व्यापार करता है। चूंकि बढ़ी हुई मजबूती से पूछे जाने वाले प्रश्न की एक शर्त है, ऐसे समाधान उपलब्ध हैं जो दोनों समय बलिदान करते हैं (सूची ट्रैवर्सल गति, साथ ही सम्मिलन की गति और नोड्स को हटाने की गति) या वैकल्पिक रूप से स्थान (प्रत्येक नोड के साथ अतिरिक्त जानकारी संग्रहीत)। अब समस्या यह बताई गई है कि यह लंबाई 100 की एक निश्चित सूची है, इस स्थिति में एक लिंक्ड सूची की डेटा संरचना सबसे अनुचित है। पहेली को थोड़ा और चुनौतीपूर्ण क्यों नहीं बनाते और कहते हैं कि सूची का आकार प्राथमिकता ज्ञात नहीं है?