टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ८.१४: ०/१ व्यंजक को &, | और ^ के साथ पूर्ण कोष्ठक देने पर सत्य या असत्य कितनी बार आता है। जावा में उप-स्ट्रिंग पर मेमो पुनरावृत्ति।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
एक बूलियन व्यंजक बिट और ऑपरेटर की श्रृंखला है: 1^0|0|1। बिना कोष्ठक के अर्थ अस्पष्ट रहता है। पूर्ण कोष्ठक के साथ हर द्विआधारी ऑपरेटर का बायाँ और दायाँ उप-व्यंजक साफ होता है। बूलियन मूल्यांकन पूछता है: स्ट्रिंग और एक लक्ष्य सत्य-मान दिए हों, तो कितनी अलग पूर्ण कोष्ठक रचनाएँ पूरे व्यंजक को उस लक्ष्य के बराबर बनाती हैं?
यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। पुनरावृत्ति और गतिशील प्रोग्रामिंग इंटरव्यू सवालों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ८ यहीं व्यंजक के मेमो कट पर खत्म होता है।
१. रोज़मर्रा की उपमा
स्विच की एक पंक्ति सोचो (० बंद, १ चालू) और बीच में गेट: और (&), या (|), एक्सओआर (^)।
जोड़े जोड़ने का क्रम तुम्हें तय करना है। हर क्रम एक पूर्ण कोष्ठक रचना है:
1 ^ 0 | 1
हो सकता है (1 ^ 0) | 1
या 1 ^ (0 | 1)
ये दो पेड़ अलग नतीजा दे सकते हैं। पहला (1) | 1 → सत्य। दूसरा 1 ^ (1) → असत्य।
काम एक क्रम चुनना नहीं है। काम है दिए गए नतीजे (सत्य या असत्य) वाले क्रम गिनना।
छोटे व्यंजक छोटे पेड़ जैसे लगते हैं। लंबे व्यंजक कैटलान जैसे बाइनरी पेड़ों की संख्या में फूटते हैं, इसलिए मेमो चाहिए।
२. सादा समस्या कथन
इनपुट: विषम लंबाई की स्ट्रिंग expr। सम इंडेक्स पर '0' या '1'। विषम इंडेक्स पर '&', '|' या '^'। एक बूलियन result (लक्ष्य)।
आउटपुट: expr को पूर्ण रूप से कोष्ठक देने के उतने तरीके जितने उसे result पर ले जाएँ।
नियम:
- हर कोष्ठक रचना ऑपरेटरों पर एक पूर्ण बाइनरी पेड़ है (हर ऑपरेटर का ठीक एक बायाँ और एक दायाँ उप-व्यंजक)।
- ऑपरेटर तभी चलते हैं जब दोनों पक्ष पूरे हों (सामान्य प्राथमिकता के खेल नहीं; कोष्ठक सब तय करते हैं)।
- गिनती अलग कोष्ठक-पेड़ों की है, अलग अंतिम स्ट्रिंग की नहीं।
उदाहरण:
| व्यंजक | लक्ष्य | तरीके | नोट |
|---|---|---|---|
"1" |
सत्य | १ | एक बिट |
"1" |
असत्य | ० | |
"1^0|1" |
सत्य | १ | नीचे वॉकथ्रू |
"1^0|0|1" |
असत्य | २ | क्लासिक नमूना |
"0&0&0&1^1|0" |
सत्य | १० | क्लासिक नमूना |
साफ करो:
- खाली स्ट्रिंग? ० लौटाओ (या अवैध कहो)।
- गलत लंबाई या अक्षर? दायरे से बाहर; सही रूप मानो।
- अलग पेड़ में वही ऑपरेटर अलग गिने? हाँ। पेड़, चपटी स्ट्रिंग नहीं।
- ओवरफ्लो? जब तक न कहें
int। लंबी स्ट्रिंग पर गिनती तेज़ी से बढ़ती है।
३. पहले सोचो
ब्रूट: हर कट आज़माओ
कई ऑपरेटर वाले पूर्ण कोष्ठक में कोई एक ऑपरेटर जड़ होता है (आखिरी लागू)। वह विषम इंडेक्स i पर बैठता है। बाईं उप-स्ट्रिंग expr[0..i), दाईं expr[i+1..]।
पुनरावृत्ति से:
१. लंबाई १ हो: बिट लक्ष्य से मिले तो १, नहीं तो ०।
२. हर ऑपरेटर इंडेक्स i = १, ३, ५, ... पर:
- बायाँ सत्य/असत्य कितनी बार।
- दायाँ सत्य/असत्य कितनी बार।
- ऑपरेटर से जोड़कर इस कट पर लक्ष्य कितनी बार। ३. सभी जड़ ऑपरेटर स्थितियों पर जोड़ो।
यह सही है और पूर्ण कोष्ठक की परिभाषा से मेल खाता है।
सत्य तालिका से जोड़ना
एक तय जड़ ऑपरेटर के लिए:
lt,lf= बायाँ सत्य / असत्य तरीकेrt,rf= दायाँ सत्य / असत्य तरीके
इस कट के कुल तरीके (कोई भी नतीजा): (lt + lf) * (rt + rf)।
कट सत्य कब:
| ऑपरेटर | सत्य जब |
|---|---|
& |
बायाँ सत्य और दायाँ सत्य → lt * rt |
| |
दोनों असत्य न हों → lt*rt + lt*rf + lf*rt |
^ |
पक्ष अलग हों → lt*rf + lf*rt |
कट असत्य = कट का कुल घटा सत्य तरीके (या उल्टी तालिका लिखो)।
चुनी गिनती को इस व्यंजक और लक्ष्य के उत्तर में जोड़ो।
मेमो क्यों
एक ही उप-स्ट्रिंग (जैसे "0|1") कई बार पूछी जाती है, एक बार सत्य के लिए, एक बार असत्य के लिए, अलग पैरेंट से। मेमो की कुंजी (उप-स्ट्रिंग, वांछित नतीजा) या शुरू/अंत इंडेक्स प्लस नतीजा।
बिना मेमो काम बाइनरी पेड़ों की संख्या पर चलता है, जो कैटलान संख्याओं जैसा: ऑपरेटरों में घातीय।
ओ(एन²) उप-स्ट्रिंग और २ नतीजों पर मेमो से हर अवस्था ओ(एन) कट देखती है, इंडेक्स सावधानी से रखो तो लगभग ओ(एन³)। नई स्ट्रिंग की जगह इंडेक्स स्थिरांक साफ रखते हैं।
इंडेक्स रूप (कोड के लिए बेहतर)
मूल कैरेक्टर ऐरे पर count(start, end, result) मतलब expr[start..end) (end बाहर, end - start विषम)।
ऑपरेटर start से विषम ऑफसेट पर। लूप k = start + 1; k < end; k += 2।
४. जावा समाधान
उप-स्ट्रिंग पर मेमो पुनरावृत्ति (स्ट्रिंग कुंजी)
साफ पहला संस्करण। बोर्ड पर समझाना आसान।
import java.util.HashMap;
import java.util.Map;
public class BooleanEvaluation {
public static int countEval(String expr, boolean result) {
if (expr == null || expr.isEmpty()) {
return 0;
}
return ways(expr, result, new HashMap<String, Integer>());
}
private static int ways(String expr, boolean result, Map<String, Integer> memo) {
if (expr.length() == 0) {
return 0;
}
if (expr.length() == 1) {
boolean bit = expr.charAt(0) == '1';
return bit == result ? 1 : 0;
}
String key = result + "#" + expr;
if (memo.containsKey(key)) {
return memo.get(key);
}
int total = 0;
// operators sit at odd indices: 1, 3, 5, ...
for (int i = 1; i < expr.length(); i += 2) {
char op = expr.charAt(i);
String left = expr.substring(0, i);
String right = expr.substring(i + 1);
int leftTrue = ways(left, true, memo);
int leftFalse = ways(left, false, memo);
int rightTrue = ways(right, true, memo);
int rightFalse = ways(right, false, memo);
int waysTrue = 0;
if (op == '&') {
waysTrue = leftTrue * rightTrue;
} else if (op == '|') {
waysTrue = leftTrue * rightTrue
+ leftTrue * rightFalse
+ leftFalse * rightTrue;
} else if (op == '^') {
waysTrue = leftTrue * rightFalse + leftFalse * rightTrue;
}
int totalForSplit = (leftTrue + leftFalse) * (rightTrue + rightFalse);
int waysForTarget = result ? waysTrue : (totalForSplit - waysTrue);
total += waysForTarget;
}
memo.put(key, total);
return total;
}
}
वही विचार इंडेक्स से (कम स्ट्रिंग आवंटन)
public static int countEvalIndexed(String expr, boolean result) {
if (expr == null || expr.isEmpty()) {
return 0;
}
// memo[start][end][0=false,1=true] ; -1 means unknown
int n = expr.length();
int[][][] memo = new int[n][n + 1][2];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= n; j++) {
memo[i][j][0] = -1;
memo[i][j][1] = -1;
}
}
return waysIdx(expr, 0, n, result, memo);
}
private static int waysIdx(String expr, int start, int end, boolean result, int[][][] memo) {
int r = result ? 1 : 0;
if (memo[start][end][r] != -1) {
return memo[start][end][r];
}
if (end - start == 1) {
boolean bit = expr.charAt(start) == '1';
int ans = bit == result ? 1 : 0;
memo[start][end][r] = ans;
return ans;
}
int total = 0;
for (int k = start + 1; k < end; k += 2) {
char op = expr.charAt(k);
int lt = waysIdx(expr, start, k, true, memo);
int lf = waysIdx(expr, start, k, false, memo);
int rt = waysIdx(expr, k + 1, end, true, memo);
int rf = waysIdx(expr, k + 1, end, false, memo);
int waysTrue = 0;
if (op == '&') {
waysTrue = lt * rt;
} else if (op == '|') {
waysTrue = lt * rt + lt * rf + lf * rt;
} else if (op == '^') {
waysTrue = lt * rf + lf * rt;
}
int splitTotal = (lt + lf) * (rt + rf);
total += result ? waysTrue : (splitTotal - waysTrue);
}
memo[start][end][r] = total;
return total;
}
वॉकथ्रू: "1^0|1" और लक्ष्य सत्य
ऑपरेटर इंडेक्स १ (^) और ३ (|) पर।
जड़ ^: बायाँ "1", दायाँ "0|1"।
- बायाँ: १ सत्य, ० असत्य।
- दायाँ
"0|1": एक ही पेड़,0|1→ सत्य। तो दायाँ सत्य = १, दायाँ असत्य = ०। ^सत्य जब पक्ष अलग:1 * 0 + 0 * 1 = 0। इस जड़ पर सत्य ० तरीके।
जड़ |: बायाँ "1^0", दायाँ "1"।
- बायाँ
"1^0": एक पेड़, सत्य। बायाँ सत्य = १, बायाँ असत्य = ०। - दायाँ: सत्य = १।
|सत्य:1*1 + 1*0 + 0*1 = 1।
कुल सत्य तरीके = ० + १ = १।
असत्य तरीके = १ (दूसरी जड़)। जाँच: countEval("1^0|1", false) १ होना चाहिए।
वॉकथ्रू: क्लासिक "1^0|0|1" → असत्य = २
तीन ऑपरेटर, इसलिए कैटलान सी₃ = ५ पूर्ण कोष्ठक। ठीक दो असत्य देते हैं। मेमो पुनरावृत्ति हर ऑपरेटर को जड़ बनाकर बच्चों की गिनती जोड़ती है; इंटरव्यू में पेड़ हाथ से नहीं गिनाते, पर छोटी स्ट्रिंग पर विश्वास जमाने को गिन सकते हो।
धुआँ परीक्षण:
public static void main(String[] args) {
System.out.println(countEval("1", true)); // 1
System.out.println(countEval("1", false)); // 0
System.out.println(countEval("1^0|1", true)); // 1
System.out.println(countEval("1^0|1", false)); // 1
System.out.println(countEval("1^0|0|1", false)); // 2
System.out.println(countEval("0&0&0&1^1|0", true)); // 10
}
५. जटिलता तालिका
मान लो एन = स्ट्रिंग की लंबाई (लगभग २एम + १, एम ऑपरेटर)।
| तरीका | समय | अतिरिक्त स्थान | नोट |
|---|---|---|---|
| बिना मेमो पुनरावृत्ति | घातीय (कैटलान) | ओ(एम) स्टैक | सिर्फ बहुत छोटी इनपुट |
| उप-स्ट्रिंग मेमो | इंडेक्स डीपी से ओ(एन³) जैसा | ओ(एन²) अवस्थाएँ | इंटरव्यू का पसंदीदा उत्तर |
| लंबाई पर नीचे-से-ऊपर डीपी | वही क्रम | ओ(एन²) | वही पुनरावृत्ति छोटा→बड़ा |
ओ(एन²) अंतरालों में से हर एक के २ नतीजा रूप। हर अंतराल ओ(एन) जड़ आज़माता है। गुणा घन काम। स्ट्रिंग-कुंजी मेमो वही असिम्प्टोटिक विचार, ज़्यादा आवंटन के साथ।
६. किनारे के केस और आम गलतियाँ
इंटरव्यूअर ये छूते हैं:
- एक बिट
"0"/"1"लक्ष्य मेल या बेमेल। - एक ऑपरेटर
"1&0","1|0","1^0": एक पेड़; उत्तर ० या १। |के साथ सब असत्य बिट: हर उप-व्यंजक असत्य रहे तभी पूरा असत्य; तालिका चलाओ, अनुमान मत लगाओ।- लक्ष्य असत्य: सिर्फ सत्य तालिका लिख बैठना आसान है।
total - waysTrueया दोनों लिखो। - सम लंबाई या आखिरी ऑपरेटर: अवैध इनपुट; अपना मान बताओ।
- बड़ा एन: गिनती
intपार कर सकती है। ज़रूरत हो तोlongनाम लो।
आम गलतियाँ:
१. सामान्य प्राथमिकता लगाना, शुद्ध कोष्ठक नहीं। समस्या सामान्य प्राथमिकता अनदेखी करती है; हर पेड़ मान्य।
२. हर इंडेक्स पर कट, बिट वाली जगह भी। सिर्फ विषम इंडेक्स (ऑपरेटर) जड़ हैं।
३. मेमो कुंजी में नतीजा न होना। एक ही उप-स्ट्रिंग के सत्य और असत्य तरीके अलग। दोनों कैश करो या कुंजी में नतीजा रखो।
४. | या ^ के गलत गुणन। कोड से पहले बोर्ड पर तीन पंक्ति की तालिका लिखो।
५. एक लक्ष्य माँगने पर सब पेड़ लौटाना। हमेशा result से छानो।
६. उप-स्ट्रिंग पर ऑफ-बाय-वन (substring(i) बनाम substring(i+1)). i वाला ऑपरेटर किसी पक्ष का हिस्सा नहीं।
७. दोस्त को समझाने वाला सार
बूलियन मूल्यांकन &, |, ^ वाले ०/१ व्यंजक की उन कोष्ठक रचनाओं को गिनता है जो दिए सत्य-मान पर पहुँचें।
१. कोई ऑपरेटर आखिरी लागू होता है (पार्स पेड़ की जड़)। २. उस ऑपरेटर के बाएँ-दाएँ काटो। हर पक्ष कितनी बार सत्य/असत्य, पुनरावृत्ति से गिनो। ३. ऑपरेटर की सत्य तालिका से सत्य तरीके जोड़ो (असत्य = कुल घटा सत्य)। ४. हर संभावित जड़ ऑपरेटर पर जोड़ो। ५. उप-स्ट्रिंग (या शुरू/अंत) प्लस वांछित नतीजे पर मेमो करो ताकि कैटलान विस्फोट मर जाए।
"1^0|1" चला सको, & / | / ^ के सत्य-गिन भर सको, और बता सको मेमो कुंजी में लक्ष्य बूलियन क्यों है, तो समस्या ८.१४ तुम्हारी है। अध्याय ८ की पुनरावृत्ति और गतिशील प्रोग्रामिंग क्लासिक "कोष्ठक के तरीके गिनो" पैटर्न पर बंद होती है।
सीरीज़
- गाइड: सीटीसीआई सीरीज़ गाइड
- पिछला: बक्सों का ढेर
- अगला: स्टॉक डेटा