टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ८.४: सेट के हर सबसेट लौटाओ, खाली और पूरा भी। छोटे पावर सेट से रिकर्सिव बिल्ड, वैकल्पिक बिट-मास्क गणना, और जावा कोड।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
तुम्हारे पास अलग-अलग स्टिकरों का थैला है: {ए, बी, सी}। हर स्टिकर अंदर या बाहर, तो कितने अलग थैले बन सकते हैं? खाली थैला गिना जाता है। भरा थैला गिना जाता है। जोड़े गिने जाते हैं। थैलों की वह सूची पावर सेट है: मूल सेट के सभी सबसेट।
यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू रिकर्शन वॉर्मअप का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ८, रिकर्शन और डायनामिक प्रोग्रामिंग, समस्या ८.४।
१. रोज़मर्रा की उपमा
तीन टॉपिंग वाले सैंडविच शॉप सोचो: लेट्यूस, टमाटर, चीज़। हर टॉपिंग हाँ या ना। काउंटर पर ऑर्डर:
- बिना टॉपिंग
- सिर्फ लेट्यूस
- सिर्फ टमाटर
- सिर्फ चीज़
- लेट्यूस + टमाटर
- लेट्यूस + चीज़
- टमाटर + चीज़
- तीनों
यह २ × २ × २ = ८ ऑर्डर हैं। तीन तत्वों वाले सेट के पावर सेट जितनी ही गिनती: न तत्वों पर २^न सबसेट।
मेन्यू रिकर्सिव बढ़ सकता है। शून्य टॉपिंग पर सिर्फ खाली ऑर्डर। चीज़ जोड़ो: पुराने ऑर्डर रहें, और हर पुराने की कॉपी चीज़ के साथ। टमाटर उसी तरह। लेट्यूस उसी तरह। यही रिकर्सिव बिल्ड है। बिट मास्क वही काम ० से २^न - १ तक लूप से करते हैं, जहाँ हर बिट कहता है "यह टॉपिंग शामिल करो"।
२. सादा समस्या कथन
इनपुट: अलग-अलग तत्वों का सेट। कोड में अक्सर यूनिक मानों की लिस्ट या ऐरे (जैसे अक्षर या पूर्णांक)।
आउटपुट: सभी सबसेट का संग्रह। सबसेटों का क्रम आमतौर पर मायने नहीं रखता। सबसेट के अंदर क्रम डेमो के लिए इनपुट क्रम रख सकते हो।
शामिल होना चाहिए:
- खाली सबसेट
{} - पूरा सेट
- बीच का हर प्रोपर सबसेट
उदाहरण:
Input: {1, 2, 3}
Power set (8 subsets):
{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}
इंटरव्यू में साफ करो:
- तत्व यूनिक? (क्लासिक पावर सेट के लिए हाँ। डुप्लिकेट अलग समस्या।)
- रिटर्न टाइप: जावा में
List<List<T>>आम है। - कॉलर की लिस्ट म्यूटेट? स्टोर करते समय हर सबसेट की डिफेंसिव कॉपी बेहतर।
- न छोटा? आउटपुट साइज़ २^न है। न = २० पर लगभग दस लाख सबसेट। ज़ोर से बोलो।
३. पहले सोचो
पहले गिनती
| न | सबसेटों की संख्या |
|---|---|
| ० | १ (सिर्फ {}) |
| १ | २ |
| २ | ४ |
| ३ | ८ |
| न | २^न |
हर सबसेट लिस्ट करना हो तो ओ(२^न · पॉली(न)) से बेहतर नहीं कर सकते। जवाब का स्पेस भी उसी क्रम का।
रिकर्सिव आइडिया (न-१ से बनाओ)
पी(एस) को एस का पावर सेट मानो।
१. अगर एस खाली है, पी(एस) = { {} }।
२. नहीं तो एक तत्व ई चुनो और रेस्ट = एस बिना ई।
३. पी(रेस्ट) निकालो।
४. पी(रेस्ट) के हर सबसेट सब के लिए सब ज्यों का त्यों रखो, और सब ∪ {ई} भी बनाओ।
हर सबसेट में ई है या नहीं। ये दो परिवार बिना ओवरलैप पावर सेट ढकते हैं।
P({1,2}) with e=2, rest={1}:
P(rest) = { {}, {1} }
without 2: {}, {1}
with 2: {2}, {1,2}
result: {}, {1}, {2}, {1,2}
इंडेक्स रिकर्शन (शामिल / बाहर)
वही गणित, अलग कोड आकार: मौजूदा पथ के साथ इंडेक्स ० .. न-१ चलो।
- इंडेक्स
आईपर तत्वआईको बाहर रखो, फिर शामिल करो (पुश, रिकर्स, पॉप)। - जब
आई == न, मौजूदा पथ की कॉपी जवाब में डालो।
यह क्लासिक बैकट्रैकिंग है। कॉल ट्री आसान दिखता है, इसलिए इंटरव्यूअर अक्सर पसंद करते हैं।
बिट मास्क आइडिया
० से २^न - १ तक ठीक २^न पूर्णांक हैं। मास्क म के लिए बिट जे तय करता है कि तत्व जे सबसेट में है या नहीं:
n = 3, elements [a, b, c]
mask 0 = 000 -> {}
mask 1 = 001 -> {a}
mask 2 = 010 -> {b}
mask 3 = 011 -> {a,b}
mask 4 = 100 -> {c}
...
mask 7 = 111 -> {a,b,c}
रिकर्शन स्टैक नहीं। रिकर्सिव के बाद साफ दूसरा तरीका।
क्या न करें
- सिर्फ निश्चित न के लिए नेस्टेड लूप (गहराई हार्ड-कोड)।
- कॉपी किए बिना एक शेयर लिस्ट जवाब में डालना (स्टोर हुए सभी सबसेट एक जैसे हो जाते हैं)।
- खाली सेट भूलना (या पूरा सेट)।
- जब लिस्ट-ऑफ-लिस्ट काफी हो, बिना साफ टाइप/हैश कहानी के सेट-ऑफ-सेट।
४. जावा समाधान
४.१ छोटे पावर सेट से रिकर्सिव बिल्ड
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Power set by growing from P(rest).
* Each new element doubles the number of subsets.
*/
public class PowerSetRecursive {
public static List<List<Integer>> powerSet(List<Integer> set) {
List<List<Integer>> result = new ArrayList<>();
if (set == null) {
return result;
}
// start with the empty subset
result.add(new ArrayList<>());
for (int element : set) {
// snapshot size: only clone subsets built so far
int sizeBefore = result.size();
for (int i = 0; i < sizeBefore; i++) {
List<Integer> withElement = new ArrayList<>(result.get(i));
withElement.add(element);
result.add(withElement);
}
}
return result;
}
public static void main(String[] args) {
List<Integer> set = Arrays.asList(1, 2, 3);
List<List<Integer>> all = powerSet(set);
System.out.println(all.size()); // 8
for (List<Integer> subset : all) {
System.out.println(subset);
}
}
}
{१, २, ३} का वॉक-थ्रू:
| चरण | जोड़ा गया तत्व | चरण के बाद सबसेट |
|---|---|---|
| शुरू | - | {} |
| १ | १ | {}, {१} |
| २ | २ | {}, {१}, {२}, {१,२} |
| ३ | ३ | आठ सबसेट: पिछले चार प्लस हर एक में ३ |
४.२ बैकट्रैक शामिल / बाहर
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PowerSetBacktrack {
public static List<List<Integer>> powerSet(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null) {
return result;
}
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private static void backtrack(
int[] nums,
int index,
List<Integer> path,
List<List<Integer>> result) {
if (index == nums.length) {
// must copy: path is reused on the way back
result.add(new ArrayList<>(path));
return;
}
// exclude nums[index]
backtrack(nums, index + 1, path, result);
// include nums[index]
path.add(nums[index]);
backtrack(nums, index + 1, path, result);
path.remove(path.size() - 1); // pop
}
public static void main(String[] args) {
List<List<Integer>> all = powerSet(new int[] {1, 2, 3});
System.out.println(all.size()); // 8
for (List<Integer> subset : all) {
System.out.println(subset);
}
}
}
दो तत्वों [ए, बी] का कॉल ट्री:
[]
/ \
exclude a include a
[] [a]
/ \ / \
exclude b include b exclude b include b
[] [b] [a] [a,b]
चार लीफ, चार सबसेट। वही पैटर्न न तक फैलता है।
४.३ वैकल्पिक बिट मास्क गणना
import java.util.ArrayList;
import java.util.List;
public class PowerSetBitMask {
public static List<List<Integer>> powerSet(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null) {
return result;
}
int n = nums.length;
// 1 << n is 2^n. For n >= 31 use care with int overflow.
int total = 1 << n;
for (int mask = 0; mask < total; mask++) {
List<Integer> subset = new ArrayList<>();
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) != 0) {
subset.add(nums[j]);
}
}
result.add(subset);
}
return result;
}
public static void main(String[] args) {
List<List<Integer>> all = powerSet(new int[] {1, 2, 3});
System.out.println(all.size()); // 8
for (List<Integer> subset : all) {
System.out.println(subset);
}
}
}
[१, २, ३] के लिए मास्क डेमो:
| मास्क | बाइनरी | सबसेट |
|---|---|---|
| ० | ००० | {} |
| १ | ००१ | {१} |
| २ | ०१० | {२} |
| ३ | ०११ | {१, २} |
| ४ | १०० | {३} |
| ५ | १०१ | {१, ३} |
| ६ | ११० | {२, ३} |
| ७ | १११ | {१, २, ३} |
इंटरव्यू में किससे शुरू करें? शामिल/बाहर या पी(रेस्ट) से बढ़ाना। बिट मास्क को साफ इटरेटिव विकल्प के रूप में नाम लो। तीनों से वही २^न सबसेट बनते हैं।
५. जटिलता तालिका
| तरीका | समय | अतिरिक्त स्पेस (आउटपुट के अलावा) | नोट |
|---|---|---|---|
| पी(रेस्ट) से बढ़ना | ओ(न · २^न) | रिजल्ट ग्रोथ के अलावा ओ(१) | २^न सबसेट में समय के साथ तक न तत्व कॉपी |
| बैकट्रैकिंग | ओ(न · २^न) | ओ(न) रिकर्शन + पथ | २^न लीफ; पथ कॉपी ओ(न) |
| बिट मास्क | ओ(न · २^न) | रिजल्ट के अलावा ओ(१) | सादे लूप; बड़े न पर 1 << n सावधानी |
| आउटपुट साइज़ | - | ओ(न · २^न) | सब लिस्ट करो तो घटता नहीं |
इंटरव्यूअर कोड से पहले २^न सबसेट सुनना चाहते हैं। "बेहतर हो सकता है?" पर पूरा एन्यूमरेशन नहीं; सिर्फ आलसी जनरेशन या अतिरिक्त शर्तों पर जल्दी रुकना।
६. एज केस और आम गलतियाँ
इंटरव्यूअर ये छेदते हैं:
- खाली इनपुट: एक खाली सबसेट वाली लिस्ट लौटाओ, सबसेटों की खाली लिस्ट नहीं।
- नल इनपुट: खाली रिजल्ट या खाली सेट मानो। एक चुनो और बोलो।
- एक तत्व: सिर्फ
{}और{एक्स}। - बड़ा न: २^२० लगभग १०^६; २^३० हल्के में नहीं समाता। मेमोरी और न ≥ ३१ पर
1 << nओवरफ्लो का ज़िक्र (1L << nया न सीमित)। - इनपुट में डुप्लिकेट: क्लासिक पावर सेट यूनिक मानता है। डुप्लिकेट में सॉर्ट + स्किप (सबसेट २), अलग समस्या।
- शेयर म्यूटेबल पथ:
new ArrayList<>(path)भूलना सभी स्टोर सबसेट एक जैसे बना देता है। - बढ़ती लिस्ट पर
sizeम्यूटेट बिना स्नैपशॉट: अनंत लूप या गलत दोगुना। पहलेsizeBeforeस्नैपशॉट। - क्रम की शर्तें: अगर सबसेट सॉर्टेड या लेक्सिको चाहिए, हर सबसेट सॉर्ट करो या फिक्स्ड इंडेक्स क्रम में जनरेट करके आखिर में बाहरी लिस्ट सॉर्ट करो।
आम गलतियाँ:
१. खाली सबसेट गायब। बेस केस गलत।
२. स्टोर पर कॉपी नहीं। सभी जवाब एक लिस्ट के एलियास।
३. सिर्फ न = ३ के लिए हार्ड-कोडेड नेस्टेड लूप।
४. न = ३१ पर 1 << n इंट ओवरफ्लो (साइन बिट)। सीमाएँ बोलो।
५. पावर सेट को परम्यूटेशन समझना। सबसेट के अंदर क्रम नया सबसेट नहीं बनाता; {१,२} और {२,१} एक ही सेट।
मिनिमल स्मोक आइडिया:
List<List<Integer>> p0 = PowerSetRecursive.powerSet(List.of());
assert p0.size() == 1 && p0.get(0).isEmpty();
List<List<Integer>> p1 = PowerSetRecursive.powerSet(List.of(7));
assert p1.size() == 2;
List<List<Integer>> p3 = PowerSetBitMask.powerSet(new int[] {1, 2, 3});
assert p3.size() == 8;
७. दोस्त को समझाने वाला सार
इंटरव्यू भाषा में पावर सेट:
१. न अलग तत्वों वाले सेट में २^न सबसेट: हर तत्व अंदर या बाहर।
२. हमेशा {} और पूरा सेट शामिल करो।
३. रिकर्सिव बढ़ना: { {} } से शुरू। हर नए तत्व पर मौजूदा हर सबसेट क्लोन करो और क्लोन में तत्व जोड़ो।
४. बैकट्रैक: हर इंडेक्स पर बाहर फिर शामिल; लीफ पर पथ कॉपी।
५. बिट मास्क: मास्क ० .. २^न - १ पर बिट जे १ हो तो तत्व जे शामिल।
६. सब लिस्ट करने वाली आम फॉर्मूलेशन में समय और आउटपुट स्पेस दोनों Θ(न · २^न)।
७. स्टोर करते समय सबसेट कॉपी करो। शेयर पथ लिस्ट का एलियास न बनाओ।
अगर {१,२} का शामिल/बाहर ट्री खींच सकते हो, तीसरा तत्व जोड़ते समय सबसेट दोगुने कर सकते हो, और बिना शेयर-लिस्ट बग के रिकर्शन या बिट-मास्क लूप लिख सकते हो, समस्या ८.४ तुम्हारी है।
सीरीज़
- गाइड: सीटीसीआई सीरीज़ गाइड
- पिछला: मैजिक इंडेक्स
- अगला: रिकर्सिव मल्टीप्लाई