इन-प्लेस रन लम्बाई डिकोडिंग?

Question

रन रन एन्कोडेड स्ट्रिंग को देखते हुए, "ए 3 बी 1 सी 2 डी 1 ई 1" कहें, स्ट्रिंग इन-प्लेस को डीकोड करें। एन्कोडेड स्ट्रिंग का उत्तर "AAABCCDE" है। मान लें कि एन्कोडेड सरणी डीकोडेड स्ट्रिंग को समायोजित करने के लिए काफी बड़ी है, यानी आप मान सकते हैं कि सरणी आकार = MAX [लंबाई (एन्कोडेडस्टिरिंग), लंबाई (डीकोडेडस्ट्रिंग)]।

यह मामूली प्रतीत नहीं होता है, क्योंकि ए 3 को 'एएए' के ​​रूप में डीकोड करने से मूल स्ट्रिंग के ओवर-राइटिंग 'बी' का कारण बन जाएगा।

इसके अलावा, कोई यह नहीं मान सकता कि डीकोडेड स्ट्रिंग एन्कोडेड स्ट्रिंग से हमेशा बड़ी होती है। उदाहरण: एनकोडेड स्ट्रिंग - 'ए 1 बी 1', डीकोडेड स्ट्रिंग 'एबी' है। कोई विचार?

और यह हमेशा एक पत्र अंकों जोड़ी हो जाएगा, यानी आप 0000055555

Answer 1

यदि हम पहले से ही नहीं जानते हैं, तो हमें डीकोडेड स्ट्रिंग की लंबाई की गणना करने के लिए, अंकों को जोड़कर, पहले जोड़ना चाहिए।

यह हमेशा एक अक्षर-अंक जोड़ी होगी, इसलिए आप किसी भी भ्रम के बिना स्ट्रिंग से 1 एस हटा सकते हैं।

A3B1C2D1E1 

A3BC2DE 

हो जाता है यहाँ कुछ कोड स्ट्रिंग (ओ (एन) जटिलता) से 1 रों दूर करने के लिए, सी ++ में, है।

// remove 1s 
int i = 0; // read from here 
int j = 0; // write to here 
while(i < str.length) { 
    assert(j <= i); // optional check 
    if(str[i] != '1') { 
     str[j] = str[i]; 
     ++ j; 
    } 
    ++ i; 
} 
str.resize(j); // to discard the extra space now that we've got our shorter string 

अब, इस स्ट्रिंग को अंतिम डीकोडेड स्ट्रिंग के समान, या समान लंबाई की गारंटी दी जाती है। हम मूल स्ट्रिंग के बारे में वह दावा नहीं कर सकते हैं, लेकिन हम इसे इस संशोधित स्ट्रिंग के बारे में बना सकते हैं।

(एक वैकल्पिक, मामूली, चरण अब पिछले 2 को पिछले अक्षर के साथ प्रतिस्थापित करना है। A3BCCDE, लेकिन हमें ऐसा करने की आवश्यकता नहीं है)।

अब हम अंत से काम करना शुरू कर सकते हैं। हमने पहले से ही डीकोडेड स्ट्रिंग की लंबाई की गणना की है, और इसलिए हम जानते हैं कि अंतिम चरित्र कहां होगा। हम आसानी से पात्रों को हमारी छोटी स्ट्रिंग के अंत से अपने अंतिम स्थान पर कॉपी कर सकते हैं।

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

Answer 2

यह एक बहुत ही अस्पष्ट सवाल यह है कि करने के लिए परिवर्तित 0515 को नहीं कहा जाएगा, हालांकि यह विशेष रूप से कठिन नहीं है अगर आप इसके बारे में सोचते हैं। जैसा कि आप कहते हैं, A3 को AAA के रूप में डीकोड करना और बस इसे जगह में लिखना B और 1 वर्णों को ओवरराइट करेगा, तो क्यों न केवल उन सरणी के साथ आगे बढ़ें?

उदाहरण के लिए, एक बार जब आप A3 पढ़ चुके हैं, तो आप जानते हैं कि आपको एक अतिरिक्त चरित्र के लिए जगह बनाने की आवश्यकता है, अगर यह A4 था, तो आपको दो की आवश्यकता होगी, और इसी तरह। इसे प्राप्त करने के लिए आपको सरणी में स्ट्रिंग का अंत मिल जाएगा (यह पहले से करें और इसकी अनुक्रमणिका को स्टोर करें)।

फिर पाश हालांकि, अपने नए स्लॉट के लिए पात्रों चलती:

शुरू करने के लिए: A|3|B|1|C|2||||||| एक चर सूचकांक 5, अर्थात पिछले, गैर खाली, प्रवेश भंडारण end कहा जाता है।

आप पहली जोड़ी में पढ़ा था, एक चर cursor बुलाया आपकी वर्तमान स्थिति को स्टोर करने का उपयोग कर - तो A और 3 यह (3 के साथ स्लॉट) 1 पर सेट किया जाएगा में पढ़ने के बाद। इस कदम के लिए

स्यूडोकोड:

वर एन = सरणी [कर्सर] - 2; // एन = 1, ए 3 से 3, और फिर जोड़ी के लिए अनुमति देने के लिए शून्य 2।

(i = end; i> कर्सर; i ++) { सरणी [i + n] = array [i]; }

इस के साथ छोड़ जाएगा:

A|3|A|3|B|1|C|2|||||

अब A वहाँ एक बार पहले से ही है, इसलिए अब आप लिखने के लिए n + 1A के सूचकांक cursor में संग्रहीत से शुरू करना चाहते हैं:

for(i = cursor; i < cursor + n + 1; i++) 
{ 
    array[i] = array[cursor - 1]; 
} 

// increment the cursor afterwards! 
cursor += n + 1; 

देने:

A|A|A|A|B|1|C|2|||||

फिर आप फिर से जाने के लिए तैयार मूल्यों की अगली जोड़ी की शुरुआत में इंगित कर रहे हैं। मुझे एहसास है कि इस जवाब में कुछ छेद हैं, हालांकि यह जानबूझकर है क्योंकि यह एक साक्षात्कार सवाल है!उदाहरण के लिए, किनारे के मामलों में आपने A1B1 निर्दिष्ट किया है, आपको आगे के पात्रों को पीछे की ओर पीछे की ओर ले जाने के लिए एक अलग लूप की आवश्यकता होगी।

Answer 3

अन्य ओ (एन^2) समाधान निम्नानुसार है।

यह देखते हुए कि उत्तर की जटिलता पर कोई सीमा नहीं है, यह सरल समाधान पूरी तरह से काम करता प्रतीत होता है।

while (there is an expandable element): 
    expand that element 
    adjust (shift) all of the elements on the right side of the expanded element 

कहाँ:

• नि: शुल्क अंतरिक्ष आकार सरणी में छोड़ दिया खाली तत्वों की संख्या है।

• एक विस्तार योग्य तत्व एक तत्व है कि:

  expanded size - encoded size <= free space size 
  

बिंदु प्रत्येक चरण में, विस्तारित स्ट्रिंग के लिए रन-लंबाई कोड से तक पहुँचने की प्रक्रिया में, पर है कि वहाँ है कम से कम एक तत्व जिसे विस्तारित किया जा सकता है (सिद्ध करने में आसान)।

Answer 4

निम्नलिखित समाधान O(n) और जगह में है। एल्गोरिदम को स्मृति को एक्सेस नहीं करना चाहिए, इसे पढ़ना और लिखना नहीं चाहिए। मैंने कुछ डीबगिंग किया है, और यह नमूना परीक्षणों के लिए सही लगता है जो मैंने इसे खिलाया था।

---

उच्च स्तरीय अवलोकन:

• इनकोडिंग लंबाई निर्धारित।
• सभी संख्याओं को पढ़कर और उन्हें संक्षेप में डीकोडेड लंबाई निर्धारित करें।
• बफर का अंत MAX (डीकोडेड लंबाई, एन्कोडेड लंबाई) है।
• स्ट्रिंग के अंत से शुरू करके स्ट्रिंग को डीकोड करें। बफर के अंत से लिखें।
• चूंकि डीकोडेड लंबाई एन्कोडेड लंबाई से अधिक हो सकती है, इसलिए डीकोडेड स्ट्रिंग बफर की शुरुआत में शुरू नहीं हो सकती है। यदि आवश्यक हो, स्ट्रिंग को शुरुआत में स्थानांतरित करके इसके लिए सही करें।

---

int isDigit (char c) { 
    return '0' <= c && c <= '9'; 
} 

unsigned int toDigit (char c) { 
    return c - '0'; 
} 

unsigned int intLen (char * str) { 
    unsigned int n = 0; 
    while (isDigit(*str++)) { 
     ++n; 
    } 
    return n; 
} 

unsigned int forwardParseInt (char ** pStr) { 
    unsigned int n = 0; 
    char * pChar = *pStr; 
    while (isDigit(*pChar)) { 
     n = 10 * n + toDigit(*pChar); 
     ++pChar; 
    } 
    *pStr = pChar; 
    return n; 
} 

unsigned int backwardParseInt (char ** pStr, char * beginStr) { 
    unsigned int len, n; 
    char * pChar = *pStr; 
    while (pChar != beginStr && isDigit(*pChar)) { 
     --pChar; 
    } 
    ++pChar; 
    len = intLen(pChar); 
    n = forwardParseInt(&pChar); 
    *pStr = pChar - 1 - len; 
    return n; 
} 

unsigned int encodedSize (char * encoded) { 
    int encodedLen = 0; 
    while (*encoded++ != '\0') { 
     ++encodedLen; 
    } 
    return encodedLen; 
} 

unsigned int decodedSize (char * encoded) { 
    int decodedLen = 0; 
    while (*encoded++ != '\0') { 
     decodedLen += forwardParseInt(&encoded); 
    } 
    return decodedLen; 
} 

void shift (char * str, int n) { 
    do { 
     str[n] = *str; 
    } while (*str++ != '\0'); 
} 

unsigned int max (unsigned int x, unsigned int y) { 
    return x > y ? x : y; 
} 

void decode (char * encodedBegin) { 
    int shiftAmount; 
    unsigned int eSize = encodedSize(encodedBegin); 
    unsigned int dSize = decodedSize(encodedBegin); 
    int writeOverflowed = 0; 
    char * read = encodedBegin + eSize - 1; 
    char * write = encodedBegin + max(eSize, dSize); 
    *write-- = '\0'; 
    while (read != encodedBegin) { 
     unsigned int i; 
     unsigned int n = backwardParseInt(&read, encodedBegin); 
     char c = *read; 
     for (i = 0; i < n; ++i) { 
      *write = c; 
      if (write != encodedBegin) { 
       write--; 
      } 
      else { 
       writeOverflowed = 1; 
      } 
     } 
     if (read != encodedBegin) { 
      read--; 
     } 
    } 
    if (!writeOverflowed) { 
     write++; 
    } 
    shiftAmount = encodedBegin - write; 
    if (write != encodedBegin) { 
     shift(write, shiftAmount); 
    } 
    return; 
} 

int main (int argc, char ** argv) { 
    //char buff[256] = { "!!!A33B1C2D1E1\0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" }; 
    char buff[256] = { "!!!A2B12C1\0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" }; 
    //char buff[256] = { "!!!A1B1C1\0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" }; 
    char * str = buff + 3; 
    //char buff[256] = { "A1B1" }; 
    //char * str = buff; 
    decode(str); 
    return 0; 
}