साक्षात्कार प्रश्न: किसी दिए गए स्ट्रिंग में अगला और पिछला वर्ण ढूंढना?

Question

हमारे पास एक भाषा एक्स है, जिसमें एक बाइट और दो बाइट वर्ण हैं। इस भाषा में निम्नलिखित विशेषताएं हैं।

1. एकल बाइट वर्ण मूल्य हमेशा से कम या दो बाइट वर्ण में 127.
2. के बराबर होगा, सबसे पहले बाइट हमेशा अधिक से अधिक से अधिक 127 और दूसरी बाइट मूल्य कुछ भी हो सकता हो जाएगा।

समस्या यह है कि हमें स्ट्रिंग में कुछ बाइट को इंगित करने के लिए एक मनमाना लंबाई स्ट्रिंग और पॉइंटर दिया जाता है और हमें यह पता लगाना होगा कि पिछले चरित्र क्या है और अगला चरित्र क्या है।

एक सरल दृष्टिकोण स्ट्रिंग की शुरुआत से शुरू होगा, बाइट के मूल्य की जांच करेगा और पॉइंटर्स की तुलना तब तक करेगा जब तक हम दिए गए पॉइंटर तक नहीं पहुंच जाते। लेकिन सबसे बुरी स्थिति में, यदि दिया गया सूचक, दिए गए स्ट्रिंग में अंतिम बाइट इंगित करता है, तो हमें सभी charaters के माध्यम से लूप करना होगा।

मुझे पता है कि कोई बेहतर एल्गोरिदम है जो स्ट्रिंग की लंबाई के बावजूद निरंतर समय में परिणाम देगा?

Answer 1

यह सबसे बुरी स्थिति में लगता है, हमें पूरी स्ट्रिंग के माध्यम से जाने की जरूरत है। बस पर विचार वर्ण एक = 100 और बी = 200, सी = 201 और लंबाई एन के निम्नलिखित तार:

एस 1 = ABCBCBC ... ईसा पूर्व

एस 2 = BBCBCBC ... ईसा पूर्व

Answer 2

आप यह सोचते हैं स्ट्रिंग में पीछे की तरफ जाने के बारे में जानें (और यह मानते हुए कि वह पॉइंटर जो आपको देता है, वास्तव में वर्तमान चरित्र के पहले बाइट होने की गारंटी देता है यदि यह बहु-बाइट है)। बस दो बाइट वापस ले जाएं।

यदि वर्तमान -2> 127 पर डेटा है तो पिछले वर्ण अंतिम दो बाइट हैं। यदि वर्तमान -2 का डेटा < 127 है तो पिछला वर्ण वर्तमान -1 पर है।

अगले चरित्र के लिए समान। यदि वर्तमान +1 पर डेटा < 127 है तो यह अगला चरित्र है, अन्यथा यह बहु-बीटी चरित्र की शुरुआत है।

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

Answer 3

जब तक आप 127 से कम लगातार दो बाइट्स दबाते हैं या आप स्ट्रिंग की शुरुआत को हिट करते हैं, तब तक पीछे की ओर स्कैन करें। अब आप वर्तमान चरित्र के बाद कहां हैं और एक पर वर्णों की गणना कर सकते हैं।

Answer 4

पिछला: बैक अप 2 बाइट्स। यदि बाइट> 127, तो यह चरित्र की शुरुआत है, अन्यथा पिछला चरित्र अगले चरित्र पर शुरू होता है।

अगला: यदि वर्तमान बाइट> 127 है, तो अगला वर्ण 2 बाइट्स में शुरू होता है, अन्यथा अगला चरित्र 1 बाइट में शुरू होता है।

Answer 5

नहीं, निरंतर समय असंभव है क्योंकि सबसे खराब मामला है, क्योंकि ओलेक्सिया कहता है कि लगभग पूरी स्ट्रिंग शीर्ष-बिट-सेट बाइट्स है और आपको यह पता लगाने के लिए सही शुरुआत करने की आवश्यकता है कि कौन सा शीर्ष है पहले दो बाइट अनुक्रम में -bit-set बाइट।

उम्मीद है कि इस रोग के मामले दुर्लभ है और तुम सिर्फ एक समय में एक बाइट पीछे हटना जब तक आप किसी भी कम बाइट, जिस स्थिति में आप यह सुनिश्चित करें कि बाइट बाद यह एक चरित्र की शुरुआत है हो सकता है पूरा कर सकते हैं। तब तक आप तब तक आगे बढ़ सकते हैं जब तक कि आप अपने मूल सूचक से मिलते हैं।

Answer 6

वास्तव में आपको तीन वर्णों को ढूंढने की आवश्यकता है: वर्तमान वर्ण, पिछले चरित्र, और अगला चरित्र।

CurrentChar या तो पॉइंटर या पी -1 द्वारा दिए गए स्थिति पी पर है। यदि स्थिति पी एक बाइट पर इंगित कर रहा है जो 127 से अधिक है तो पी CurrentChar है। यदि पी 127 से कम है तो पी -1 देखें। यदि पी -1 1 से अधिक है तो CurrentChar पी -1 है अन्यथा CurrentChar स्थिति पी

पिछला कक्ष प्राप्त करने के लिए, CurrentChar - 2 देखें और यदि यह 127 से अधिक है पिछलाछ = CurrentChar -2 अन्यथा पिछलाChar = CurrentChar -1

अगलाखार पी को देखकर प्राप्त किया जा सकता है। यदि पी 127 से अधिक है तो अगला चार पी + 2 पर है। यदि पी 127 से कम है अगला अगला स्थिति पी + 1 पर है।

Answer 7

चलो देखते हैं ... आप पहले से ही एक ऐसे चरित्र को इंगित कर रहे हैं जो एक बाइट या डबल बाइट हो सकता है। बाद के मामले में, आप इस चरित्र के पहले या दूसरे बाइट पर हो सकते हैं। तो सबसे पहले आपको यह जानने की जरूरत है कि क्या आप किसी चरित्र की शुरुआत में हैं या नहीं। मामलों को और भी खराब बनाने के लिए, दो-बाइट वर्ण का दूसरा बाइट कोई मूल्य हो सकता है, इस प्रकार एक मौका है कि सभी बाइट 127 से अधिक हैं! इससे पिछले चरित्र को ढूंढना बुरा लगता है। लेकिन सबसे पहले, यह निर्धारित करें कि क्या आप एक नए चरित्र की शुरूआत में हैं या एक के बीच में हैं।

• चरित्र शुरू करना निर्धारित करें: एक बाइट वापस जाएं जब तक कि आपको एक बाइट नहीं मिलता है जिसमें यह उच्चतम बिट सेट नहीं होता है। (या स्ट्रिंग की शुरुआत।) उच्चतम बिट सेट वाले बाइट्स की संख्या के आधार पर, आपको पता चलेगा कि आप शुरुआत में हैं या नहीं। वर्तमान बाइट से पहले सेट किए गए उच्च बिट्स की एक अजीब संख्या का मतलब है कि आपको वर्तमान चरित्र के लिए पीछे एक बाइट जाना है।

• पिछले चरित्र को निर्धारित करना: दो बाइट्स वापस जाएं। यदि उच्चतम बिट सेट है, तो आपको यह पता चला है। यदि नहीं, तो एक बाइट आगे बढ़ें।

• अगले चरित्र को निर्धारित करना: वर्तमान बाइट का उच्चतम बिट देखें। यदि सेट है, तो दो बाइट आगे बढ़ें। अन्यथा, सिर्फ एक।

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

मुझे लगता है कि स्ट्रिंग के प्रारंभ और अंत को इंगित करने के लिए आपके पास कुछ तरीका है। यदि नहीं, तो यह कहां से शुरू होता है और बंद हो जाता है इसका कोई संकेत नहीं है। (जब तक आप स्टार्ट/स्टॉप को इंगित करने के लिए एक नल बाइट का उपयोग नहीं करते हैं, तो आप बाइट्स को छोड़ नहीं सकते हैं क्योंकि आप इस तरह के एक शून्य बाइट को छोड़ सकते हैं।)

क्या कोई तेज तरीका है? खैर, यदि आप प्रारंभ/समाप्ति स्थान जानते हैं तो आप इस स्ट्रिंग में बाइट्स की संख्या की गणना कर सकते हैं। पात्रों की संख्या इस स्ट्रिंग में बाइट्स की संख्या होगी जो उनके उच्चतम बिट सेट नहीं हैं। तो केवल 128 से कम बाइट्स की संख्या को बढ़ाएं!

Answer 8

यह मानते हुए कि आगमन [] एक स्ट्रिंग और एक बाइट के लिए सूचक की तरह है सूचकांक

#include<stdio.h> 
#include<stdlib.h> 
int find_valid(int); 
int arr[]={128,12,128,19,128,127,128,12,32,145,12,223,54,76,23}; 
int main(){ 
    int index=1; 
    while(index != 0){ 
    printf("\nEnter the index:"); 
    scanf("%d",&index); 
    if(arr[index] < 128){ // it can be the first byte or the second byte of the Two byte 
      if(arr[index -1] < 128) printf("\nThis is the first byte in itself"); 
      else // index-1 >= 128 
       { 
        int count = find_valid(index-2); 
        if(count%2 == 0) printf("\n This is the second byte of the two bytes:");  
        else printf("\nThis is the first byte in itself:"); 
       } 
      } 
    else{ // it can be the second or the first in the two bytes 
      if (arr[index - 1] < 128) printf("\n This is the First byte of the two bytes:"); 
      else{ 
       int count = find_valid(index-2); 
       if(count%2 == 0) printf("\n This is the second byte of the two bytes:"); 
       else printf("\nThis is the First byte of the two bytes:"); 
       } 
      }   

    printf("\nHave u seen the result:"); 
    scanf("%d",&index);} 
} 

int find_valid(int i){ 
    int count=0; 
    while((arr[i] > 127) && (i>0)) { ++count; --i;} 
     return count;  
}