प्रॉम्प्ट और दायरा
स्टिक के एंडपॉइंट 0 और n हैं, और cuts में अलग-अलग आंतरिक स्थितियाँ शामिल हैं। प्रत्येक चरण में, वर्तमान सेगमेंट में एक कट चुनें, उस सेगमेंट की लंबाई का भुगतान करें, और इसे दो सेगमेंट में विभाजित करें। LeetCode 1547 के पैमाने का उपयोग करें: n अधिकतम 1,000,000 है और कटों की संख्या m अधिकतम 100 है। केवल न्यूनतम लागत लौटाएँ; क्रम को पुनः प्राप्त करने के लिए निर्णय बिंदु (decision point) को स्टोर करने की आवश्यकता होती है।
इंटरव्यूअर क्या जांच रहा है
- क्या आप इनपुट क्रम का लालचपूर्वक (greedily) पालन करने के बजाय इंटरवल DP को पहचानते हैं।
- क्या आप 0 और n को सेंटिनल्स के रूप में जोड़ते हैं और कट स्थितियों को सॉर्ट करते हैं।
- क्या आप यह समझा सकते हैं कि पहला या अंतिम कट चुनना समस्या को स्वतंत्र अंतरालों में क्यों विभाजित करता है।
- क्या आप m-आधारित समय, स्पेस और इंटीजर-सुरक्षा सीमाओं को बता सकते हैं।
स्पष्टीकरण वाले प्रश्न
- क्या cuts में 0, n, या डुप्लिकेट शामिल हो सकते हैं? यदि हाँ, तो क्या API को उन्हें हटाना चाहिए या अस्वीकार करना चाहिए?
- क्या हमें केवल न्यूनतम लागत चाहिए, या एक इष्टतम क्रम भी चाहिए? इसके लिए एक चॉइस टेबल की आवश्यकता होगी।
- m के लिए ऊपरी सीमा क्या है? एक बड़ा m क्यूबिक समय को बाहर कर सकता है।
- क्या प्रत्येक कट की लागत बिल्कुल वर्तमान सेगमेंट की लंबाई है? भारित (weighted) लागत ट्रांज़िशन को बदल देती है।
30-सेकंड का उत्तर
मैं कटों को सॉर्ट करता हूँ और 0 तथा n जोड़ता हूँ। मान लें कि dp[i][j], पॉइंट्स i और j के ठीक बीच के प्रत्येक कट को करने की न्यूनतम लागत है; आसन्न एंडपॉइंट्स का मान शून्य होता है। प्रत्येक अंतराल के लिए, पहले कट के रूप में प्रत्येक आंतरिक पिवट k को आज़माएँ। उस कट की लागत अंतराल की लंबाई होती है, और बाएँ तथा दाएँ अंतराल स्वतंत्र होते हैं, इसलिए मैं dp[i][k] और dp[k][j] को जोड़ता हूँ। बढ़ते क्रम में स्पैन को भरने से O(m cubed) समय और O(m squared) स्पेस में dp[0][m+1] प्राप्त होता है।
विस्तृत उत्तर
1. निर्देशांक और इनवेरिएंट्स स्थापित करें
cuts को सॉर्ट करें और points बनाएँ जिसमें 0, सभी कट स्थितियाँ, और n शामिल हों। सॉर्ट करने के बाद, points[i] से points[j] तक के अंतराल के आंतरिक कट बिल्कुल i और j के बीच के इंडेक्स होते हैं। यह इनवेरिएंट स्टेट को पिछले कटों के इतिहास के बजाय एंडपॉइंट्स पर निर्भर बनाता है।
2. अंतराल स्थिति को परिभाषित करें
dp[i][j], points[i] और points[j] के अंदर के प्रत्येक कट को करने की न्यूनतम लागत है। जब j, i प्लस एक होता है, तो कोई आंतरिक कट नहीं होता है, इसलिए मान शून्य होता है। स्टेट क्रम को रिकॉर्ड नहीं करती है क्योंकि पहले कट के बाद बाएँ और दाएँ सब-प्रॉब्लम्स आपस में इंटरैक्ट नहीं करते हैं, और बाद की प्रत्येक लागत केवल अपने वर्तमान सेगमेंट पर निर्भर करती है।
3. ट्रांज़िशन प्राप्त करें
यदि पहला कट points[k] है, जहाँ i < k और k < j है, तो वर्तमान भुगतान points[j] माइनस points[i] है। कट दो स्वतंत्र अंतराल बनाता है:
dp[i][j] = min(
dp[i][k] + dp[k][j] + points[j] - points[i]
for k in (i + 1 ... j - 1)
)पहले छोटे स्पैन की गणना करें ताकि दोनों सब-इंटरवल मान पहले से उपलब्ध हों।
4. इसे लागू करें
function minCost(n: number, cuts: number[]): number {
const points = [0, ...cuts.slice().sort((a, b) => a - b), n];
const m = points.length;
const dp = Array.from({ length: m }, () => Array<number>(m).fill(0));
for (let span = 2; span < m; span += 1) {
for (let left = 0; left + span < m; left += 1) {
const right = left + span;
let best = Number.POSITIVE_INFINITY;
for (let pivot = left + 1; pivot < right; pivot += 1) {
best = Math.min(
best,
dp[left][pivot] + dp[pivot][right] + points[right] - points[left],
);
}
dp[left][right] = best === Number.POSITIVE_INFINITY ? 0 : best;
}
}
return dp[0][m - 1];
}5. ट्रांज़िशन सिद्ध करें
आंतरिक कटों की संख्या पर इंडक्शन का उपयोग करें। शून्य कट के साथ लागत शून्य है। मान लें कि छोटे अंतराल इष्टतम हैं। प्रत्येक इष्टतम क्रम में एक पहला पिवट k होता है। इसकी लागत पूर्ण अंतराल लंबाई के रूप में निश्चित होती है; शेष कार्य बाएँ और दाएँ अंतरालों में विभाजित हो जाता है, जिनके इष्टतम मान इंडक्शन द्वारा dp[i][k] और dp[k][j] होते हैं। प्रत्येक संभावित k पर न्यूनतम लेने से प्रत्येक पहला कट कवर हो जाता है, इसलिए ट्रांज़िशन इष्टतम है।
6. जटिलता, संख्याएँ, और पुनर्निर्माण
m आंतरिक कटों के साथ O(m squared) स्टेट्स और प्रति स्टेट O(m) तक पिवट होते हैं, जिससे O(m cubed) समय और O(m squared) स्पेस प्राप्त होता है। n अधिकतम 1,000,000 और m अधिकतम 100 के साथ, एक JavaScript number बताई गई लागत सीमा को कवर करता है; बड़ी भारित लागतों के लिए, BigInt या स्पष्ट सुरक्षित-पूर्णांक जांच का उपयोग करें। एक क्रम को पुनर्निर्मित करने के लिए, उस पिवट को स्टोर करें जिसने प्रत्येक न्यूनतम मान प्राप्त किया और रिकर्सिव रूप से निर्णय ट्री को उत्सर्जित करें।
7. प्रति-उदाहरण और परीक्षण
n=7 और cuts=[1,3,4,5] के लिए, इनपुट क्रम में काटने पर 20 लागत आती है, जबकि 3,5,1,4 क्रम में 16 लागत आती है। यह इनपुट-क्रम और बाएँ-से-दाएँ लालची विकल्पों को गलत साबित करता है। साथ ही एक कट, एंडपॉइंट्स के पास की स्थितियों, अनसॉर्टेड इनपुट, डुप्लिकेट नीति, लगातार अंतराल, अधिकतम m, और शून्य-आंतरिक-कट बेस अंतरालों का परीक्षण करें।
मॉडल उत्तर
मैं कटों को सॉर्ट करता हूँ और 0 तथा n जोड़ता हूँ। dp[i][j] दोनों एंडपॉइंट्स के बीच के प्रत्येक कट के लिए न्यूनतम लागत है, जिसमें आसन्न एंडपॉइंट्स के लिए शून्य है। प्रत्येक अंतराल के लिए मैं पहले कट के रूप में पिवट k को आज़माता हूँ: अंतराल की लंबाई का भुगतान करें, फिर इष्टतम बाएँ और दाएँ लागत जोड़ें। बढ़ते स्पैन द्वारा भरने पर बाहरी अंतराल प्राप्त होता है। m कटों के साथ जटिलता O(m cubed) समय और O(m squared) स्पेस है; प्रत्येक सर्वोत्तम पिवट को संग्रहीत करके क्रम का पुनर्निर्माण किया जा सकता है। मैं अनसॉर्टेड इनपुट, एंडपॉइंट के निकटवर्ती कट, एकल कट, और n=7, [1,3,4,5] प्रति-उदाहरण का परीक्षण करता हूँ।
सामान्य गलतियाँ
- इनपुट क्रम में काटना → वह क्रम इष्टतम से बहुत दूर हो सकता है → सॉर्ट करें और इंटरवल DP के साथ पहले पिवट की गणना करें।
- 0 और n को छोड़ना → बाउंड्री लंबाइयाँ और स्टेट्स अधूरी रह जाती हैं → दोनों एंडपॉइंट्स को सेंटिनल्स के रूप में शामिल करें।
- dp को केवल एक कट की लागत के रूप में परिभाषित करना → बाद के कट छूट जाते हैं → इसे संपूर्ण आंतरिक सेट के लिए न्यूनतम लागत के रूप में परिभाषित करें।
- सबसे छोटे या सबसे लंबे सेगमेंट को लालच से चुनना → स्थानीय विकल्प दोनों सब-प्रॉब्लम लागतों को बदल देते हैं → रिकर्सिव विभाजन और इंडक्शन प्रमाण दिखाएं।
- केवल सॉर्ट किए गए इनपुट का परीक्षण करना → कोड चुपचाप क्रम मान सकता है → फ़ंक्शन के अंदर कॉपी और सॉर्ट करें, फिर एक अनसॉर्टेड ऐरे का परीक्षण करें।
फॉलो-अप प्रश्न
आप एक इष्टतम कट क्रम कैसे लौटाते हैं?
उस पिवट को स्टोर करें जो प्रत्येक अंतराल न्यूनतम प्राप्त करता है। उस पिवट को उत्सर्जित करें, फिर बाएँ और दाएँ अंतरालों पर रिकर्स करें। यदि कई पिवट टाई करते हैं, तो एक नियतात्मक (deterministic) नियम परिभाषित करें जैसे सबसे छोटा इंडेक्स या लेक्सिकोग्राफ़िक रूप से सबसे छोटा क्रम।
क्या m के 100 से बढ़कर 2,000 होने पर O(m cubed) स्वीकार्य है?
बिना मापे इसका वादा न करें। स्टेट काउंट और समय बजट का अनुमान लगाएं, फिर अतिरिक्त संरचना, सन्निकटन (approximation), या ऑफ़लाइन बाधाओं की तलाश करें। एक सामान्य O(m squared) दावे के लिए एक सिद्ध मोनोटोनिसिटी या क्वाड्रैंगल-असमानता संपत्ति की आवश्यकता होती है।
क्या होगा यदि cuts में डुप्लिकेट स्थितियाँ शामिल हों?
दोहराए गए कट का कोई दूसरा भौतिक प्रभाव नहीं होता है। इनपुट अनुबंध के अनुसार सॉर्ट करें और डुप्लिकेट हटाएं, या डुप्लिकेट को अस्वीकार करें; शून्य-लंबाई अंतराल बनाने के बजाय विकल्प का दस्तावेजीकरण करें और उसका परीक्षण करें।
क्या होगा यदि प्रत्येक कट की लागत सेगमेंट लंबाई गुणा एक वेट हो?
यदि वेट केवल चुने गए पिवट k पर निर्भर करता है, तो अंतराल लंबाई शब्द को अंतराल लंबाई गुणा weight[k] से बदलें, और विभाजन स्वतंत्र रहता है। यदि लागत इतिहास, कट काउंट, या क्रॉस-इंटरवल स्टेट पर निर्भर करती है, तो सब-प्रॉब्लम्स अब स्वतंत्र नहीं हैं और स्थिति को फिर से डिज़ाइन किया जाना चाहिए।