टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ६.९: १०० बंद लॉकर, १०० लोग हर i-वें दरवाज़े को पलटते हैं। खुले लॉकर पूर्ण वर्ग हैं (१, ४, ९, ..., १००) क्योंकि सिर्फ वर्गों के गुणनखंड विषम संख्या में होते हैं। वैकल्पिक जावा सिमुलेशन।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
गलियारे में १०० लॉकर हैं, सब बंद। १०० लोग गुजरते हैं। व्यक्ति i हर i-वें लॉकर को पलटता है: व्यक्ति १ सबको छूता है, व्यक्ति २ छूता है २, ४, ६, ..., व्यक्ति १०० सिर्फ लॉकर १००। जब सब खत्म हो जाएँ, कौन से लॉकर खुले हैं?
पूरे गलियारे को लूप से सिमुलेट कर सकते हो। काम करता है, और इंटरव्यू में कोड माँग सकते हैं। असली जवाब साफ है: सिर्फ पूर्ण-वर्ग लॉकर खुले रहते हैं (1, 4, 9, 16, 25, 36, 49, 64, 81, 100)। हर लॉकर बंद शुरू होता है और हर भाजक पर एक बार पलटता है। सिर्फ वर्गों के भाजक विषम संख्या में होते हैं, इसलिए सिर्फ वे खुले खत्म होते हैं।
यह पोस्ट शुरुआती लोगों के लिए मूल शिक्षण है, पलटने का वैकल्पिक जावा सिमुलेशन साथ। क्लासिक इंटरव्यू गणित पहेलियों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ६, गणित और तर्क, समस्या ६.९।
१. रोज़मर्रा की उपमा
स्कूल के गलियारे में १०० धातु के लॉकर सोचो। हर दरवाज़ा शुरू में बंद।
छात्रों की कतार गुजरती है। छात्र १ हर दरवाज़ा खोलता या बंद करता है (सब खुल जाते)। छात्र २ हर दूसरा दरवाज़ा छूता है (आधे बंद हो जाते)। छात्र ३ हर तीसरा, और आखिर छात्र १०० सिर्फ लॉकर १०० छूता है।
हर छात्र को देखने की ज़रूरत नहीं। सवाल बदलो: लॉकर k कितनी बार छुआ जाता है? हर उस संख्या के लिए एक बार जो k को विभाजित करे। लॉकर १२ को १, २, ३, ४, ६ और १२ छूते हैं: छह बार। छह सम है, बंद खत्म (बंद शुरू, सम पलट बंद छोड़ते हैं)। लॉकर १६ को १, २, ४, ८ और १६: पाँच बार। विषम, खुला खत्म।
विषम गिनती तभी आती है जब कोई गुणनखंड "खुद से जोड़ी" बनाता है: पूर्ण वर्ग।
२. समस्या सादे शब्दों में
सेटअप:
- १०० लॉकर, १ से १०० तक।
- सब बंद शुरू।
- १०० लोग, १ से १०० तक।
- व्यक्ति
iलॉकरi, 2i, 3i, ...पलटता है (iके हर गुणज जो १०० से बड़े न हों)। - पलटना: बंद खुला हो, खुला बंद हो।
लक्ष्य: व्यक्ति १०० के बाद खुले लॉकर सूचीबद्ध करो (या गिनो)।
इंटरव्यू में साफ कहो:
- लॉकर और लोग दोनों १-आधारित, १..१००।
- हर व्यक्ति एक पास, क्रम में (क्रम अंतिम स्थिति नहीं बदलता; हर लॉकर हर भाजक पर एक बार पलटता है)।
- पासों के बीच और कोई क्रिया नहीं।
अगर सिमुलेटर लिखो तो सिग्नेचर का आकार:
// returns true if locker is open after the full process (1-based indices in comments)
boolean[] openLockers(int n);
या सिर्फ खुले सूचकांक:
// simulate n lockers / n people; return list of open locker numbers (1-based)
List<Integer> openAfterProcess(int n);
छोटी संख्या पूर्वावलोकन (n = १०):
| लॉकर | भाजक (कौन पलटता) | गिनती | अंतिम (बंद शुरू) |
|---|---|---|---|
| १ | १ | १ विषम | खुला |
| २ | १, २ | २ सम | बंद |
| ३ | १, ३ | २ सम | बंद |
| ४ | १, २, ४ | ३ विषम | खुला |
| ५ | १, ५ | २ सम | बंद |
| ६ | १, २, ३, ६ | ४ सम | बंद |
| ७ | १, ७ | २ सम | बंद |
| ८ | १, २, ४, ८ | ४ सम | बंद |
| ९ | १, ३, ९ | ३ विषम | खुला |
| १० | १, २, ५, १० | ४ सम | बंद |
n = १० पर खुले: १, ४, ९। n = १०० पर: १, ४, ९, ..., १०० (दस दरवाज़े)।
३. पहले सोचो
पहले सीधा बल-प्रयोग
दो नेस्टेड लूप:
lockers[1..n] = closed
for person p = 1..n:
for locker k = p, 2p, 3p, ... <= n:
toggle lockers[k]
नाइव रूप में O(n²); असल में कुल लगभग O(n log n) पलट, क्योंकि व्यक्ति p n/p दरवाज़े छूता है। n = १०० के लिए ठीक। फिर भी क्यों चाहिए।
लॉकर k को कौन पलटता है?
व्यक्ति p लॉकर k तभी छूता है जब p k को विभाजित करे। तो लॉकर k k के हर धनात्मक भाजक पर एक बार पलटता है।
बंद शुरू:
- सम संख्या पलट → बंद
- विषम संख्या पलट → खुला
खुले लॉकर वही हैं जिनकी भाजक गिनती विषम है।
भाजकों की संख्या कब विषम होती है?
भाजक आमतौर पर जोड़ी बनाते हैं: अगर d k को विभाजित करे तो k/d भी, और d ≠ k/d जब तक d² = k न हो।
१२ का उदाहरण:
1 × 12
2 × 6
3 × 4
छह अलग भाजक, तीन जोड़ियाँ।
१६ का उदाहरण:
1 × 16
2 × 8
4 × 4 // sqrt pairs with itself
भाजक: १, २, ४, ८, १६। पाँच मान। बीच वाला गुणनखंड एक बार गिना जाता है।
सिर्फ पूर्ण वर्ग में वर्गमूल वाला भाजक "खुद से जोड़ी" बनाता है, इसलिए सिर्फ उनकी गिनती विषम।
इसलिए खुले लॉकर:
1², 2², 3², ..., floor(sqrt(n))²
n = १०० पर: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100। गिनती: १०।
गिनती का बंद रूप
सामान्य n पर खुले लॉकरों की संख्या floor(sqrt(n)) है। प्रमेय मिल जाए तो सिमुलेशन ज़रूरी नहीं।
यह "गणित और तर्क" क्यों है, कोड ट्रिविया नहीं
कोई भी दोहरा लूप लिख लेता है। इंटरव्यू की जीत है पलट की सम-विषमता को भाजक की सम-विषमता से पूर्ण वर्ग तक जोड़ना। कीबोर्ड छूने से पहले यह श्रृंखला बोलो।
जो वेरिएंट लोग लाते हैं
- बंद की जगह खुले शुरू: अंतिम स्थिति पलट जाती है (या "खुला" फिर परिभाषित करो)। शुरुआती अवस्था हमेशा बताओ।
- n १०० नहीं: वही नियम; खुले = n तक के वर्ग।
- सूची नहीं, सिर्फ गिनती: जवाब
floor(sqrt(n))। - "कौन से लोग लॉकर खुला छोड़ते हैं?" फिर भी वर्ग सूचकांक; अंतिम स्थिति लोगों की नहीं, पलट की है।
४. जावा समाधान (सिमुलेशन)
तर्क काफी है। कोड n = १०० और सामान्य n पर दावा साबित करता है।
पूरा सिमुलेशन
import java.util.ArrayList;
import java.util.List;
/** Simulate n lockers / n people. Returns 1-based open locker numbers. */
static List<Integer> openAfterProcess(int n) {
boolean[] open = new boolean[n + 1]; // index 0 unused; false = closed
for (int person = 1; person <= n; person++) {
for (int locker = person; locker <= n; locker += person) {
open[locker] = !open[locker];
}
}
List<Integer> result = new ArrayList<>();
for (int k = 1; k <= n; k++) {
if (open[k]) {
result.add(k);
}
}
return result;
}
सिर्फ गणित वाला जवाब (पहले यही कहो)
/** Open lockers are perfect squares: 1, 4, 9, ..., floor(sqrt(n))^2. */
static List<Integer> openBySquares(int n) {
List<Integer> result = new ArrayList<>();
for (int i = 1; i * i <= n; i++) {
result.add(i * i);
}
return result;
}
सिमुलेशन से सेल्फ-चेक
static void verify(int n) {
List<Integer> sim = openAfterProcess(n);
List<Integer> math = openBySquares(n);
if (!sim.equals(math)) {
throw new AssertionError("mismatch for n=" + n + " sim=" + sim + " math=" + math);
}
System.out.println("ok n=" + n + " open=" + math + " count=" + math.size());
}
// verify(10); // [1, 4, 9]
// verify(100); // [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
सूची के बिना गिनती
static int countOpen(int n) {
return (int) Math.floor(Math.sqrt(n));
// or integer loop: int c = 0; for (int i = 1; i * i <= n; i++) c++; return c;
}
n = १०० पर, floor(sqrt(100)) = 10।
लॉकर ३६ के काम किए आंकड़े
३६ के भाजक: १, २, ३, ४, ६, ९, १२, १८, ३६। यानी ९ (विषम)।
start closed
after 1: open
after 2: closed
after 3: open
after 4: closed
after 6: open
after 9: closed
after 12: open
after 18: closed
after 36: open
खुला खत्म। ३६ = ६²।
लॉकर ५०: भाजक १, २, ५, १०, २५, ५०। छह बार, सम, बंद खत्म।
५. जटिलता तालिका
| तरीका | समय | अतिरिक्त जगह | नोट |
|---|---|---|---|
| दोहरा लूप सिमुलेशन | O(n log n) पलट | बूलियन सरणी के लिए O(n) | साफ, कोड राउंड के लिए अच्छा |
पूर्ण वर्ग सूची i*i <= n |
O(sqrt(n)) | जवाब सूची O(sqrt(n)) | अंतर्दृष्टि मिलने पर सबसे अच्छा |
सिर्फ गिनती floor(sqrt(n)) |
Math.sqrt से O(१), या पूर्णांक लूप O(sqrt(n)) |
O(१) | अगर सिर्फ "कितने" पूछें |
| हर k के भाजक गिनना | नाइव O(n sqrt(n)) | आउटपुट के अलावा O(१) | सही पर धीमा; भाजक नज़रिया सिखाता है |
n = १०० पर सब तुरंत। बहुत बड़े n पर वर्ग सूची या फ्लोर-वर्गमूल गिनती चुनो।
६. किनारे के मामले और आम गलतियाँ
इंटरव्यूअर ये छेड़ते हैं:
- n = १: सिर्फ लॉकर १, व्यक्ति १ खोलता है। खुले:
[1]। - n = ० या ऋणात्मक: खाली मानो; कोड में अस्वीकार।
- ऑफ-बाय-वन सरणियाँ: जावा ०-आधारित; सूचकांक ० खाली छोड़ो या मैप संभालो।
- खुले शुरू: जवाब पलट जाता है। पुष्टि करो कि समस्या बंद शुरू कहती है।
- क्या व्यक्ति i सिर्फ लॉकर i पलटता है? नहीं: गुणज भी। कुछ लोग भूलकर सिर्फ
iछूते हैं। - गिनती के लिए फ्लोट वर्गमूल:
Math.sqrtलगभग २^५३ तक सटीक पूर्णांक वर्गों के लिए ठीक; बहुत बड़ेlongपर फ्लोर वर्गमूल की बाइनरी खोज, या सावधानी से कास्ट। - "व्यक्ति १ ने जो छुए सब अंत में खुले" गलत; बाद वाले कई बंद करते हैं।
आम गलतियाँ:
१. सिर्फ व्यक्ति १ और १०० सिमुलेट करना और बिना भाजक पैटर्न अनुमान लगाना।
२. कहना अभाज्य खुले रहते हैं (नहीं: अभाज्य के ठीक दो भाजक, सम गिनती, बंद)।
३. "खास लगने वाले" गैर-वर्ग शामिल करना (दो की घात आदि)।
४. ० को वर्ग लॉकर गिनना जब लॉकर १..n हों।
५. for k=1..n if k % p == 0 वाला O(n²) जबकि for locker = p; locker <= n; locker += p साफ और तेज़।
न्यूनतम स्मोक आइडिया:
verify(1);
verify(10);
verify(100);
System.out.println(countOpen(100)); // 10
System.out.println(openBySquares(100));
// [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
७. दोस्त को समझाओ सार
सौ लॉकर, सब बंद। सौ लोग। व्यक्ति i हर i-वाँ दरवाज़ा पलटता है।
१. लॉकर k हर भाजक पर एक बार पलटता है।
२. बंद शुरू: विषम पलट → खुला, सम → बंद।
३. भाजक जोड़ियाँ बनाते हैं, सिवाय जब k पूर्ण वर्ग हो (वर्गमूल एक बार गिना जाता है)।
४. इसलिए खुले १, ४, ९, ..., १००। १० हैं (floor(sqrt(100)))।
५. कोड बूलियन सरणी से सिमुलेट कर सकता है, या i*i तब तक निकाल सकता है जब i*i <= n।
अगर बिना पूरी तालिका खींचे कह सको "विषम संख्या गुणनखंड, सिर्फ वर्ग", तो समस्या ६.९ तुम्हारी है। अध्याय ६ यही स्टाइल पुरस्कृत करता है: एक निश्चर सिमुलेशन के ढेर को हरा देता है।
श्रृंखला
- गाइड: सीटीसीआई सीरीज़ गाइड
- पिछला: द एग ड्रॉप प्रॉब्लम
- अगला: पॉइज़न