कोडिंग इंटरव्यू: पलिंड्रोम बनाने के लिए न्यूनतम आसन्न (adjacent) स्वैप्स

प्रॉम्प्ट और संदर्भ

प्रत्येक आसन्न स्वैप की लागत एक होती है। वर्ण दोहराए जा सकते हैं, और जब एक से अधिक वर्णों की आवृत्ति विषम (odd) होती है, तो इनपुट असंभव हो सकता है। लक्ष्य न्यूनतम स्वैप्स की संख्या ज्ञात करना है, न कि केवल कोई भी पलिंड्रोम बनाना।

इंटरव्यूअर क्या जांचता है

• विषम-आवृत्ति वाली साध्यता (feasibility) शर्त प्राप्त करना।
• बाईं ओर के वर्ण को दाईं ओर से निकटतम उपयुक्त साझेदार के साथ मिलाना।
• यह सिद्ध करना कि ग्रीडी विकल्प इष्टतम (optimal) क्यों है और शिफ्ट्स का हिसाब रखना।

उत्तर देने से पहले स्पष्ट करने वाले प्रश्न

• क्या स्वैप्स केवल आसन्न हैं, और क्या प्रत्येक स्वैप की लागत एक है?
• क्या वर्णमाला मनमानी है, और क्या यूनिकोड कोड पॉइंट्स को वर्ण माना जाता है?
• क्या फ़ंक्शन को किसी ऐरे को म्यूटेट करना चाहिए या केवल गिनती लौटानी चाहिए?
• किस इनपुट आकार से यह निर्धारित होता है कि O(n²) दृष्टिकोण स्वीकार्य है या नहीं?

30-सेकंड का उत्तर ढांचा

पहले विषम आवृत्तियों की गणना करें; एक से अधिक विषम गणना पलिंड्रोम को असंभव बना देती है। दोनों सिरों पर पॉइंटर्स का उपयोग करें। यदि सिरे मेल खाते हैं, तो अंदर की ओर बढ़ें। अन्यथा दाईं सीमा से अंदर की ओर स्कैन करके बाएं सिरे के लिए मेल खाने वाला वर्ण खोजें, आसन्न स्वैप्स के साथ इसे दाईं ओर बबल करें, और प्रत्येक चाल की गणना करें। यदि कोई मिलान मौजूद नहीं है, तो बेमेल वर्ण एकल केंद्र होना चाहिए; इसे केंद्र की ओर ले जाएं और जारी रखें।

चरण-दर-चरण गहन विश्लेषण

1. साध्यता सिद्ध करें

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

2. सीमाओं का मिलान करें

पॉइंटर्स i और j के लिए, यदि s[i], s[j] के बराबर है, तो दोनों स्थितियां तय हो जाती हैं। अन्यथा j से नीचे i + 1 तक s[k] == s[i] के लिए k खोजें। उस वर्ण को दाईं ओर ले जाने में j - k स्वैप्स लगते हैं और यह पहले से तय प्रीफिक्स को बनाए रखता है।

3. केंद्र वर्ण को संभालें

यदि कोई मिलान नहीं मिलता है, तो s[i] वह विषम-आवृत्ति वाला वर्ण है जो केंद्र में होना चाहिए। स्वैप्स की गणना करते हुए, इसे एक बार में एक कदम दाईं ओर ले जाएं जब तक कि यह मध्य तक न पहुंच जाए। इसे छोड़ें नहीं या यह न मानें कि केंद्र पहली बार में ही मिल जाना चाहिए।

4. सिमुलेशन लागू करें

count odd frequencies
if odd_count > 1: return impossible
left = 0, right = n - 1, swaps = 0
while left < right:
    if s[left] == s[right]: left++, right--; continue
    k = right
    while k > left and s[k] != s[left]: k--
    if k == left:
        swap s[k] with s[k + 1]
        swaps++
    else:
        while k < right:
            swap s[k] with s[k + 1]
            k++, swaps++
        left++, right--
return swaps

5. जटिलता और प्रमाण के विचार का विश्लेषण करें

प्रत्येक खोज और बबलिंग पास O(n) स्कैन कर सकता है, जिसे O(n) बार दोहराया जाता है, इसलिए समय O(n²) है और म्यूटेबल ऐरे O(1) अतिरिक्त स्पेस का उपयोग करता है। ग्रीडी पार्टनर सीमा के सबसे निकट होता है; समान वर्ण को दूर से ले जाने पर सीमा तय होने से पहले कम से कम उतने ही स्वैप्स की आवश्यकता होगी। केंद्र का मामला समता (parity) द्वारा बाध्य होता है।

उच्च-गुणवत्ता वाला नमूना उत्तर

"मैं पहले विषम आवृत्तियों की गणना करता हूं; एक से अधिक का अर्थ है असंभव। फिर मैं दोनों सिरों की तुलना करता हूं। बेमेल होने पर, मैं दाईं सीमा के निकटतम समान वर्ण को ढूंढता हूं और उसकी दूरी जोड़ते हुए उसे सही स्थान पर बबल करता हूं; यदि कोई समान वर्ण मौजूद नहीं है, तो वह वर्ण अद्वितीय विषम केंद्र है, इसलिए मैं इसे मध्य की ओर ले जाता हूं। मेल खाने वाले सिरे विंडो को छोटा करते हैं। सिमुलेशन में O(n²) समय और O(1) अतिरिक्त स्पेस लगता है, और ग्रीडी विकल्प इष्टतम है क्योंकि किसी भी दूर के पार्टनर को कम से कम उतने ही आसन्न स्वैप्स की आवश्यकता होती है।"

सामान्य गलतियां

• केवल यह जांचना कि गणनाएं सम (even) हैं या नहीं → विषम-लंबाई वाली स्ट्रिंग्स में एक विषम गणना हो सकती है → अधिकतम एक विषम आवृत्ति की अनुमति दें।
• किसी भी मनमाने मेल खाने वाले वर्ण के साथ स्वैप करना → अतिरिक्त हलचल न्यूनतम नहीं हो सकती है → सीमा के निकटतम पार्टनर को चुनें।
• बेमेल वर्ण को छोड़ देना → केंद्र की चाल कम गिनी जाती है → इसे मध्य की ओर बबल करें।
• बिना शिफ्ट किए टू-पॉइंटर स्वैप्स का उपयोग करना → आसन्न-स्वैप लागत छूट जाती है → प्रत्येक आसन्न चाल का सिमुलेशन करें या एक समकक्ष डेटा संरचना का उपयोग करें।

फॉलो-अप प्रश्न और उत्तर

क्या एल्गोरिदम पलिंड्रोम भी लौटा सकता है?

हाँ। म्यूटेबल ऐरे को बनाए रखें और इसकी अंतिम सामग्री और स्वैप गणना दोनों लौटाएं। यदि कॉलर को अनुक्रम की आवश्यकता है तो वही सिमुलेशन प्रत्येक आसन्न स्वैप को रिकॉर्ड करता है।

आप बड़े इनपुट्स के लिए इसे कैसे बेहतर बनाएंगे?

Fenwick tree या ऑर्डर-स्टैटिस्टिक्स संरचना के साथ मूल स्थितियों को ट्रैक करें ताकि किसी वर्ण को स्थानांतरित करने पर लॉगरिदमिक समय में स्थितियों को अपडेट किया जा सके। ग्रीडी पेयरिंग बनी रहती है, जबकि लागत गणना प्रत्येक तत्व को शिफ्ट करने से बचाती है।

क्या होगा यदि स्वैप्स आसन्न के बजाय मनमाने हों?

वह एक अलग लागत मॉडल है। निकटतम-पार्टनर दूरी प्रमाण अब लागू नहीं होता है; इस एल्गोरिदम का पुन: उपयोग करने से पहले अनुमत ऑपरेशन को परिभाषित करें।