टीएल;डीआर

  • समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
  • दृष्टिकोण: अक्षरों की लगातार पंक्तियों को कंप्रेस करें (aabcccccaaa से a2b1c5a3) स्ट्रिंगबिल्डर से, और जब छोटा न बने तो मूल लौटाएं। किनारे के मामलों सहित जावा वॉकथ्रू।
  • जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

कल्पना कीजिए बैग की सूची में पांच एक जैसे काले मोजे हैं। आप "मोजा, मोजा, मोजा, मोजा, मोजा" नहीं लिखते। आप लिखते हैं "मोजा × ५"। यही इस समस्या का सार है: एक ही अक्षर की लगातार पंक्ति को उस अक्षर और उसकी गिनती से बदल दो।

यह १.६ समस्या है, क्लासिक क्रैकिंग द कोडिंग इंटरव्यू शैली सेट (ऐरे और स्ट्रिंग) की। नीचे जावा में मूल शिक्षण वॉकथ्रू है, किसी किताब का समाधान पाठ नहीं। श्रृंखला मानचित्र: सीटीसीआई गाइड।

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

लगातार दोहराए गए अक्षरों की गिनती से बुनियादी स्ट्रिंग कंप्रेशन लागू करो।

हिस्सा मतलब
इनपुट केवल बड़े और छोटे अक्षरों वाली स्ट्रिंग (a-z, A-Z)
नियम बाएं से दाएं चलो। एक ही अक्षर की हर अधिकतम पंक्ति उस अक्षर और उसकी गिनती बन जाती है
उदाहरण aabcccccaaa बनता है a2b1c5a3
शर्त अगर कंप्रेस्ड रूप मूल से छोटा नहीं है, तो मूल स्ट्रिंग लौटाओ

गिनती दशमलव में लिखी जाती है। बारह x की पंक्ति x12 बनती है (अक्षर प्लस अंक), बारह अलग 1 नहीं।

"लगातार" मायने रखता है। aba तीन पंक्तियां लंबाई १ की हैं: a1b1a1। यह aba से लंबा है, इसलिए aba ही लौटेगा।

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

कच्चा झुकाव: स्ट्रिंग घूमो और "a" + "2" + "b" + ... से नई स्ट्रिंग जोड़ते जाओ, String पर + से।

आकार सही है, लागत गलत। जावा में हर बार जब String जोड़कर परिणाम बढ़ता है, पूरा प्रिफिक्स फिर कॉपी होता है। कई छोटी पंक्तियों पर लगभग वर्ग समय लगता है।

बेहतर आकार:

१. इंडेक्स i से स्ट्रिंग एक बार घूमो।
२. जब तक अगला अक्षर वर्तमान जैसा है, काउंटर बढ़ाओ।
३. अक्षर और गिनती StringBuilder में जोड़ो।
४. पूरे पास के बाद लंबाइयां तुलना करो। अगर बिल्डर छोटा नहीं, मूल लौटाओ।

StringBuilder म्यूटेबल बफर रखता है। हर लिखे अक्षर पर append औसत ओ(१) है, इसलिए पूरा निर्माण आउटपुट आकार में रैखिक है (स्कैन इनपुट में रैखिक)।

पहले यह भी जांच सकते हो कि "क्या वाकई सिकुड़ेगा?" पंक्तियां गिनकर अनुमानित लंबाई से। जब कंप्रेशन हारे तो बिल्डर बनाने से बचते हो। इंटरव्यू में एक पास बिल्डर प्लस अंतिम लंबाई जांच साफ और अक्सर काफी है।

स्ट्रिंगबिल्डर के साथ जावा समाधान

public final class StringCompression {

    private StringCompression() {}

    /**
     * Compress consecutive runs: aabcccccaaa -> a2b1c5a3.
     * Returns the original string when compression is not strictly shorter.
     */
    public static String compress(String s) {
        if (s == null || s.isEmpty()) {
            return s;
        }

        StringBuilder compressed = new StringBuilder();
        int n = s.length();
        int i = 0;

        while (i < n) {
            char c = s.charAt(i);
            int count = 0;
            // grow the run of c starting at i
            while (i < n && s.charAt(i) == c) {
                count++;
                i++;
            }
            compressed.append(c);
            compressed.append(count);
        }

        // only keep compression when it truly shrinks the string
        if (compressed.length() >= n) {
            return s;
        }
        return compressed.toString();
    }
}

aabcccccaaa का वॉकथ्रू:

१. a की पंक्ति लंबाई २ → a, 2 जोड़ो
२. b की पंक्ति लंबाई १ → b, 1 जोड़ो
३. c की पंक्ति लंबाई ५ → c, 5 जोड़ो
४. a की पंक्ति लंबाई ३ → a, 3 जोड़ो
५. परिणाम a2b1c5a3 लंबाई ८। मूल लंबाई १०। कंप्रेस्ड लौटाओ।

append(count) इसलिए चलता है क्योंकि StringBuilder में append(int) ओवरलोड है। स्पष्टता के लिए String.valueOf(count) भी ठीक है, जरूरी नहीं।

वैकल्पिक: जल्दी रुकना जब कंप्रेशन जीत ही न सके

हर पंक्ति कम से कम दो अक्षर बनती है (अक्षर + कम से कम एक अंक)। अगर हर पंक्ति लंबाई १ है, कंप्रेस्ड लंबाई 2 * n है। लोग अक्सर यह अर्ली एग्जिट करते हैं:

// rough check: if there are too many short runs, skip building
private static int countCompressedLength(String s) {
    int length = 0;
    int i = 0;
    int n = s.length();
    while (i < n) {
        char c = s.charAt(i);
        int count = 0;
        while (i < n && s.charAt(i) == c) {
            count++;
            i++;
        }
        length += 1 + String.valueOf(count).length();
    }
    return length;
}

पहले इसे बुलाओ। अगर countCompressedLength(s) >= s.length(), तो बिना दूसरे पास के s लौटा दो। दो रैखिक पास भी वर्ग जोड़ से बेहतर हैं। इंटरव्यू में ट्रेड-ऑफ जोर से कहो: अतिरिक्त पास बनाम बड़ा बिल्डर बनाकर फेंकना।

ज्यादातर व्हाइटबोर्ड पर सिंगल-पास बिल्डर काफी है।

जटिलता

माप सीमा क्यों
समय O(n) इनपुट का एक स्कैन; हर इंडेक्स ज्यादा से ज्यादा एक बार आगे बढ़ता है
अतिरिक्त स्थान O(n) बिल्डर सबसे खराब स्थिति में लगभग O(n) अक्षर रखता है
पहले लंबाई जांच के साथ O(n) समय, बिना बिल्ड किए मूल लौटाने पर O(1) अतिरिक्त दूसरा पास केवल जब कंप्रेशन मदद करे

n इनपुट स्ट्रिंग की लंबाई है। गिनती के अंक छोटे होते हैं (हर पंक्ति पर log10(count) + 1), इसलिए सामान्य इंटरव्यू इनपुट पर बिग-ओ नहीं बदलता।

किनारे के मामले जो इंटरव्यूअर छूते हैं

इनपुट अपेक्षित क्यों
"" "" खाली खाली रहता है (नल नीति इंटरव्यूअर से तय करो)
"a" "a" a1 लंबा है
"aa" "aa" रूप a2 समान लंबाई का है, इसलिए मूल रखो
"aaa" "a3" साफ तौर पर छोटा
"aabbcc" "aabbcc" कंप्रेस्ड a2b2c2 लंबाई ६, छोटा नहीं
"AAAAA" "A5" केस सुरक्षित; A और a अलग अक्षर हैं
"aAaA" "aAaA" बदलता केस: चार पंक्तियां लंबाई १ की

तुलना स्पष्ट रखो: सख्ती से छोटा। समान लंबाई पर मूल लौटाओ। यही सामान्य कथन से मेल खाता है।

यह भी पक्का करो: गिनती केवल लगातार पंक्तियों की है, पूरी स्ट्रिंग में अक्षर की कुल आवृत्ति नहीं। aba का मतलब a2b1 नहीं।

आम गलतियां

१. लूप में String +। जवाब सही, जटिलता धीमी। रनटाइम पूछेंगे।
२. आखिरी पंक्ति भूलना। अगर सिर्फ अगला अक्षर बदलने पर फ्लश करते हो, लूप के बाद भी फ्लश चाहिए (या ऊपर जैसा लूप ताकि अंदर वाला व्हाइल अंतिम पंक्ति खा ले)।
३. पंक्ति लंबाई के बजाय कुल गिनती। फ्रिक्वेंसी मैप अलग समस्या हल करता है।
४. समान लंबाई पर कंप्रेस्ड लौटाना। समस्या चाहती है कि सिकुड़े नहीं तो मूल रहे।
५. A और a मिलाना। वे अलग पंक्तियां हैं।

दोस्त को समझाओ

स्ट्रिंग पर चलो और पड़ोसी जो एक जैसे दिखते हैं उन्हें समूह में बांटो। हर समूह "अक्षर + कितने" बनता है। टुकड़े StringBuilder से जोड़ो ताकि हर append पर पूरी स्ट्रिंग न बने। अंत में मापो: नई लिखावट छोटी नहीं तो फेंक दो और मूल सूची रखो।

यह अक्षरों के लिए रन-लेंथ शैली कंप्रेशन है, ईमानदार जांच के साथ: कंप्रेशन को सच में मदद करनी चाहिए।

आगे अभ्यास

अभी भी अध्याय १ में:

कल बिना देखे compress याद से दोबारा लिखो। अगर एक वाक्य में बता सको कि StringBuilder क्यों मायने रखता है, समस्या तुम्हारी है।