टीएल;डीआर

  • समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
  • दृष्टिकोण: दो स्ट्रिंग एक-दूसरे की क्रमचयन (परम्यूटेशन) हैं या नहीं, यह तय करें। स्क्रैबल टाइल उपमा, जावा में sort बनाम count array बनाम हैशमैप, जटिलता, और शुरुआती के लिए एज केस।
  • जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

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

यह सीटीसीआई जावा सीरीज़ का समस्या १.२ है: दो स्ट्रिंग दी हों, तय करें कि एक दूसरी की क्रमचयन (परम्यूटेशन) है या नहीं। हम शुरुआती-पहले रहेंगे: उपमा, सादा समस्या, सोचने का तरीका, फिर तीन साफ जावा संस्करण।

रोज़मर्रा की उपमा: स्क्रैबल की दो ढेरियाँ

आप और एक दोस्त, दोनों अक्षरों की टाइलें मेज पर गिराते हैं।

  • आपकी ढेर: T, A, R
  • दोस्त की ढेर: R, A, T

अगर हर ढेर को अक्षरक्रम में सॉर्ट करें, दोनों A, R, T बन जाती हैं। अक्षरों का वही मल्टीसेट। यही क्रमचयन (परम्यूटेशन) है।

अगर दोस्त के पास R, A, T, S है, ढेरियाँ एक नहीं। एक अतिरिक्त टाइल का मतलब: क्रमचयन (परम्यूटेशन) नहीं।

यहाँ क्रमचयन (परम्यूटेशन) का मतलब: वही कैरेक्टर, वही गिनती, शायद अलग क्रम में। “संबंधित शब्द” नहीं। “सिर्फ हिंदी/अंग्रेज़ी का एनाग्राम” नहीं। सिर्फ कैरेक्टर के थैले जो मेल खाते हैं।

समस्या सादे शब्दों में

इनपुट: दो स्ट्रिंग, a और b।

आउटपुट: true अगर a, b का पुनर्व्यवस्थापन है, वरना false।

उदाहरण

a b परिणाम क्यों
"abc" "bca" true वही तीन अक्षर
"abc" "ab" false लंबाई अलग
"aabc" "abac" true दो a, एक b, एक c
"Dog" "god" false अगर केस मायने रखे D और d अलग
"ab c" "abc" false अगर स्पेस गिने स्पेस भी एक कैरेक्टर है

इंटरव्यू में पूछने वाले सवाल

१. केस सेंसिटिव? आमतौर पर हाँ, जब तक वे न कहें। "God" और "dog" अलग हैं। २. स्पेस और विराम चिह्न गिनें? आमतौर पर हाँ। हर char बराबर समझें। ३. कैरेक्टर सेट? सिर्फ ASCII, या पूरा Unicode? इसी से काउंट ऐरे बनाम हैशमैप चुनते हैं। ४. Null या खाली? खाली और खाली true हो सकता है (शून्य कैरेक्टर)। Null प्रोडक्ट फैसला है; इंटरव्यू में अपना नियम बोलें।

इस पोस्ट में मान्यता:

  • केस सेंसिटिव।
  • स्पेस गिना जाता है।
  • पहले साफ ASCII समाधान, फिर सामान्य HashMap संस्करण।

कोड से पहले कैसे सोचें

बहुत धीमी brute force

a की हर क्रमचयन (परम्यूटेशन) बनाएँ और देखें b मिलती है या नहीं। लंबाई n पर लगभग n! स्ट्रिंग। लंबाई ४ पर ठीक। लंबाई २० पर खत्म। वहाँ न जाएँ।

विचार १: दोनों स्ट्रिंग सॉर्ट करें

अगर दो स्ट्रिंग क्रमचयन (परम्यूटेशन) हैं, उनके कैरेक्टर सॉर्ट करने पर एक ही क्रम मिलता है।

१. लंबाई अलग हो तो तुरंत false। २. हर स्ट्रिंग को char[] में बदलें। ३. दोनों ऐरे सॉर्ट करें। ४. ऐरे बराबरी जाँचें (या स्ट्रिंग बनाकर equals)।

समझाना आसान, तोड़ना मुश्किल। कीमत सॉर्ट की है: समय O(n log n)।

विचार २: कैरेक्टर गिनें (इंटरव्यू अपग्रेड)

सॉर्ट क्रम बदलता है। गिनती बताती है कितनी बार हर अक्षर है।

१. लंबाई अलग → false। २. a पर चलें, हर कैरेक्टर का काउंट बढ़ाएँ। ३. b पर चलें, घटाएँ। ४. कोई काउंट ऋणात्मक हो जाए, या अंत में गैर-शून्य बचे, तो क्रमचयन (परम्यूटेशन) नहीं।

अगर वर्णमाला छोटी और तय हो (क्लासिक ASCII, १२८ या २५६ स्लॉट), int[] काफी है। अगर कोई भी Unicode हो सकता है, HashMap<Character, Integer> लें।

गिनती आमतौर पर समय O(n) और निश्चित वर्णमाला पर अतिरिक्त जगह O(१) (ऐरे का आकार n के साथ नहीं बढ़ता)।

पहले कौन सा कहें?

असली इंटरव्यू में: पहले सॉर्ट, फिर बोलें “अगर वर्णमाला सीमित है तो आवृत्ति count से बेहतर कर सकते हैं।” इससे साबित होता है कि आप सरल संस्करण दे सकते हैं और फिर भी ऑप्टिमाइज़ जानते हैं।

जावा समाधान १: दोनों सॉर्ट

import java.util.Arrays;

public class CheckPermutation {

    /** true अगर a, b की permutation है (केस सेंसिटिव, हर char गिना)। */
    public static boolean permutationBySort(String a, String b) {
        if (a == null || b == null) {
            return a == b; // दोनों null -> true; एक null -> false
        }
        if (a.length() != b.length()) {
            return false;
        }

        char[] ca = a.toCharArray();
        char[] cb = b.toCharArray();
        Arrays.sort(ca);
        Arrays.sort(cb);
        return Arrays.equals(ca, cb);
    }
}

शुरुआती नोट:

  • toCharArray() कैरेक्टर कॉपी करता है ताकि सॉर्ट immutable String को म्यूट न करे।
  • लंबाई जाँच मुफ्त early exit है। अलग लंबाई कभी क्रमचयन (परम्यूटेशन) नहीं।
  • Arrays.equals सॉर्ट के बाद हर इंडेक्स मिलाता है।

जावा समाधान २: काउंट ऐरे (ASCII-मित्र)

मान लें कैरेक्टर ०..१२७ में हैं (स्टैंडर्ड ASCII)। अगर समस्या “extended ASCII” कहे, आकार २५६ रखें।

public class CheckPermutation {

    private static final int ASCII = 128;

    public static boolean permutationByCountArray(String a, String b) {
        if (a == null || b == null) {
            return a == b;
        }
        if (a.length() != b.length()) {
            return false;
        }

        int[] counts = new int[ASCII];

        for (int i = 0; i < a.length(); i++) {
            char c = a.charAt(i);
            // वैकल्पिक गार्ड अगर non-ASCII अस्वीकार करना हो:
            // if (c >= ASCII) throw new IllegalArgumentException("non-ASCII");
            counts[c]++;
        }

        for (int i = 0; i < b.length(); i++) {
            char c = b.charAt(i);
            counts[c]--;
            if (counts[c] < 0) {
                // b के पास इस char की संख्या a से ज्यादा
                return false;
            }
        }

        // लंबाई मेल, कभी ऋणात्मक नहीं: सब शून्य।
        return true;
    }
}

counts[c] < 0 पर जल्दी return क्यों काम करता है:

  • कुल लंबाई बराबर है।
  • जब भी b कोई कैरेक्टर खर्च करता है, a से बने स्टॉक से एक घटता है।
  • स्टॉक ऋणात्मक हुआ तो b को उस कैरेक्टर की जरूरत a से ज्यादा थी।
  • अगर ऐसा कभी न हो और लंबाई मेल खाए, थैले बराबर हैं। बचे सकारात्मक ढूँढने का तीसरा लूप जरूरी नहीं।

अगर किताब वाला तीन-पास स्टाइल पसंद हो: a से बढ़ाएँ, b से घटाएँ, फिर ऐरे में कोई non-zero खोजें। वही big-O; थोड़ा ज्यादा कोड।

जावा समाधान ३: हैशमैप (सामान्य कैरेक्टर सेट)

जब ASCII मान न सकें, मैप से गिनें।

import java.util.HashMap;
import java.util.Map;

public class CheckPermutation {

    public static boolean permutationByHashMap(String a, String b) {
        if (a == null || b == null) {
            return a == b;
        }
        if (a.length() != b.length()) {
            return false;
        }

        Map<Character, Integer> counts = new HashMap<>();

        for (int i = 0; i < a.length(); i++) {
            char c = a.charAt(i);
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }

        for (int i = 0; i < b.length(); i++) {
            char c = b.charAt(i);
            Integer left = counts.get(c);
            if (left == null || left == 0) {
                return false;
            }
            if (left == 1) {
                counts.remove(c); // वैकल्पिक: मैप साफ
            } else {
                counts.put(c, left - 1);
            }
        }

        return counts.isEmpty();
    }
}

ट्रेडऑफ:

  • जावा में संग्रहीत किसी भी char (UTF-१६ कोड यूनिट) पर काम करता है।
  • तंग int[] की तुलना में ऑब्जेक्ट और हैश की अतिरिक्त कीमत।
  • इंटरव्यू के ASCII स्ट्रिंग सवालों में, सॉर्ट के बाद ऐरे अक्सर तेज जवाब है।

छोटे स्मोक टेस्ट

public static void main(String[] args) {
    System.out.println(permutationBySort("abc", "bca"));       // true
    System.out.println(permutationBySort("abc", "ab"));        // false
    System.out.println(permutationByCountArray("aabc", "abac")); // true
    System.out.println(permutationByHashMap("Dog", "god"));    // false
    System.out.println(permutationByHashMap("", ""));          // true
}

जटिलता

जब लंबाई मेल खाए, n वह लंबाई है (अलग हो तो O(१) में रुकते हैं)।

तरीका समय अतिरिक्त जगह कब बेहतर
दोनों सॉर्ट O(n log n) char ऐरे के लिए O(n) (कॉपी न गिनें तो O(१) कह सकते हैं) सबसे सरल सही कोड चाहिए
काउंट ऐरे (आकार k) O(n) O(k) निश्चित, जैसे १२८ या २५६ वर्णमाला छोटी और ज्ञात
हैशमैप औसत O(n) O(min(n, alphabet)) कैरेक्टर बिखरे या वर्णमाला बड़ी

इंटरव्यू की एक पंक्ति: अलग लंबाई तुरंत नहीं। कैरेक्टर का वही मल्टीसेट मतलब हाँ। सॉर्ट मल्टीसेट साबित करता है। निश्चित वर्णमाला पर गिनती उसे तेज साबित करती है।

एज केस जो इंटरव्यूअर छेड़ते हैं

१. अलग लंबाई ("ab", "abc") → अगर पहले लंबाई जाँचें तो सामग्री स्कैन बिना false। २. खाली स्ट्रिंग ("", "") → true। ("", "a") → false। ३. एक खाली, एक नहीं → false। ४. डुप्लिकेट ("aab", "aba") → true; ("aab", "abb") → false। सिर्फ “a और b इस्तेमाल” नहीं, आवृत्ति मायने रखती है। ५. केस ("Abc", "abc") → case-sensitive नियम पर false। ६. स्पेस ("a b", "ab ") → true (वही कैरेक्टर, अलग क्रम); ("a b", "ab") → false। ७. Null → कोड से पहले नीति तय करें। ८. बहुत लंबी स्ट्रिंग → अगर सीमा विशाल और वर्णमाला तय हो तो सॉर्ट के बजाय O(n) गिनती। ९. Unicode / इमोजी → जावा में char UTF-१६ कोड यूनिट है। पूरे code point का हैंडलिंग गहरा विषय है; अगर इमोजी मायने रखें तो ज़िक्र करें।

आम गलतियाँ

  • जावा में स्ट्रिंग की तुलना == से (रेफरेंस समानता)। सॉर्ट के बाद कंटेंट तुलना करें, या स्ट्रिंग बनाएँ ही नहीं: ऐरे / काउंट मिलाएँ।
  • लंबाई जाँच भूलना और लंबा काउंट लिखना जो “लगभग” चलता हो।
  • काउंट के बजाय boolean “seen” सेट। सेट आवृत्ति मिटा देता है। "aab" और "abb" दोनों {a, b} लगेंगे।
  • बिना पूछे case-insensitive मान लेना।
  • ऐरे आकार पर off-by-one: १२८ बनाम २५६ बनाम Character.MAX_VALUE + 1 (जब तक मतलब न हो ६५k न आवंटित करें)।

दोस्त को समझाने वाला सार

Permutation जाँच पूछती है: क्या ये दो स्ट्रिंग अक्षरों का एक ही थैला हैं?

स्क्रैबल टाइलें सोचो। अगर दोनों के पास वही टाइलें हैं, सिर्फ अलग क्रम में रखीं, तो मेल। किसी के पास एक टाइल ज्यादा या कम हो तो नहीं।

तेज मानसिक एल्गोरिदम:

१. लंबाई अलग? नहीं। २. या दोनों ढेर सॉर्ट करके मिलाओ, या हर अक्षर की गिनती करो। ३. गिनती बराबर = हाँ।

जावा में सॉर्ट पहला साफ ड्राफ्ट है। निश्चित आकार का काउंट ऐरे ASCII के लिए आम O(n) अपग्रेड है। HashMap तब है जब वर्णमाला छोटी न हो।

यही सीटीसीआई १.२ है। अध्याय १ में आगे अक्सर URLify आता है (स्पेस को %20 स्थान पर ही (इन-प्लेस))। अध्याय का पिछला आइडिया Is Unique है (सभी कैरेक्टर अलग)।

सीरीज़

अभ्यास सुझाव: पहले बिना देखे सॉर्ट लिखें, अगले दिन याद से काउंट वाला संस्करण दोबारा लिखें।