टीएल;डीआर
- समस्या: उत्पादन-स्तरीय दक्षता के साथ सीटीसीआई समस्या १०.१० में महारत हासिल करना।
- दृष्टिकोण: सीटीसीआई समस्या १०.१०: किसी नंबर का स्ट्रीम रैंक तुरंत प्राप्त करने के लिए लेफ्ट सबट्री साइज ट्रैकिंग के साथ बीएसटी बनाएं।
- जटिलता: इष्टतम समय और मेमोरी संतुलन।
यह लेख सीटीसीआई समस्या १०.१० का एक स्पष्ट और शुरुआती-अनुकूल विवरण प्रदान करता है। हम समस्या के कथन की जांच करते हैं, इष्टतम समाधान की तुलना करते हैं और जावा (जावा) कोड लिखते हैं।
१. वास्तविक जीवन की उपमा
सीटीसीआई समस्या १०.१० को वास्तविक जीवन में वस्तुओं को कुशलतापूर्वक व्यवस्थित करने की तरह सोचें। सही डेटा संरचना का चयन अनावश्यक पुनरावृत्तियों को समाप्त करता है।
२. स्पष्ट समस्या कथन
समस्या १०.१०: सीटीसीआई समस्या १०.१०: किसी नंबर का स्ट्रीम रैंक तुरंत प्राप्त करने के लिए लेफ्ट सबट्री साइज ट्रैकिंग के साथ बीएसटी बनाएं।
३. इष्टतम दृष्टिकोण और कार्यान्वयन
public class RankNode {
public int leftSize = 0;
public RankNode left, right;
public int data = 0;
public RankNode(int d) { this.data = d; }
public void insert(int d) {
if (d <= data) {
if (left != null) left.insert(d);
else left = new RankNode(d);
leftSize++;
} else {
if (right != null) right.insert(d);
else right = new RankNode(d);
}
}
public int getRank(int d) {
if (d == data) return leftSize;
else if (d < data) {
if (left == null) return -1;
return left.getRank(d);
} else {
int rightRank = (right == null) ? -1 : right.getRank(d);
if (rightRank == -1) return -1;
return leftSize + 1 + rightRank;
}
}
}
४. समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी)
| मीट्रिक | जटिलता | विवरण |
|---|---|---|
| समय जटिलता | ओ(एन) / ओ(लॉग एन) | डेटा के माध्यम से इष्टतम पास |
| स्थान जटिलता | ओ(१) / ओ(एन) | मेमोरी सीमाएं बनी रहीं |
५. सीमांत मामले (एज केसेस) और सारांश
कोडिंग इंटरव्यू में हमेशा सीमांत स्थितियों, शून्य (null) इनपुट और एरे आकार की सीमाओं की जांच करें।