टीएल;डीआर
- समस्या: उत्पादन-स्तरीय दक्षता के साथ सीटीसीआई समस्या १०.८ में महारत हासिल करना।
- दृष्टिकोण: सीटीसीआई समस्या १०.८: केवल ४ केबी रैम का उपयोग करके १ से ३२,००० तक की संख्याओं के एरे में सभी डुप्लिकेट खोजें।
- जटिलता: इष्टतम समय और मेमोरी संतुलन।
यह लेख सीटीसीआई समस्या १०.८ का एक स्पष्ट और शुरुआती-अनुकूल विवरण प्रदान करता है। हम समस्या के कथन की जांच करते हैं, इष्टतम समाधान की तुलना करते हैं और जावा (जावा) कोड लिखते हैं।
१. वास्तविक जीवन की उपमा
सीटीसीआई समस्या १०.८ को वास्तविक जीवन में वस्तुओं को कुशलतापूर्वक व्यवस्थित करने की तरह सोचें। सही डेटा संरचना का चयन अनावश्यक पुनरावृत्तियों को समाप्त करता है।
२. स्पष्ट समस्या कथन
समस्या १०.८: सीटीसीआई समस्या १०.८: केवल ४ केबी रैम का उपयोग करके १ से ३२,००० तक की संख्याओं के एरे में सभी डुप्लिकेट खोजें।
३. इष्टतम दृष्टिकोण और कार्यान्वयन
public class FindDuplicates {
static class BitSetCustom {
int[] bitset;
public BitSetCustom(int size) {
bitset = new int[(size >> 5) + 1];
}
public boolean get(int pos) {
int wordNumber = (pos >> 5);
int bitNumber = (pos & 0x1F);
return (bitset[wordNumber] & (1 << bitNumber)) != 0;
}
public void set(int pos) {
int wordNumber = (pos >> 5);
int bitNumber = (pos & 0x1F);
bitset[wordNumber] |= (1 << bitNumber);
}
}
public static void checkDuplicates(int[] array) {
BitSetCustom bs = new BitSetCustom(32000);
for (int num : array) {
int num0 = num - 1;
if (bs.get(num0)) {
System.out.println(num);
} else {
bs.set(num0);
}
}
}
}
४. समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी)
| मीट्रिक | जटिलता | विवरण |
|---|---|---|
| समय जटिलता | ओ(एन) / ओ(लॉग एन) | डेटा के माध्यम से इष्टतम पास |
| स्थान जटिलता | ओ(१) / ओ(एन) | मेमोरी सीमाएं बनी रहीं |
५. सीमांत मामले (एज केसेस) और सारांश
कोडिंग इंटरव्यू में हमेशा सीमांत स्थितियों, शून्य (null) इनपुट और एरे आकार की सीमाओं की जांच करें।