कोडिंग इंटरव्यू: UTF-8 बाइट सीक्वेंस को वैलिडेट करना

प्रॉम्प्ट और दायरा

यह एक बिट-मैनिपुलेशन और कैरेक्टर-एन्कोडिंग समस्या है। इनपुट एक बाइट ऐरे है, न कि पहले से डिकोड की गई यूनिकोड स्ट्रिंग। निर्धारित करें कि क्या प्रत्येक स्केलर 1 से 4 बाइट्स का उपयोग करता है और ट्रंकेटेड या विकृत (malformed) सीक्वेंस को अस्वीकार करें। LeetCode 393 समान बाधाओं का उपयोग करता है: अधिकतम लंबाई 2 * 10^4, जिसमें प्रत्येक पूर्णांक अपने सबसे निचले 8 बिट्स का योगदान देता है। RFC 3629 1–4 बाइट UTF-8 रूपों और मान्य स्केलर-वैल्यू रेंज को परिभाषित करता है।

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

लीडिंग-बाइट पैटर्न से कंटिन्यूशन काउंट प्राप्त करना।
10xxxxxx कंटिन्यूशन प्रीफिक्स को सख्ती से चेक करना।
अतिरिक्त कंटिन्यूशन बाइट्स, ट्रंकेशन और पांच-बाइट लीडिंग पैटर्न को अस्वीकार करना।
O(n) समय और O(1) अतिरिक्त स्पेस के साथ सिंगल पास समाधान तैयार करना।

पहले पूछे जाने वाले स्पष्टीकरण

पुष्टि करें कि क्या प्रत्येक तत्व का 0..255 में होना सुनिश्चित है; अन्यथा पहले सीमा से बाहर के मानों को अस्वीकार करें। यह भी स्पष्ट करें कि क्या कार्य केवल बाइट शेप की जांच करता है या उसे ओवरलॉन्ग एन्कोडिंग, सरोगेट कोड पॉइंट्स और U+10FFFF से ऊपर के मानों को भी अस्वीकार करना चाहिए। LeetCode संस्करण बाइट शेप पर केंद्रित है; प्रोडक्शन पार्सर को सख्त RFC 3629 स्केलर-वैल्यू नियमों को लागू करना चाहिए।

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

remaining बनाए रखें, जो वर्तमान कैरेक्टर के लिए अभी भी आवश्यक कंटिन्यूशन बाइट्स की संख्या है। एक लीडिंग बाइट के लिए, 0, 1, 2, या 3 सेट करने के लिए इसके हाई-बिट पैटर्न का उपयोग करें; एक कंटिन्यूशन बाइट के लिए, (byte & 0b11000000) === 0b10000000 की आवश्यकता रखें और काउंटर को घटाएं। किसी अवैध लीडर, अप्रत्याशित कंटिन्यूशन, या remaining !== 0 के साथ इनपुट की समाप्ति को अस्वीकार करें। स्कैन केवल इस काउंटर को रखता है।

चरण-दर-चरण समाधान

1. लीडिंग-बाइट पैटर्न को पहचानें

0xxxxxxx एक एक-बाइट कैरेक्टर है; 110xxxxx, 1110xxxx, और 11110xxx के लिए क्रमशः 1, 2, और 3 कंटिन्यूशन बाइट्स की आवश्यकता होती है। मास्क के साथ प्रीफिक्स का परीक्षण करें: पहले 0x80, फिर 0xE0, 0xF0, और अंत में 0xF8 की जांच करें। यदि 0xF8 परीक्षण अभी भी गैर-शून्य है, तो बाइट पांच-बाइट या उससे लंबे रूप को शुरू करता है और इसे अस्वीकार किया जाना चाहिए।

2. कंटिन्यूशन बाइट्स को ऑनलाइन वैलिडेट करें

जब remaining > 0 हो, तो वर्तमान बाइट को 10xxxxxx से मेल खाना चाहिए। सफल जांच के बाद घटाएं। इस स्थिति में एक ASCII लीडर या अन्य मल्टी-बाइट लीडर तुरंत अमान्य हो जाता है। किसी बैकट्रैकिंग या स्लाइसिंग की आवश्यकता नहीं है, और इनपुट समाप्त होने पर ट्रंकेशन का पता चल जाता है।

3. संदर्भ कार्यान्वयन

text

isValidUtf8(bytes):
  remaining = 0
  for byte in bytes:
    if byte < 0 or byte > 255: return false
    if remaining > 0:
      if (byte & 0b11000000) != 0b10000000: return false
      remaining -= 1
      continue
    if (byte & 0b10000000) == 0:
      remaining = 0
    else if (byte & 0b11100000) == 0b11000000:
      remaining = 1
    else if (byte & 0b11110000) == 0b11100000:
      remaining = 2
    else if (byte & 0b11111000) == 0b11110000:
      remaining = 3
    else:
      return false
  return remaining == 0

4. प्रोडक्शन-स्तरीय सख्ती

अकेले प्रीफिक्स काउंटिंग कुछ ओवरलॉन्ग एन्कोडिंग को स्वीकार कर लेती है, जैसे कि एक मान को तीन बाइट्स के साथ दर्शाना जब एक ही पर्याप्त होता, और सरोगेट मानों को स्वीकार कर सकती है। एक प्रोडक्शन पार्सर को स्केलर मान जमा करना चाहिए और इसकी लंबाई के लिए न्यूनतम मान, सरोगेट रेंज और U+10FFFF सीमा की जांच करनी चाहिए; स्पष्ट रूप से तय करें कि क्या BOM की अनुमति है। नियमों को चुपचाप मिलाने के बजाय पहले अभ्यास की सीमा बताएं, फिर इस विस्तार की व्याख्या करें।

5. परीक्षण और जटिलता

[197,130,1] को सत्य, [235,140,4] को असत्य, एक अलग कंटिन्यूशन [128], एक ट्रंकेटेड [226,130], एक पांच-बाइट लीडर [248,128,128,128,128], और खाली ऐरे को कवर करें। प्रत्येक बाइट को एक बार स्कैन किया जाता है: O(n) समय और O(1) अतिरिक्त स्पेस, जहाँ n ऐरे की लंबाई है।

मॉडल उत्तर

मैं लीडिंग-बाइट पहचान को कंटिन्यूशन-बाइट वैलिडेशन से अलग करता हूँ। 0xxxxxxx, 110xxxxx, 1110xxxx, या 11110xxx से मेल खाने वाला लीडर remaining को क्रमशः 0, 1, 2, या 3 पर सेट करता है; कंटिन्यूशन स्थिति केवल 10xxxxxx को स्वीकार करती है और काउंटर को घटाती है। पांच-बाइट लीडर, अप्रत्याशित कंटिन्यूशन, आउट-ऑफ-रेंज तत्व, या अधूरे कैरेक्टर के साथ इनपुट की समाप्ति false लौटाती है। कार्यान्वयन O(1) स्पेस के साथ एक O(n) पास है। प्रोडक्शन के लिए, ओवरलॉन्ग एन्कोडिंग, सरोगेट्स और U+10FFFF से ऊपर के मानों को अस्वीकार करने के लिए स्केलर मान जमा करें।

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

प्रत्येक 10 प्रीफिक्स की जांच किए बिना कंटिन्यूशन बाइट्स की गिनती करना।
111110xx को मान्य पांच-बाइट रूप मानना।
अंतिम remaining जांच को भूल जाना और ट्रंकेशन को स्वीकार करना।
बिट-स्तरीय इनवेरिएंट या त्रुटि इंडेक्स दिखाए बिना किसी भाषा के डिकोडर को काम सौंपना।
दायरा बताए बिना LeetCode शेप चेक को RFC स्केलर-वैल्यू नियमों के साथ मिलाना।
byte को हस्ताक्षरित (signed) मानना और बिट संचालन से पहले इसे 0..255 में सामान्यीकृत करने में विफल रहना।

फॉलो-अप प्रश्न

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

{valid, errorIndex, reason} लौटाएं। जब कोई लीडर, कंटिन्यूशन, या एंड-ऑफ़-इनपुट चेक विफल हो जाए तो वर्तमान इंडेक्स रिकॉर्ड करें। स्कैनिंग स्थिति अपरिवर्तित रहती है, इसलिए कॉलर मूल बाइट को हाइलाइट कर सकते हैं।

आप चंक्ड स्ट्रीमिंग इनपुट का समर्थन कैसे करेंगे?

चंक्स के बीच पार्सर ऑब्जेक्ट में remaining और आंशिक स्केलर स्थिति बनाए रखें। एक कैरेक्टर तभी पूरा होता है जब बाद का चंक सभी कंटिन्यूशन बाइट्स की आपूर्ति करता है; remaining != 0 के साथ स्ट्रीम का अंत अभी भी एक ट्रंकेशन त्रुटि है।

केवल रेगुलर एक्सप्रेशन का उपयोग क्यों न करें?

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

आप ओवरलॉन्ग एन्कोडिंग को कैसे अस्वीकार करते हैं?

लीडर से सीक्वेंस की लंबाई और संचित मान रिकॉर्ड करें, फिर आवश्यकता रखें कि मान उस लंबाई की न्यूनतम सीमा को पूरा करे। साथ ही 0xD800..0xDFFF और 0x10FFFF से ऊपर के मानों को अस्वीकार करें।

आप दुर्भावनापूर्ण बड़े इनपुट को कैसे संभालते हैं?

कॉलर को बाइट सीमा, टाइमआउट और एरर-सैंपलिंग नीति लागू करने दें। पार्सर स्वयं O(1) स्थिति बनाए रखता है और पहली निश्चित त्रुटि पर शॉर्ट-सर्किट करता है, इसलिए विकृत इनपुट को अतिरिक्त बफ़र की आवश्यकता नहीं होती है।