टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: सही लंबाई वाले कैरेक्टर ऐरे पर इन-प्लेस यूआरएल एन्कोडिंग। रिक्त स्थान गिनें, पीछे से चलें, %२० लिखें बिना उन अक्षरों को मिटाए जो अभी पढ़ने बाकी हैं।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
यूआरएल कच्चे रिक्त स्थान नहीं रख सकते। एक रिक्त स्थान तीन अक्षरों वाला टोकन %20 बन जाता है। इस समस्या के इंटरव्यू रूप में आपको कोई लाइब्रेरी हेल्पर नहीं बुलाना है। आपको एक char[] मिलता है जिसके अंत में पहले से खाली जगह है, साथ में स्ट्रिंग की सही लंबाई (पैडिंग से पहले कितने अक्षर मायने रखते हैं)। काम है ऐरे को इन-प्लेस फिर से लिखना।
यह क्लासिक सीटीसीआई-शैली सेट के ऐरे और स्ट्रिंग अध्याय की समस्या १.३ है। सीटीसीआई जावा श्रृंखला का हिस्सा।
रोजमर्रा की उपमा
थिएटर की एक कतार सोचें। पहले तेरह सीटों पर असली लोग बैठे हैं। कतार के अंत में अतिरिक्त खाली सीटें हैं।
हर खड़ा व्यक्ति (एक रिक्त स्थान) को एक के बजाय तीन सीटें चाहिए: अक्षर %, 2, और 0। अगर आप आगे से पैक करना शुरू करें, तो आपके पीछे हर व्यक्ति को बार-बार दाईं ओर खिसकना पड़ेगा। यह धीमा है और आसानी से गड़बड़ होता है।
अगर आप पीछे से शुरू करें, तो पहले खाली सीटें लेते हैं और लोगों (या %20) को खाली स्लॉट में रखते हैं। जिसे अभी हिलाना बाकी है, वह ओवरराइट नहीं होता। पूरा ट्रिक यही है।
सादे शब्दों में समस्या
इनपुट
chars: कैरेक्टर ऐरे। असली स्ट्रिंग इंडेक्स0 .. trueLength - 1में रहती है। बाकी ऐरे अतिरिक्त बफर है।trueLength: असली सामग्री के कितने अक्षर हैं (पूरे ऐरे की लंबाई नहीं)।
आउटपुट
- वही ऐरे, जिसमें सही लंबाई वाले हिस्से का हर रिक्त स्थान
%,2,0से बदला गया हो। - रिटर्न टाइप अक्सर
void(इन-प्लेस बदलना) या आसान टेस्ट के लिए अंतिम स्ट्रिंग होता है।
जो मान्यताएं जोर से कहें
१. ऐरे में विस्तार के लिए काफी जगह है। हर रिक्त स्थान दो अतिरिक्त अक्षर जोड़ता है।
२. सिर्फ सही-लंबाई क्षेत्र के रिक्त स्थान मायने रखते हैं। अंत के बफर अक्षर "सामग्री के रिक्त स्थान" नहीं हैं।
३. जावा में char[] इस्तेमाल करें ताकि इन-प्लेस लिख सकें। StringBuilder से नई स्ट्रिंग बनाना अलग समस्या हल करता है (आसान रास्ता बता सकते हैं, फिर इन-प्लेस संस्करण करें)।
क्लासिक उदाहरण
Input: chars = ['M','r',' ','J','o','h','n',' ','S','m','i','t','h',' ',' ',' ',' ']
trueLength = 13
Output: ['M','r','%','2','0','J','o','h','n','%','2','0','S','m','i','t','h']
स्ट्रिंग "Mr John Smith" की लंबाई १३ है और दो रिक्त स्थान हैं। अंतिम लंबाई 13 + 2 * 2 = 17 है।
कोड से पहले कैसे सोचें
ब्रूट फोर्स विचार (और क्यों दुखता है)
बाएं से दाएं स्कैन करें। रिक्त स्थान दिखे तो हर बाद वाले अक्षर को दो जगह दाईं खिसकाएं, फिर %20 लिखें। हर खिसकाव प्रति रिक्त स्थान O(n) है, इसलिए बहुत रिक्त स्थान लगभग O(n²) बन जाते हैं। इंटरव्यूअर बेहतर मांगेगा।
बेहतर विचार: अंत से संपादित करें
१. सही-लंबाई क्षेत्र में कितने रिक्त स्थान हैं, गिनें।
२. अंतिम लेखन इंडेक्स निकालें: आपको trueLength + 2 * spaceCount स्लॉट चाहिए (इंडेक्स 0 से उस संख्या घटा एक तक)।
३. असली स्ट्रिंग को दाएं से बाएं चलें।
४. गैर-रिक्त अक्षर को अंत से अगले खाली स्लॉट में कॉपी करें।
५. रिक्त स्थान पर '0', फिर '2', फिर '%' लिखें (पीछे जाते हुए, ताकि बाएं से दाएं पढ़ने पर तीन अक्षर सही क्रम में हों)।
पीछे क्यों काम करता है: हर लेखन ऐसे स्लॉट में जाता है जो या तो बफर था या जिसमें पहले से संसाधित अक्षर था। अभी न पढ़ा इनपुट कभी नहीं मिटता।
जावा समाधान
public final class Urlify {
private Urlify() {}
/**
* Replaces spaces with %20 in place.
* chars must have room for the expansion: trueLength + 2 * spaceCount.
*/
public static void urlify(char[] chars, int trueLength) {
if (chars == null || trueLength < 0 || trueLength > chars.length) {
throw new IllegalArgumentException("bad length");
}
int spaces = 0;
for (int i = 0; i < trueLength; i++) {
if (chars[i] == ' ') {
spaces++;
}
}
// Index of the last slot we will write into.
int write = trueLength + spaces * 2 - 1;
if (write >= chars.length) {
throw new IllegalArgumentException("array too small for %20 expansion");
}
for (int read = trueLength - 1; read >= 0; read--) {
char c = chars[read];
if (c == ' ') {
chars[write] = '0';
chars[write - 1] = '2';
chars[write - 2] = '%';
write -= 3;
} else {
chars[write] = c;
write--;
}
}
}
/** Convenience for tests: build a padded char array from a string and true length. */
public static String urlifyString(String s, int trueLength) {
int spaces = 0;
for (int i = 0; i < trueLength; i++) {
if (s.charAt(i) == ' ') {
spaces++;
}
}
int finalLen = trueLength + spaces * 2;
char[] chars = new char[finalLen];
for (int i = 0; i < trueLength; i++) {
chars[i] = s.charAt(i);
}
urlify(chars, trueLength);
return new String(chars);
}
}
उदाहरण का वॉकथ्रू
शुरुआत: असली सामग्री "Mr John Smith", दो रिक्त स्थान, write इंडेक्स 16 से शुरू।
| चरण | पढ़ा अक्षर | क्रिया | बाद में लेखन सूचकांक |
|---|---|---|---|
| १ | h |
१६ पर कॉपी | १५ |
| २ | t |
१५ पर कॉपी | १४ |
| ३ | i |
१४ पर कॉपी | १३ |
| ४ | m |
१३ पर कॉपी | १२ |
| ५ | S |
१२ पर कॉपी | ११ |
| ६ | रिक्त | ९-११ पर %20 |
८ |
| ७ | n |
८ पर कॉपी | ७ |
| ... | ... | आगे बढ़ें | ... |
| अंतिम रिक्त / अक्षर | ... | आगे पूरा करें | हो गया |
खत्म होने पर ऐरे में "Mr%20John%20Smith" होता है।
जटिलता
| माप | लागत | क्यों |
|---|---|---|
| समय | O(n) |
एक पास रिक्त गिनने को, एक पास फिर लिखने को। n है trueLength। |
| अतिरिक्त स्थान | O(1) |
कुछ पूर्णांक ही। आउटपुट दिए गए ऐरे का ही उपयोग करता है। |
अगर इंटरव्यूअर नई स्ट्रिंग मान ले, तो StringBuilder भी समय में O(n) और अतिरिक्त स्थान में O(n) है। इस प्रश्न का मूल इन-प्लेस संस्करण है।
किनारे के मामले जो इंटरव्यूअर छूते हैं
- शून्य रिक्त स्थान: अंतिम लंबाई
trueLengthके बराबर। उल्टा लूप हर अक्षर को खुद पर (या बिना बढ़ोतरी पर उसी इंडेक्स पर) कॉपी करता है। सही ही रहता है। - सब रिक्त स्थान: हर अक्षर
%20बनता है। क्षमता3 * trueLengthचाहिए। - असली सामग्री के आगे या पीछे रिक्त: फिर भी एन्कोड करें। सही लंबाई ४ वाली
" hi "बनती है"%20hi%20"। - खाली सही लंबाई (
0): कुछ नहीं करना। ऋणात्मक लंबाई से बचाव रखें। - ऐरे बहुत छोटा: जल्दी फेल करें। व्हाइटबोर्ड पर क्षमता सूत्र बोलें: अंतिम आकार =
trueLength + 2 * spaceCount। - टैब या अन्य व्हाइटस्पेस: क्लासिक समस्या सिर्फ स्पेस अक्षर
' 'बदलती है। पूछें कि अन्य व्हाइटस्पेस गिने या नहीं। आमतौर पर नहीं। - यूनिकोड / मल्टी-बाइट: जावा में
charयूटीएफ-१६ कोड यूनिट है। इंटरव्यू में एएससीआईआई पाठ के यूआरएल एन्कोडिंग के लिए रिक्त स्थान पर टिके रहें।
आम गलतियां
१. आगे से संपादित करना और बार-बार खिसकाना: द्विघातीय, दबाव में सही करना मुश्किल।
२. chars.length को सही लंबाई मानना। अंत के बफर रिक्त स्थान सामग्री नहीं हैं। इसलिए trueLength अलग दिया जाता है।
३. पीछे जाते समय %, 2, 0 गलत क्रम में लिखना। याद रखें: तीन स्लॉट में सबसे दायां पहले '0' पाता है जब आप अंत से लिखते हैं।
४. write पर ऑफ-बाय-वन। शुरू करें trueLength + 2 * spaces - 1 से, trueLength + 2 * spaces से नहीं।
५. गलत दिशा में राइट हेड से आगे पढ़ते हुए म्यूटेट करना। पीछे चलना उस टक्कर से बचाता है।
जल्दी चला सकने वाला चेक
public static void main(String[] args) {
// 13 chars of content, room for two spaces -> +4
char[] chars = "Mr John Smith ".toCharArray(); // length 17
Urlify.urlify(chars, 13);
System.out.println(new String(chars)); // Mr%20John%20Smith
System.out.println(Urlify.urlifyString("Mr John Smith", 13));
System.out.println(Urlify.urlifyString("nospace", 7)); // nospace
System.out.println(Urlify.urlifyString(" ", 2)); // %20%20
}
दोस्त को समझाएं
आपके पास कैरेक्टर ऐरे है: आगे असली स्ट्रिंग, अंत में खाली सीटें। रिक्त स्थान तीन अक्षर %20 बनने चाहिए। रिक्त गिनें, स्ट्रिंग कितनी बढ़ेगी निकालें, फिर अंतिम असली अक्षर से पीछे चलें। सामान्य अक्षर खाली सीटों में पीछे से कॉपी करें। रिक्त मिले तो तीन सीटों में %20 रख दें। क्योंकि आप अंत से भरते हैं, जिसे अभी पढ़ना बाकी है वह कभी नहीं मिटता। एक गिनती पास, एक लेखन पास, रैखिक समय, स्थिर अतिरिक्त मेमोरी।
अध्याय १ में आगे: पैलिंड्रोम परम्यूटेशन। पिछला: चेक परम्यूटेशन।