टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली समस्या ६.३: ८×८ बोर्ड से दो विपरीत कोने हटाए, ३१ डोमिनो। रंग-अपरिवर्तनीय साबित करता है असंभव। गिनती, बोर्ड स्केच और वैकल्पिक जावा दृश्य।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
एक ८×८ शतरंज बोर्ड पर ६४ वर्ग होते हैं। दो विपरीत कोने काट दो तो ६२ वर्ग बचते हैं। एक डोमिनो दो पड़ोसी वर्ग ढकता है। तो ३१ डोमिनो ठीक ६२ वर्ग ढक सकते अगर कोई टाइलिंग मौजूद हो। इंटरव्यू का सवाल सीधा: क्या मौजूद है?
हैरान करने वाला जवाब नहीं। इसलिए नहीं कि कोई चालाक लेआउट नहीं मिला, बल्कि इसलिए कि रंग तर्क साबित करता है हर लेआउट विफल। सारी टाइलिंग आज़माने की ज़रूरत नहीं।
यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू की क्लासिक गणित और तर्क पहेलियों जैसी समस्या, किसी किताब की नकल नहीं। सीटीसीआई जावा श्रृंखला का हिस्सा। अध्याय ६, गणित और तर्क पहेलियाँ, समस्या ६.३।
१. रोज़मर्रा की उपमा
रसोई का फर्श सोचो, काली और सफ़ेद टाइल बारी-बारी। तुम और दोस्त, हर एक के पास एक रंग का गोंद। हर डोमिनो-नुमा दरी एक काली और एक सफ़ेद टाइल पर बैठेगी, क्योंकि डोमिनो दो साथ के वर्ग हैं, और मानक रंग-योजना में साथ के वर्ग हमेशा अलग रंग के होते हैं।
अब कोई दो काली टाइलें विपरीत कोनों से उखाड़कर ३१ दरियाँ थमा देता है। सफ़ेद अब काली से ज़्यादा हैं। हर दरी एक-एक रंग हटाती है। पहले काली खत्म होंगी, दो सफ़ेद बचेंगी, और दो सफ़ेद ढकने वाली कोई वैध दरी नहीं। यही पूरी उपपत्ति है, फर्श के काम की भाषा में।
२. सादे शब्दों में समस्या
सेटअप:
- एक ८×८ शतरंज बोर्ड (६४ वर्ग)।
- दो विपरीत कोने हटाओ। मानक बोर्ड पर वे कोने एक ही रंग के होते हैं (दोनों "काले" या दोनों "सफ़ेद", जिस कोने को काला कहो)।
- पास हैं ३१ डोमिनो। हर डोमिनो ठीक दो पड़ोसी वर्ग ढकता है (किनारा साझा, सिर्फ कोना नहीं)।
सवाल: क्या ३१ डोमिनो बचे हर वर्ग को बिना ओवरलैप और बिना छेद के ढक सकते हैं?
तर्क का आउटपुट (इंटरव्यूअर क्या चाहता है): साफ़ हाँ या नहीं, साथ में उपपत्ति, अधूरी खोज नहीं।
महत्वपूर्ण संख्याएँ:
| मात्रा | मान |
|---|---|
| पूरे बोर्ड के वर्ग | ६४ |
| दो हटाने के बाद वर्ग | ६२ |
| पूरी कवर के लिए डोमिनो | ३१ |
| मानक रंग-योजना में काले | ३२ |
| मानक रंग-योजना में सफ़ेद | ३२ |
| हटाए विपरीत कोने | एक ही रंग के २ |
| बची रंग-गिनती | एक रंग के ३०, दूसरे के ३२ |
"हल" से पहले पूछो:
- पड़ोसी का मतलब किनारा साझा? (हाँ।)
- डोमिनो घुमा सकते हो? (क्षैतिज या ऊर्ध्व, दोनों ठीक।)
- सिर्फ विपरीत कोने, या कोई भी दो? (क्लासिक कथन: विपरीत। आसन्न कोने अलग रंग; वह अलग सवाल।)
- क्या बोर्ड हमेशा चेकर्ड रंग में होता है? (तुम वह रंग चुन सकते हो। यह उपपत्ति का औज़ार है, भौतिक बोर्ड पर पेंट की मजबूरी नहीं।)
३. पहले सोचो
भोली इच्छा: टाइलिंग खोजो
बैकट्रैक कर सकते हो: डोमिनो रखो, रिकर्स करो, वापस लो। ६२ सेल पर बिना सममिति सँभाले खोज बड़ी हो जाती है। यहाँ सामान्य एग्ज़ैक्ट कवर सॉल्वर नहीं चाहिए। चाहिए अपरिवर्तनीय।
बेहतर: समता / रंग-अपरिवर्तनीय
बोर्ड को शतरंज जैसा रंगो:
(r + c) even -> black (or white; pick one convention and stick to it)
(r + c) odd -> white
किनारा साझा करने वाले दो वर्ग एक निर्देशांक में ठीक १ से भिन्न होते हैं। तो एक का r+c सम, दूसरे का विषम। हर डोमिनो एक काला और एक सफ़ेद ढकता है।
३१ डोमिनो की पूर्ण टाइलिंग ३१ काले और ३१ सफ़ेद ढकेगी।
विपरीत कोनों का रंग?
८×८ बोर्ड के कोने (०-इंडेक्स पंक्ति और स्तंभ 0..7):
(0,0) r+c = 0 even
(0,7) r+c = 7 odd
(7,0) r+c = 7 odd
(7,7) r+c = 14 even
विपरीत जोड़े:
(0,0)और(7,7): दोनों सम (एक रंग)।(0,7)और(7,0): दोनों विषम (एक रंग)।
दो विपरीत कोने हटाओ तो एक रंग के दो वर्ग हटते हैं। बचते हैं उस रंग के ३० और दूसरे के ३२।
३१ डोमिनो को ३१+३१ चाहिए। पास ३०+३२। असंभव।
उपपत्ति क्या है और क्या नहीं
- यह आवश्यक शर्त का तर्क है: अगर टाइलिंग होती तो काली गिनती सफ़ेद के बराबर होती। बराबर नहीं। तो टाइलिंग नहीं।
- यह नहीं कहता "जितने काले उतने सफ़ेद वाला हर बोर्ड टाइल हो जाता है।" समानता आवश्यक है, हमेशा पर्याप्त नहीं। यहाँ असमानता समस्या खत्म करने के लिए काफ़ी है।
विरोधाभास: अलग रंग के दो वर्ग हटाओ
अगर एक काला और एक सफ़ेद हटाओ (जैसे दो आसन्न कोने), गिनती ३१ और ३१ रहती है। रंग तर्क अब टाइलिंग मना नहीं करता। कई ऐसे बोर्ड टाइल हो भी जाते हैं। इसलिए "विपरीत" शब्द भार रखता है।
४. जावा समाधान (तर्क हेल्पर + वैकल्पिक बोर्ड स्केच)
उपपत्ति के लिए प्रोडक्शन कोड ज़रूरी नहीं। फिर भी छोटा जावा हेल्पर जो बोर्ड रंगे, विपरीत कोने हटाए, गिनती छापे, इंटरव्यू आईडीई में अपरिवर्तनीय को ठोस बनाता है।
public final class DominosBoard {
private static final int N = 8;
/** Color: 0 = black (even r+c), 1 = white (odd r+c). */
public static int color(int r, int c) {
return (r + c) & 1;
}
/**
* Count remaining black (0) and white (1) after removing two opposite corners.
* pair 0: (0,0) and (N-1,N-1); pair 1: (0,N-1) and (N-1,0).
*/
public static int[] remainingColorCounts(int oppositePair) {
boolean[][] removed = new boolean[N][N];
if (oppositePair == 0) {
removed[0][0] = true;
removed[N - 1][N - 1] = true;
} else {
removed[0][N - 1] = true;
removed[N - 1][0] = true;
}
int black = 0;
int white = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (removed[r][c]) {
continue;
}
if (color(r, c) == 0) {
black++;
} else {
white++;
}
}
}
return new int[] {black, white};
}
/** True only if remaining black == remaining white (necessary for any domino tiling). */
public static boolean colorCountsAllowTiling(int oppositePair) {
int[] counts = remainingColorCounts(oppositePair);
return counts[0] == counts[1];
}
/** ASCII board: B/W for colors, . for removed. */
public static String sketch(int oppositePair) {
boolean[][] removed = new boolean[N][N];
if (oppositePair == 0) {
removed[0][0] = true;
removed[N - 1][N - 1] = true;
} else {
removed[0][N - 1] = true;
removed[N - 1][0] = true;
}
StringBuilder sb = new StringBuilder();
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (removed[r][c]) {
sb.append('.');
} else {
sb.append(color(r, c) == 0 ? 'B' : 'W');
}
if (c + 1 < N) {
sb.append(' ');
}
}
if (r + 1 < N) {
sb.append('\n');
}
}
return sb.toString();
}
public static void main(String[] args) {
for (int pair = 0; pair <= 1; pair++) {
int[] counts = remainingColorCounts(pair);
System.out.println("pair=" + pair
+ " black=" + counts[0]
+ " white=" + counts[1]
+ " allowTiling=" + colorCountsAllowTiling(pair));
System.out.println(sketch(pair));
System.out.println();
}
// pair=0 black=30 white=32 allowTiling=false
// pair=1 black=32 white=30 allowTiling=false
}
}
वैकल्पिक: भोला बैकट्रैकिंग (खोज विफल दिखाता है; ज़रूरी नहीं)
अगर "खोज" बनाम "उपपत्ति" दिखाना हो, छोटे बोर्ड पर छोटा सॉल्वर डेमो के लिए काफ़ी। कटे ८×८ पर बिना कड़ी छँटाई खोज थक जाती है। इंटरव्यू का मतलब: वह खोज ज़रूरी नहीं होनी चाहिए।
// Illustration only: try to tile a board represented as free cells.
// Returns true if some complete domino cover exists.
static boolean canTile(boolean[][] free) {
int r = -1, c = -1;
outer:
for (int i = 0; i < free.length; i++) {
for (int j = 0; j < free[i].length; j++) {
if (free[i][j]) {
r = i;
c = j;
break outer;
}
}
}
if (r < 0) {
return true; // no free cells left: success
}
// place horizontal
if (c + 1 < free[r].length && free[r][c + 1]) {
free[r][c] = false;
free[r][c + 1] = false;
if (canTile(free)) {
return true;
}
free[r][c] = true;
free[r][c + 1] = true;
}
// place vertical
if (r + 1 < free.length && free[r + 1][c]) {
free[r][c] = false;
free[r + 1][c] = false;
if (canTile(free)) {
return true;
}
free[r][c] = true;
free[r + 1][c] = true;
}
return false;
}
कटे ८×८ पर colorCountsAllowTiling पहले ही असत्य देता है, इसलिए canTile बुला सकते हो छोड़ो।
५. क्लासिक मामलों की चाल
मामला क: विपरीत कोने (0,0) और (7,7)
दोनों का r+c सम (हमारी परंपरा में काला)।
Full board: 32 B, 32 W
Remove 2 B: 30 B, 32 W
Dominos need equal counts per color → impossible
मामला ख: विपरीत कोने (0,7) और (7,0)
दोनों विषम (सफ़ेद)।
Remove 2 W: 32 B, 30 W
Still unequal → impossible
मामला ग: मानसिक मिनी-बोर्ड २×२, विपरीत कोने हटाओ
B W
W B
दोनों बी हटाओ: विकर्ण पर दो डब्ल्यू। कोई किनारा-साझा जोड़ा नहीं बचा। एक रंग के दो वर्ग जो सिर्फ कोने से छूते हों, डोमिनो नहीं ले सकते। वही अपरिवर्तनीय, छोटा चित्र।
मामला घ: एक काला और एक सफ़ेद हटाओ
गिनती: ३१ बी, ३१ डब्ल्यू। रंग तर्क अब टाइलिंग नहीं रोकता। कई बनावटें काम करती हैं। ज़ोर से कहो ताकि इंटरव्यूअर देखे कि तर्क की सीमा समझते हो।
धुआँ परीक्षा
public static void main(String[] args) {
int[] a = DominosBoard.remainingColorCounts(0);
int[] b = DominosBoard.remainingColorCounts(1);
assert a[0] + a[1] == 62;
assert b[0] + b[1] == 62;
assert a[0] != a[1];
assert b[0] != b[1];
assert !DominosBoard.colorCountsAllowTiling(0);
assert !DominosBoard.colorCountsAllowTiling(1);
System.out.println("counts invariant ok");
}
६. जटिलता, किनारे, इंटरव्यू सुझाव
| विषय | जवाब |
|---|---|
| इस उदाहरण का निर्णय | असंभव (कोई टाइलिंग नहीं) |
| उपपत्ति का औज़ार | शतरंज रंग; हर डोमिनो एक काला + एक सफ़ेद |
| विपरीत कोने हटाने के बाद | एक रंग के ३०, दूसरे के ३२ |
| उपपत्ति से "हल" समय | तर्क ओ(१); गिनने के लिए n×n स्कैन तो ओ(n²) |
| स्केच के लिए अतिरिक्त जगह | स्पष्ट बोर्ड पर ओ(n²), सिर्फ तर्क पर ओ(१) |
| खोज विकल्प | घातीय बैकट्रैक; अपरिवर्तनीय टूटे तो अनावश्यक |
आम गलतियाँ:
१. अपरिवर्तनीय खोजने के बजाय कोई खास लेआउट गढ़ना। २. भूलना कि विपरीत कोने एक रंग के हैं। पहले चार कोने बनाओ, रंग लगाओ। ३. कहना "६२ सम है तो काम करेगा।" सम कुल आकार डोमिनो के लिए आवश्यक है, पर्याप्त नहीं। ४. दावा कि बराबर काला/सफ़ेद हमेशा टाइल होता है। आवश्यक, पर्याप्त नहीं। यहाँ सिर्फ आवश्यकता काफ़ी। ५. विपरीत और आसन्न कोने मिलाना। आसन्न अलग रंग; क्लासिक जाल विपरीत इस्तेमाल करता है। ६. ज़्यादा कोड। दो मिनट की सही उपपत्ति आधे घंटे के टूटे सॉल्वर से बेहतर।
कैसे बोलो (३० सेकंड संस्करण):
१. बोर्ड काला/सफ़ेद रंगो। २. हर डोमिनो एक-एक ढकता है। ३. विपरीत कोने एक रंग के, हटाने पर ३० और ३२। ४. इसलिए ३१ डोमिनो बोर्ड नहीं ढक सकते।
आगे कहाँ दिखता है:
- पहेलियों में अपरिवर्तनीय तर्क (संतुलन, समता, मॉड्यूलर अंकगणित)।
- मैचिंग अंतर्ज्ञान: डोमिनो काले बनाम सफ़ेद द्विभाजित ग्राफ़ की भुजाएँ; असमान भागों पर पूर्ण मैचिंग नहीं।
- इंटरव्यू में और "कटे" बोर्ड और ग्रिड-टाइलिंग सवाल।
७. दोस्त को समझाने वाला सार
डोमिनो (समस्या ६.३) तर्क की समस्या है, कोड की चक्की नहीं।
१. ८×८ बोर्ड, दो विपरीत कोने गए: ६२ वर्ग, तो गिनती से ३१ डोमिनो फिट बैठेंगे। २. बोर्ड रंगो। पड़ोसी वर्ग हमेशा अलग रंग। ३. हर डोमिनो एक काला और एक सफ़ेद। ४. विपरीत कोने एक ही रंग, तो एक रंग के दो हटे। ५. बचे ३० और ३२। पूर्ण टाइलिंग को ३१ और ३१ चाहिए। असंभव।
अगर चार कोने चिह्नित कर सको, एक-रंग वाला तथ्य कह सको, और ३०/३२ गिनती से खत्म कर सको, तो समस्या ६.३ तुम्हारी है। पन्ने पर एक डोमिनो रखने की ज़रूरत नहीं।
सीरीज़
- गाइड: सीटीसीआई सीरीज़ गाइड
- पिछला: बास्केटबॉल
- अगला: त्रिभुज पर चींटियाँ