टीएल;डीआर
- समस्या: उत्पादन-स्तरीय दक्षता के साथ सीटीसीआई समस्या ९.२ में महारत हासिल करना।
- दृष्टिकोण: सीटीसीआई समस्या ९.२: एक अरब-नोड वाले सोशल ग्राफ में दो उपयोगकर्ताओं के बीच कनेक्शन पथ की गणना करने वाला वितरित सिस्टम डिजाइन करें।
- जटिलता: इष्टतम समय और मेमोरी संतुलन।
यह लेख सीटीसीआई समस्या ९.२ का एक स्पष्ट और शुरुआती-अनुकूल विवरण प्रदान करता है। हम समस्या के कथन की जांच करते हैं, इष्टतम समाधान की तुलना करते हैं और जावा (जावा) कोड लिखते हैं।
१. वास्तविक जीवन की उपमा
सीटीसीआई समस्या ९.२ को वास्तविक जीवन में वस्तुओं को कुशलतापूर्वक व्यवस्थित करने की तरह सोचें। सही डेटा संरचना का चयन अनावश्यक पुनरावृत्तियों को समाप्त करता है।
२. स्पष्ट समस्या कथन
समस्या ९.२: सीटीसीआई समस्या ९.२: एक अरब-नोड वाले सोशल ग्राफ में दो उपयोगकर्ताओं के बीच कनेक्शन पथ की गणना करने वाला वितरित सिस्टम डिजाइन करें।
३. इष्टतम दृष्टिकोण और कार्यान्वयन
public class BidirectionalBreadthFirstSearch {
public List<Long> findShortestPath(Map<Long, List<Long>> graph, long source, long target) {
Queue<Long> qSource = new LinkedList<>(), qTarget = new LinkedList<>();
Map<Long, Long> parentsSource = new HashMap<>(), parentsTarget = new HashMap<>();
qSource.add(source); parentsSource.put(source, null);
qTarget.add(target); parentsTarget.put(target, null);
while (!qSource.isEmpty() && !qTarget.isEmpty()) {
Long intersect = searchLevel(graph, qSource, parentsSource, parentsTarget);
if (intersect != null) return mergePaths(parentsSource, parentsTarget, intersect);
intersect = searchLevel(graph, qTarget, parentsTarget, parentsSource);
if (intersect != null) return mergePaths(parentsSource, parentsTarget, intersect);
}
return Collections.emptyList();
}
}
४. समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी)
| मीट्रिक | जटिलता | विवरण |
|---|---|---|
| समय जटिलता | ओ(एन) / ओ(लॉग एन) | डेटा के माध्यम से इष्टतम पास |
| स्थान जटिलता | ओ(१) / ओ(एन) | मेमोरी सीमाएं बनी रहीं |
५. सीमांत मामले (एज केसेस) और सारांश
कोडिंग इंटरव्यू में हमेशा सीमांत स्थितियों, शून्य (null) इनपुट और एरे आकार की सीमाओं की जांच करें।