परिचय
आपको कुलीनों के लिए बने सबसे चर्चित नए डेटिंग ऐप Noble Knots को बनाने का काम मिला है!
शाही परिवारों में सदियों से होते आए आपसी विवाहों की वजह से मामला उलझ गया है।
अरे, हम तो जुड़वाँ निकले जैसी किसी भी स्थिति से बचने के लिए आपको एक ऐसा सिस्टम बनाना है जो जाँचता है कि दो लोग कितने करीबी रिश्तेदार हैं।
Noble Knots आइसलैंड के "Islendinga-App" से प्रेरित है, जिसके पीछे एक डेटाबेस है जो आइसलैंड में बसावट के समय से आइसलैंडवासियों के बीच के सभी ज्ञात पारिवारिक संबंधों का पता लगाता है।
आपका एल्गोरिदम शाही वंशावली में दो व्यक्तियों के बीच रिश्तेदारी की दूरी तय करेगा।
तो क्या आपका ऐप एक बेहतरीन जोड़ी चुन पाएगा?
निर्देश
आपको एक वंश वृक्ष में दो व्यक्तियों के बीच अलगाव की डिग्री पता लगानी है।
यह उस पॉप कल्चर विचार के समान है कि हर हॉलीवुड अभिनेता Kevin Bacon की छह डिग्री के भीतर होता है।
- आपको एक इनपुट दिया जाएगा, जिसमें सभी माता-पिता के नाम और उनके बच्चे होंगे।
- प्रत्येक नाम अद्वितीय है, एक बच्चे के एक या दो माता-पिता हो सकते हैं।
- अलगाव की डिग्री को एक व्यक्ति से दूसरे व्यक्ति तक के कनेक्शनों की सबसे छोटी संख्या के रूप में परिभाषित किया गया है।
- यदि दो व्यक्ति जुड़े हुए नहीं हैं, तो एक ऐसी वैल्यू लौटाइए जो "कोई ज्ञात संबंध नहीं" को दर्शाती हो।
कृपया वास्तविक इम्प्लीमेंटेशन के लिए टेस्ट केस देखिए।
उदाहरण
निम्नलिखित वंश वृक्ष दिया गया है:
┌──────────┐ ┌──────────┐ ┌───────────┐
│ Helena │ │ Erdős ├─────┤ Shusaku │
└───┬───┬──┘ └─────┬────┘ └────┬──────┘
┌───┘ └───────┐ └───────┬───────┘
┌─────┴────┐ ┌────┴───┐ ┌─────┴────┐
│ Isla ├─────┤ Tariq │ │ Kevin │
└────┬─────┘ └────┬───┘ └──────────┘
│ │
┌────┴────┐ ┌────┴───┐
│ Uma │ │ Morphy │
└─────────┘ └────────┘
Tariq और Uma के बीच अलगाव की डिग्री 2 है (Tariq → Isla → Uma)।
Isla और Kevin के बीच कोई ज्ञात संबंध नहीं है, क्योंकि दिए गए डेटा में कोई कनेक्शन नहीं है।
Uma और Isla के बीच अलगाव की डिग्री 1 है।
Isla और Tariq सगे भाई-बहन हैं और उनके बीच अलगाव 1 है।
इसी तरह, यह इम्प्लीमेंटेशन आपसे आपके पिता के भाई तक अलगाव 2 रिपोर्ट करेगा।
