कोडिंग इंटरव्यू: एक वर्ग का समान रूप से सैंपल लेना और सबसे लंबे बढ़ते सन्निहित सब-एरे को स्कैन करना

प्रश्न और दायरा

सार्वजनिक इंटरव्यू रिकॉर्ड इस अभ्यास को दो छोटे कार्यों में विभाजित करता है: rand01() फ़ंक्शन को कॉल करना जो side भुजा वाले वर्ग के अंदर एक बिंदु को सैंपल करने के लिए 0 और 1 के बीच एक समान मान लौटाता है, फिर किसी ऐरे का सबसे लंबा स्ट्रिक्टली बढ़ता सन्निहित खंड खोजना। यह लेख वर्ग के निचले-बाएँ कोने को (0, 0) पर रखता है, रैंडम स्रोत को [0, 1) के रूप में मानता है, और एक खाली ऐरे के लिए एक खाली परिणाम लौटाता है।

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

यह अभ्यास प्रोबेबिलिटी मॉडलिंग, रेंज मैपिंग, वन-पास इनवेरिएंट और सटीक परिणाम सिमेंटिक्स को जोड़ता है। Cornell के व्याख्यान नोट्स बताते हैं कि [0,1] पर दो स्वतंत्र समान चर इकाई वर्ग पर क्षेत्रफल के संबंध में एक समान बिंदु बनाते हैं; MIT की वर्ग-संभाव्यता सामग्री भी यही क्षेत्रफल व्याख्या देती है। स्कैन यह परीक्षण करता है कि क्या उम्मीदवार निरंतरता बनाए रखता है, समानता को ब्रेक के रूप में मानता है, और एक डिटर्मिनिस्टिक टाई-ब्रेक चुनता है।

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

1. क्या rand01() संवृत (closed) है या अर्ध-खुला (half-open)? यह उत्तर [0, 1) मानता है।
2. क्या वर्ग अनुवादित (translated) है? यह उत्तर मूल बिंदु (origin) से शुरू होता है; अनुवाद केवल ऑफसेट जोड़ता है।
3. क्या वृद्धि स्ट्रिक्ट (strict) है? इस उत्तर के लिए a[i] > a[i-1] आवश्यक है।
4. टाई होने पर कौन सा सबसे लंबा रन जीतता है? यह उत्तर सबसे पहला प्रारंभ लौटाता है।
5. क्या डिडुप्लीकेशन या क्रिप्टोग्राफ़िक यादृच्छिकता की आवश्यकता है? मूल अभ्यास में दोनों में से किसी की भी आवश्यकता नहीं है।

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

“मैं rand01() को स्वतंत्र रूप से दो बार कॉल करता हूँ और मानों को भुजा की लंबाई से गुणा करता हूँ। स्वतंत्र समान निर्देशांक प्रत्येक छोटे आयत की प्रायिकता को उसके क्षेत्रफल के बराबर बनाते हैं। ऐरे के लिए, मैं वर्तमान स्ट्रिक्टली बढ़ते रन की शुरुआत और सर्वश्रेष्ठ शुरुआत/अंत इंडेक्स रखता हूँ। गैर-वृद्धि वर्तमान शुरुआत को रीसेट करती है; मैं केवल तभी उत्तर अपडेट करता हूँ जब वर्तमान रन स्ट्रिक्टली अधिक लंबा हो। सैंपलिंग O(1) है, स्कैनिंग O(n) है, और अतिरिक्त स्थान O(1) है। मैं सीमाओं, समानता, खाली इनपुट, मोनोटोन ऐरे और टाई का परीक्षण करूँगा।”

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

1. समान सैंपल व्युत्पन्न करें

मान लें कि U और V, [0,1) पर स्वतंत्र समान चर हैं। किसी भी अक्ष-संरेखित आयत [a,b) × [c,d) के लिए, इसके अंदर आने की प्रायिकता (b-a)(d-c) है, जो बिल्कुल इसका क्षेत्रफल है। इसलिए (side × U, side × V) वर्ग में समान है। एक ही ड्रा का पुन: उपयोग करने से निर्देशांक पूरी तरह से सहसंबद्ध (correlated) हो जाएंगे और प्रत्येक बिंदु एक विकर्ण पर आ जाएगा।

2. लीनियर-स्कैन इनवेरिएंट बनाए रखें

इंडेक्स i पर, currentStart, i पर समाप्त होने वाले सबसे लंबे स्ट्रिक्टली बढ़ते रन की शुरुआत है; bestStart और bestEnd प्रीफिक्स में सर्वश्रेष्ठ रन का वर्णन करते हैं। यदि a[i] > a[i-1] है, तो रन को आगे बढ़ाएं। अन्यथा currentStart = i सेट करें। केवल स्ट्रिक्टली बड़ी लंबाई पर ही अपडेट करें, जो टाई के बीच सबसे पहले रन को बनाए रखता है।

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

from typing import Callable


def sample_square(side: float, rand01: Callable[[], float]) -> tuple[float, float]:
    if side < 0:
        raise ValueError("side must be non-negative")
    u, v = rand01(), rand01()
    if not (0 <= u < 1 and 0 <= v < 1):
        raise ValueError("rand01 must return values in [0, 1)")
    return side * u, side * v


def longest_increasing_run(values: list[int]) -> tuple[int, int] | None:
    if not values:
        return None
    current_start = best_start = best_end = 0
    for i in range(1, len(values)):
        if values[i] <= values[i - 1]:
            current_start = i
        current_length = i - current_start + 1
        best_length = best_end - best_start + 1
        if current_length > best_length:
            best_start, best_end = current_start, i
    return best_start, best_end

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

सैंपलिंग दो रैंडम-स्रोत कॉल करती है, इसलिए समय और अतिरिक्त स्थान O(1) हैं। स्कैन प्रत्येक तत्व को एक बार देखता है, जिसमें O(n) समय और O(1) अतिरिक्त स्थान लगता है; लौटाए गए मानों को भौतिक रूप से उत्पन्न करने (materialize) पर अतिरिक्त O(k) की लागत आएगी। निर्देशांक मैपिंग का परीक्षण करने के लिए एक निश्चित rand01 अनुक्रम का उपयोग करें, स्ट्रिक्टनेस का परीक्षण करने के लिए [1, 2, 2, 3] का उपयोग करें, और एकल-तत्व उत्तर का परीक्षण करने के लिए [5, 4, 3] का उपयोग करें।

आदर्श उत्तर

“मैं दो निर्देशांकों को स्वतंत्र समान चरों के रूप में मॉडल करता हूँ: rand01 को दो बार कॉल करें और भुजा की लंबाई से स्केल करें। यह किसी भी छोटे आयत की प्रायिकता को उसके क्षेत्रफल के बराबर बनाता है। मैं एक लीनियर स्कैन में एक स्टार्ट पॉइंटर और सर्वश्रेष्ठ इंडेक्स के साथ बढ़ते रन को खोजता हूँ, गैर-वृद्धि पर रीसेट करता हूँ और केवल स्ट्रिक्टली लंबे रन के लिए अपडेट करता हूँ, ताकि टाई में सबसे प्रारंभिक खंड चुना जाए। सैंपलिंग O(1) है, स्कैनिंग O(n) है, और दोनों O(1) अतिरिक्त स्थान का उपयोग करते हैं। मैं रैंडम-स्रोत अनुबंध, नकारात्मक भुजाओं, समान मानों और खाली ऐरे को सत्यापित करूँगा।”

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

• एक ही रैंडम ड्रा का पुन: उपयोग करना → निर्देशांक सहसंबद्ध हो जाते हैं और विकर्ण पर स्थित होते हैं → स्वतंत्र रूप से दो बार ड्रा करें।
• एक मनमाना rand01 रेंज मान लेना → निर्देशांक वर्ग से बाहर जा सकते हैं → [0,1) अनुबंध बताएं और मान्य करें।
• सन्निहित रन के लिए सॉर्ट करना या डायनेमिक प्रोग्रामिंग का उपयोग करना → क्रम खो जाता है या स्थान बढ़ जाता है → एक स्कैन स्थिति बनाए रखें।
• बढ़ने के लिए >= का उपयोग करना → समान मान गलत तरीके से जुड़ जाते हैं → > की आवश्यकता रखें।
• समान सर्वश्रेष्ठ लंबाइयों पर अधिलेखित (overwrite) करना → टाई व्यवहार अनपेक्षित हो जाता है → केवल स्ट्रिक्टली बड़ी लंबाई पर ही अपडेट करें।
• ऐरे को पुनरावर्ती (recursively) रूप से स्कैन करना → इनपुट आकार के साथ स्टैक की गहराई बढ़ती है → इटरेशन का उपयोग करें।

फॉलो-अप और विस्तार

आप एक आयत या अनुवादित वर्ग का सैंपल कैसे लेते हैं?

एक आयत के लिए x = xmin + (xmax-xmin)U और y = ymin + (ymax-ymin)V का उपयोग करें। एक अनुवाद केवल दोनों निर्देशांकों में एक ऑफसेट जोड़ता है और स्वतंत्रता को बनाए रखता है।

आप एकरूपता (uniformity) का निदान कैसे करेंगे?

वर्ग को समान क्षेत्रफल वाले सेल में विभाजित करें, कई सैंपल ड्रा करें और सेल गणनाओं की तुलना करें। यह एक निदान है, प्रमाण नहीं; रिग्रेशन के लिए एक निश्चित सीड उपयोगी है लेकिन दृश्य एकरूपता की गारंटी नहीं देता है।

क्या होगा यदि प्रत्येक सबसे लंबा रन लौटाया जाना चाहिए?

वर्तमान सर्वश्रेष्ठ लंबाई और एक सूची रखें। लंबे रन पर सूची साफ़ करें और समान रन पर जोड़ें; अतिरिक्त स्थान O(r) है, जहाँ r टाई हुए रनों की संख्या है।

क्या होगा यदि ऐरे एक स्ट्रीम के रूप में आता है?

केवल पिछला मान, वर्तमान शुरुआत, सर्वश्रेष्ठ इंडेक्स और वर्तमान स्थिति रखें। कुल इनपुट लंबाई से स्वतंत्र मेमोरी के साथ स्ट्रीम के अंत में सर्वश्रेष्ठ अंतराल उत्सर्जित करें।