टीएल;डीआर
- समस्या: उत्पादन-स्तरीय दक्षता के साथ सीटीसीआई समस्या १०.३ में महारत हासिल करना।
- दृष्टिकोण: सीटीसीआई समस्या १०.३: किसी अज्ञात ऑफ़सेट द्वारा घुमाए गए सॉर्ट किए गए एरे में तत्व खोजने के लिए संशोधित बाइनरी सर्च।
- जटिलता: इष्टतम समय और मेमोरी संतुलन।
यह लेख सीटीसीआई समस्या १०.३ का एक स्पष्ट और शुरुआती-अनुकूल विवरण प्रदान करता है। हम समस्या के कथन की जांच करते हैं, इष्टतम समाधान की तुलना करते हैं और जावा (जावा) कोड लिखते हैं।
१. वास्तविक जीवन की उपमा
सीटीसीआई समस्या १०.३ को वास्तविक जीवन में वस्तुओं को कुशलतापूर्वक व्यवस्थित करने की तरह सोचें। सही डेटा संरचना का चयन अनावश्यक पुनरावृत्तियों को समाप्त करता है।
२. स्पष्ट समस्या कथन
समस्या १०.३: सीटीसीआई समस्या १०.३: किसी अज्ञात ऑफ़सेट द्वारा घुमाए गए सॉर्ट किए गए एरे में तत्व खोजने के लिए संशोधित बाइनरी सर्च।
३. इष्टतम दृष्टिकोण और कार्यान्वयन
public class SearchRotatedArray {
public static int search(int[] a, int left, int right, int x) {
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (a[mid] == x) return mid;
if (a[left] < a[mid]) { // Left half is normally sorted
if (x >= a[left] && x < a[mid]) return search(a, left, mid - 1, x);
else return search(a, mid + 1, right, x);
} else if (a[mid] < a[left]) { // Right half is normally sorted
if (x > a[mid] && x <= a[right]) return search(a, mid + 1, right, x);
else return search(a, left, mid - 1, x);
} else { // Duplicates handling
int location = -1;
if (a[mid] != a[right]) location = search(a, mid + 1, right, x);
if (location == -1) location = search(a, left, mid - 1, x);
return location;
}
}
}
४. समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी)
| मीट्रिक | जटिलता | विवरण |
|---|---|---|
| समय जटिलता | ओ(एन) / ओ(लॉग एन) | डेटा के माध्यम से इष्टतम पास |
| स्थान जटिलता | ओ(१) / ओ(एन) | मेमोरी सीमाएं बनी रहीं |
५. सीमांत मामले (एज केसेस) और सारांश
कोडिंग इंटरव्यू में हमेशा सीमांत स्थितियों, शून्य (null) इनपुट और एरे आकार की सीमाओं की जांच करें।