समस्या और यह कब लागू होती है
प्रोग्रामरों को समस्याएं सौंपना एक उपयोगी मॉडल है: समस्याएं बाईं ओर हैं, प्रोग्रामर दाईं ओर हैं, और एक किनारा (edge) दर्शाता है कि वे एक आवश्यक टैग साझा करते हैं। प्रत्येक किनारे को अधिकतम एक बार चुना जा सकता है, और उद्देश्य असाइनमेंट को अधिकतम करना है। PracHub का एक सार्वजनिक साक्षात्कार प्रॉम्प्ट इस पात्रता आवंटन को द्विपक्षीय मिलान (bipartite matching) के रूप में मॉडल करता है और इसे एज जेनरेशन, वितरित समन्वय और स्ट्रीमिंग परिवर्तनों तक विस्तारित करता है; यह लेख सिंगल-मशीन कोडिंग कोर पर केंद्रित है।
साक्षात्कारकर्ता क्या जांच रहा है
- किसी भी व्यवहार्य (feasible), अधिकतम संभव (maximal), और अधिकतम-कार्डिनैलिटी (maximum-cardinality) मिलानों में अंतर करना।
- इनवेरिएंट्स को बनाए रखते हुए मिलान कैसे बढ़ सकता है, यह समझाने के लिए संवर्धित पथों (augmenting paths) का उपयोग करना।
- शीर्ष-असंयुक्त (vertex-disjoint) सबसे छोटे संवर्धित पथों के सेट के लिए BFS लेयरिंग और DFS की व्याख्या करना।
- वर्स्ट-केस O((V+E)√V) समय, O(V+E) स्टोरेज और एल्गोरिदम की सीमाओं को स्पष्ट करना।
पहले पूछे जाने वाले स्पष्टीकरण प्रश्न
- क्या उद्देश्य अधिकतम कार्डिनैलिटी है, या इसमें वज़न (weights), प्राथमिकताएं या निष्पक्षता (fairness) की बाधाएं हैं?
- n, m और E की सीमाएं क्या हैं, और क्या इनपुट पहले से ही द्विपक्षीय (bipartite) और डुप्लिकेट-मुक्त है?
- क्या उत्तर में केवल आकार लौटाना चाहिए, या प्रत्येक जोड़ी और प्रत्येक गैर-मिलान शीर्ष भी?
- क्या ग्राफ़ एक स्थिर बैच है, या एक ऑनलाइन लेटेंसी लक्ष्य के तहत किनारों को डाला और हटाया जाएगा?
30-सेकंड का उत्तर
“मैं दो ऑब्जेक्ट श्रेणियों को एक द्विपक्षीय ग्राफ़ के दो पक्षों के रूप में और पात्रता को किनारों के रूप में मॉडल करता हूँ। मैं pair_left और pair_right बनाए रखता हूँ। प्रत्येक BFS प्रत्येक गैर-मिलान वाले बाएं शीर्ष से शुरू होता है और वैकल्पिक गैर-मिलान और मिलान किए गए किनारों के माध्यम से परतें बनाता है। इसके बाद DFS उस स्तरित ग्राफ़ में सबसे छोटे संवर्धित पथों का एक शीर्ष-असंयुक्त सेट ढूंढता है; प्रत्येक पथ को पलटने (flipping) से मिलान बढ़ जाता है। जब कोई संवर्धित पथ नहीं बचता है, तो संवर्धित-पथ प्रमेय (augmenting-path theorem) अधिकतम मिलान प्रदान करता है। वर्स्ट-केस जटिलता O((V+E)√V) है; एक छोटे ग्राफ़ के लिए, एक सरल DFS संवर्धित कार्यान्वयन पर्याप्त हो सकता है।”
चरण-दर-चरण समाधान
चरण 1: ग्राफ़ और इनवेरिएंट्स बनाएं
निकटता सूचियों (adjacency lists) में केवल वास्तविक व्यवहार्य किनारों को संग्रहीत करें। pair_left[u] और pair_right[v] को एक-दूसरे की ओर इंगित करना चाहिए, या दोनों को -1 होना चाहिए। एक संवर्धित पथ को पलटने से केवल उसके किनारों में बदलाव होता है, इसलिए किसी भी शीर्ष को दो मिलान वाले किनारे नहीं मिलते हैं।
चरण 2: BFS के साथ परतें (layers) बनाएं
सभी गैर-मिलान वाले बाएं शीर्षों से एक साथ शुरुआत करें। दाईं ओर एक गैर-मिलान वाले किनारे से होकर गुजरें और फिर वापस बाएं शीर्ष पर मिलान किए गए किनारे से गुजरें, और सबसे छोटी परत रिकॉर्ड करें। उन सबसे छोटी परतों को रखें जो एक गैर-मिलान वाले दाएं शीर्ष तक पहुंच सकती हैं ताकि DFS उसी चरण में लंबे पथों का पता न लगाए।
चरण 3: DFS के साथ बैचों में संवर्धन करें
प्रत्येक गैर-मिलान वाले बाएं शीर्ष से DFS चलाएं। एक गैर-मिलान वाले दाएं शीर्ष तक पहुंचना सफल होता है। एक मिलान किए गए दाएं शीर्ष तक पहुंचना केवल तभी इसके मिलान किए गए बाएं शीर्ष के माध्यम से पुनरावृत्ति (recurse) करता है जब परत एक से बढ़ जाती है। प्रत्येक बाएं शीर्ष के लिए एक एडजसेंसी कर्सर उसी चरण में विफल किनारों को फिर से स्कैन करने से रोकता है।
चरण 4: शुद्धता और समाप्ति
एक संवर्धित पथ में मिलान किए गए किनारे की तुलना में एक गैर-मिलान वाला किनारा अधिक होता है, इसलिए इसके साथ सममित अंतर (symmetric difference) कार्डिनैलिटी को एक से बढ़ाता है। संवर्धित-पथ प्रमेय कहता है कि मिलान अधिकतम तभी होता है जब कोई संवर्धित पथ मौजूद न हो। प्रत्येक चरण मिलान को बढ़ाता है, इसलिए लूप समाप्त हो जाता है।
चरण 5: जटिलता और ट्रेड-ऑफ़
Hopcroft–Karp में वर्स्ट-केस समय O((V+E)√V), O(V) सहायक स्पेस और O(V+E) ग्राफ़ स्टोरेज होता है। Princeton का संदर्भ कार्यान्वयन न्यूनतम शीर्ष आवरण (minimum vertex cover) भी प्राप्त करता है; इस प्रॉम्प्ट को केवल एक मिलान की आवश्यकता है। एक छोटे ग्राफ़ के लिए, प्रति-बाएं DFS छोटा होता है लेकिन सबसे खराब स्थिति में O(VE) ले सकता है। भारित (weighted) उद्देश्यों के लिए इसके बजाय हंगेरियन (Hungarian) या न्यूनतम-लागत प्रवाह (min-cost flow) की आवश्यकता होती है।
निष्पादन योग्य Python कार्यान्वयन
from collections import deque
def hopcroft_karp(left_size, right_size, edges):
adj = [[] for _ in range(left_size)]
for left, right in edges:
adj[left].append(right)
pair_left = [-1] * left_size
pair_right = [-1] * right_size
distance = [-1] * left_size
def bfs():
queue = deque()
for left in range(left_size):
if pair_left[left] == -1:
distance[left] = 0
queue.append(left)
else:
distance[left] = -1
found = False
while queue:
left = queue.popleft()
for right in adj[left]:
mate = pair_right[right]
if mate == -1:
found = True
elif distance[mate] == -1:
distance[mate] = distance[left] + 1
queue.append(mate)
return found
def dfs(left, next_edge):
while next_edge[left] < len(adj[left]):
right = adj[left][next_edge[left]]
next_edge[left] += 1
mate = pair_right[right]
if mate == -1 or (
distance[mate] == distance[left] + 1
and dfs(mate, next_edge)
):
pair_left[left] = right
pair_right[right] = left
return True
distance[left] = -1
return False
matching = 0
while bfs():
next_edge = [0] * left_size
for left in range(left_size):
if pair_left[left] == -1 and dfs(left, next_edge):
matching += 1
return matching, pair_leftएक उच्च-गुणवत्ता वाला नमूना उत्तर
“मैं पहले पुष्टि करता हूँ कि उद्देश्य अधिकतम कार्डिनैलिटी है, भारित मिलान नहीं, और पात्रता को द्विपक्षीय किनारों के रूप में मॉडल करता हूँ। दो युग्म सरणियाँ (pair arrays) एक द्विदिशीय इनवेरिएंट बनाए रखती हैं। BFS सभी गैर-मिलान वाले बाएं शीर्षों से सबसे छोटे संवर्धित पथों को स्तरित करता है; DFS उस लेयर ग्राफ़ में अधिक से अधिक शीर्ष-असंयुक्त पथ खोजने के लिए वर्तमान-किनारे कर्सर का उपयोग करता है, फिर उनके किनारों को पलट देता है। जब कोई पथ नहीं बचता है, तो संवर्धित-पथ प्रमेय इष्टतमता सिद्ध करता है। कार्यान्वयन O((V+E)√V) समय और O(V+E) स्टोरेज का उपयोग करता है; छोटे ग्राफ़ सरल DFS का उपयोग कर सकते हैं, जबकि भारित उद्देश्यों के लिए हंगेरियन या न्यूनतम-लागत प्रवाह की आवश्यकता होती है।”
सामान्य गलतियाँ
- लालची परिणाम को अधिकतम कहना; एक मैक्सिमल (maximal) मिलान अधिकतम (maximum) मिलान से बहुत छोटा हो सकता है।
- प्रत्येक जोड़ी का केवल एक पक्ष संग्रहीत करना और फ़्लिप के बाद डुप्लिकेट ऑक्यूपेंसी बनाना।
- BFS को किसी भी पहुंच योग्य पथ पर रोकना, जो सबसे छोटी-परत की बैचिंग को बाधित करता है।
- वर्तमान-किनारे कर्सर को छोड़ देना और एक ही चरण में विफल किनारों को फिर से स्कैन करना।
- सामान्य, भारित या गतिशील रूप से अद्यतन मिलान के लिए O((V+E)√V) का दावा करना।
फॉलो-अप और मजबूत प्रतिक्रियाएं
आप सभी n×m जोड़ों की तुलना किए बिना पात्रता किनारे कैसे उत्पन्न करते हैं?
टैग द्वारा एक इनवर्टेड इंडेक्स बनाएं। दाईं ओर की वस्तुओं को बकेट करें, फिर प्रत्येक बाईं वस्तु के लिए बकेट का संघ (union) और डिडुप्लीकेशन करें। E अभी भी बड़ा हो सकता है, इसलिए E, हॉट-टैग स्क्यू (hot-tag skew) और मेमोरी सीमाओं की रिपोर्ट करें।
कोई संवर्धित पथ न होने पर एल्गोरिदम क्यों रुक सकता है?
प्रत्येक संवर्धित पथ मिलान आकार को एक से बढ़ाता है। संवर्धित-पथ प्रमेय बताता है कि एक बड़ा मिलान केवल तभी मौजूद होता है जब एक संवर्धित पथ मौजूद हो, इसलिए कोई पथ न मिलना अधिकतम कार्डिनैलिटी को सिद्ध करता है।
भारित प्राथमिकताओं के लिए क्या परिवर्तन होता है?
Hopcroft–Karp केवल किनारों की संख्या को अनुकूलित करता है। हंगेरियन या न्यूनतम-लागत अधिकतम-प्रवाह का उपयोग करें, और जटिलता, पूर्णांक-भार सीमाओं और कोई व्यवहार्य असाइनमेंट मौजूद न होने पर फ़ॉलबैक को फिर से बताएं।
आप लगातार किनारे के बदलाव (edge churn) को कैसे संभालेंगे?
बैच एल्गोरिदम पुनर्गणना के लिए उपयुक्त है। एक ऑनलाइन सेवा प्रभावित शीर्षों के आसपास संवर्धित पथों की स्थानीय रूप से खोज कर सकती है, लेकिन उसे लेटेंसी, पुनर्गठन सीमाओं और अस्थायी गैर-इष्टतमता अनुबंध को स्पष्ट करना होगा।