टीएल;डीआर
- समस्या: उत्पादन-स्तरीय दक्षता के साथ सीटीसीआई समस्या १०.७ में महारत हासिल करना।
- दृष्टिकोण: सीटीसीआई समस्या १०.७: सीमित रैम में बिटसेट और टू-पास चंकिंग का उपयोग करके ४ अरब नंबरों में से गायब संख्या खोजें।
- जटिलता: इष्टतम समय और मेमोरी संतुलन।
यह लेख सीटीसीआई समस्या १०.७ का एक स्पष्ट और शुरुआती-अनुकूल विवरण प्रदान करता है। हम समस्या के कथन की जांच करते हैं, इष्टतम समाधान की तुलना करते हैं और जावा (जावा) कोड लिखते हैं।
१. वास्तविक जीवन की उपमा
सीटीसीआई समस्या १०.७ को वास्तविक जीवन में वस्तुओं को कुशलतापूर्वक व्यवस्थित करने की तरह सोचें। सही डेटा संरचना का चयन अनावश्यक पुनरावृत्तियों को समाप्त करता है।
२. स्पष्ट समस्या कथन
समस्या १०.७: सीटीसीआई समस्या १०.७: सीमित रैम में बिटसेट और टू-पास चंकिंग का उपयोग करके ४ अरब नंबरों में से गायब संख्या खोजें।
३. इष्टतम दृष्टिकोण और कार्यान्वयन
public class MissingInt {
public static int findOpenNumber(Scanner scanner) {
long numberOfInts = ((long) Integer.MAX_VALUE) + 1;
byte[] bitfield = new byte[(int) (numberOfInts / 8)];
while (scanner.hasNextInt()) {
int n = scanner.nextInt();
bitfield[n / 8] |= 1 << (n % 8);
}
for (int i = 0; i < bitfield.length; i++) {
for (int j = 0; j < 8; j++) {
if ((bitfield[i] & (1 << j)) == 0) {
return i * 8 + j;
}
}
}
return -1;
}
}
४. समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी)
| मीट्रिक | जटिलता | विवरण |
|---|---|---|
| समय जटिलता | ओ(एन) / ओ(लॉग एन) | डेटा के माध्यम से इष्टतम पास |
| स्थान जटिलता | ओ(१) / ओ(एन) | मेमोरी सीमाएं बनी रहीं |
५. सीमांत मामले (एज केसेस) और सारांश
कोडिंग इंटरव्यू में हमेशा सीमांत स्थितियों, शून्य (null) इनपुट और एरे आकार की सीमाओं की जांच करें।