एनिमल शेल्टर: कुत्ते और बिल्लियों की फीफो गोद-लेना कतार (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ३.६: आश्रय में सिर्फ कुत्ते और बिल्लियाँ सख्त पहले-आओ-पहले-जाओ कतार में। दो कतारों और आगमन क्रम से एनक्यू, डीक्यूएनी, डीक्यूडॉग, डीक्यूकैट बनाओ।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

एक आश्रय निष्पक्ष कतार चलाता है। जानवर एक-एक करके आते हैं। गोद लेने वाला या तो कुल मिलाकर सबसे लंबा इंतज़ार करने वाला जानवर ले सकता है, या सिर्फ कुत्ता या सिर्फ बिल्ली माँगकर उसी प्रकार का सबसे पुराना पा सकता है। कोई खास पालतू नाम लेकर नहीं चुनता। यही शुद्ध फीफो है, ऊपर से प्रकार का फ़िल्टर।

यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली कतार-डिज़ाइन समस्याओं का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ३ यहीं खत्म होता है।

१. आश्रय की उपमा

काउंटर के पीछे दो प्रतीक्षालय सोचो:

कक्ष डी: सिर्फ कुत्ते, आगमन क्रम में।
कक्ष सी: सिर्फ बिल्लियाँ, आगमन क्रम में।

हर जानवर आने पर टिकट नंबर पाता है: ०, १, २, ३, ... छोटा टिकट मतलब पहले आया। दीवार की घड़ी नहीं। आश्रय का अपना पूर्णांक काउंटर है।

जब कोई "कोई भी जानवर" कहे, क्लर्क दोनों कक्षों के आगे झाँकता है और छोटा टिकट वाला चुनता है। जब "एक कुत्ता" कहे, सिर्फ कक्ष डी देखता है। बिल्लियों के लिए भी वही।

एक मिली-जुली कतार में "कोई भी" आसान होता, पर "सिर्फ कुत्ता" के लिए बिल्लियों के पार चलकर पहला कुत्ता ढूँढना पड़ता। दो टाइप वाली कतारें हर ऑपरेशन को सूची के आगे रखती हैं।

२. समस्या सादे शब्दों में

लक्ष्य: ऐसा आश्रय जिसकी संरचना और विधियाँ सिर्फ कुत्ते-बिल्लियों को सख्त फीफो में रखें।

ऑपरेशन:

विधि	अर्थ
`enqueue(animal)`	जानवर आया; अपनी प्रकार की कतार के पीछे जाए
`dequeueAny()`	किसी भी प्रकार का सबसे पुराना जानवर गोद
`dequeueDog()`	सबसे पुराना कुत्ता गोद
`dequeueCat()`	सबसे पुरानी बिल्ली गोद

नियम:

सिर्फ कुत्ते और बिल्लियाँ।
"सबसे पुराना" मतलब सबसे पहले आया, जैविक उम्र नहीं।
पहचान से कोई खास जानवर नहीं चुनते, सिर्फ प्रकार (या कोई भी)।
बिल्ट-इन लिंक्ड लिस्ट या कतार इस्तेमाल कर सकते हो।

कोड से पहले स्पष्ट करो:

आश्रय खाली हो तो? (null लौटाओ या एक्सेप्शन; एक ठेका चुनकर निभाओ।)
कुत्ता माँगा और कोई कुत्ता न बचा? (वही ठेका।)
एक ही नाम दो बार? (हाँ। पहचान ऑब्जेक्ट प्लस क्रम है, नाम की स्ट्रिंग नहीं।)

३. पहले सोचो

एक मिली-जुली कतार

सभी जानवर एक LinkedList<Animal> में।

dequeueAny है removeFirst: ओ(१)।
dequeueDog आगे से चलकर पहला कुत्ता ढूँढता है: सबसे खराब ओ(एन)।
बिल्लियों पर भी वही लागत।

चलता है, और कभी इंटरव्यू में चल जाता है। जब दो सूचियाँ मिली हों तो यह साफ जवाब नहीं।

दो कतारें प्लस क्रम (पसंदीदा)

रखो:

dogs: कुत्तों की कतार
cats: बिल्लियों की कतार
order: हर एनक्यू पर बढ़ने वाला पूर्णांक (तार्किक टाइमस्टैम्प)

एनक्यू पर:

१. जानवर पर मौजूदा order लगाओ, फिर order++। २. प्रकार के हिसाब से कुत्ता या बिल्ली कतार में धक्का दो।

dequeueAny पर:

१. एक तरफ खाली हो तो दूसरी से निकालो। २. दोनों में जानवर हों तो दोनों आगे झाँको और छोटा order वाला निकालो (पहले आया)। ३. दोनों खाली हों तो null (या तुम्हारा खाली ठेका)।

dequeueDog / dequeueCat पर: सिर्फ उसी कतार से पोल।

विरासत क्यों? dequeueAny कुत्ता या बिल्ली लौटाए, इसलिए दोनों साझा Animal आधार रखते हैं। क्रम की तुलना उसी आधार पर रहती है ताकि क्लर्क को ठोस क्लास से मतलब न हो, बस "कौन सा कक्ष"।

४. जावा समाधान

import java.util.LinkedList;

abstract class Animal {
    private int order;
    protected String name;

    public Animal(String name) {
        this.name = name;
    }

    public void setOrder(int order) {
        this.order = order;
    }

    public int getOrder() {
        return order;
    }

    /** True if this animal arrived before the other. */
    public boolean isOlderThan(Animal other) {
        return this.order < other.getOrder();
    }

    public String getName() {
        return name;
    }
}

class Dog extends Animal {
    public Dog(String name) {
        super(name);
    }
}

class Cat extends Animal {
    public Cat(String name) {
        super(name);
    }
}

class AnimalQueue {
    private LinkedList<Dog> dogs = new LinkedList<>();
    private LinkedList<Cat> cats = new LinkedList<>();
    private int order = 0; // arrival counter, not wall-clock time

    public void enqueue(Animal a) {
        a.setOrder(order);
        order++;

        if (a instanceof Dog) {
            dogs.addLast((Dog) a);
        } else if (a instanceof Cat) {
            cats.addLast((Cat) a);
        } else {
            throw new IllegalArgumentException("Only dogs and cats");
        }
    }

    public Animal dequeueAny() {
        if (dogs.isEmpty() && cats.isEmpty()) {
            return null;
        }
        if (dogs.isEmpty()) {
            return dequeueCat();
        }
        if (cats.isEmpty()) {
            return dequeueDog();
        }

        Dog dog = dogs.peek();
        Cat cat = cats.peek();
        if (dog.isOlderThan(cat)) {
            return dequeueDog();
        } else {
            return dequeueCat();
        }
    }

    public Dog dequeueDog() {
        return dogs.isEmpty() ? null : dogs.poll();
    }

    public Cat dequeueCat() {
        return cats.isEmpty() ? null : cats.poll();
    }
}

कदम-दर-कदम:

कदम	क्रिया	कुत्ते आगे	बिल्लियाँ आगे	नोट
१	एनक्यू `Dog("Rex")` क्रम ०	रेक्स	-
२	एनक्यू `Cat("Mimi")` क्रम १	रेक्स	मीमी
३	एनक्यू `Dog("Buddy")` क्रम २	रेक्स	मीमी	बडी, रेक्स के पीछे
४	डीक्यूएनी	बडी	मीमी	रेक्स निकला (क्रम ० जीता १ पर)
५	डीक्यूकैट	बडी	-	मीमी निकली; अकेली बिल्ली
६	डीक्यूएनी	-	-	बडी निकला

अगर order सिर्फ enqueue से लगता है तो बराबर क्रम नहीं आने चाहिए। असली घड़ी के टाइमस्टैम्प में बराबरी हो तो समस्या के नियमों में कोई भी ठीक।

order को long मिलीसेकंड घड़ी भी रख सकते हो। काउंटर इंटरव्यू में आसान है: घड़ी का झुकाव नहीं, "एक ही मिलीसेकंड" की बहस नहीं, तुलना सादा पूर्णांक छोटा-है।

५. जटिलता तालिका

ऑपरेशन	समय	अतिरिक्त स्थान नोट
`enqueue`	ओ(१)	एक स्टैम्प + लिंक्ड लिस्ट पर ऐडलास्ट
`dequeueDog` / `dequeueCat`	ओ(१)	उसी कतार के आगे से पोल
`dequeueAny`	ओ(१)	दो पीक + एक पोल
एक मिली कतार + प्रकार खोज	प्रकार गोद पर ओ(एन)	संरचना सरल, टाइप गोद महँगा

आश्रय में बचे एन जानवरों के लिए स्थान ओ(एन)। हर जानवर पर order क्षेत्र ओ(१)।

६. किनारे के केस और आम गलतियाँ

इंटरव्यूअर ये छेड़ते हैं:

खाली आश्रय किसी भी डीक्यू पर → null (या थ्रो)। बिना जाँचे पीक मत करो।
सिर्फ कुत्ते (या सिर्फ बिल्लियाँ) पर dequeueAny → बिना तुलना के भरी तरफ से लो।
एक कुत्ता, बहुत बिल्लियाँ → टाइप डीक्यू गलत कतार नहीं छीनते; dequeueAny अब भी आगमन क्रम से तय होता है।
अज्ञात Animal उपक्लास → अगर सिर्फ कुत्ता-बिल्ली चलते हैं तो एनक्यू पर अस्वीकार।
नाम टकराव → कुत्ता "मैक्स" और बिल्ली "मैक्स" अलग ऑब्जेक्ट, अलग क्रम।

आम गलतियाँ:

१. एक सूची और हर टाइप गोद पर रैखिक स्कैन। पहले स्केच में ठीक। ओ(एन) लागत बोलो और दो कतारों पर जाओ। २. क्रम स्टैम्प भूलना। फिर दोनों कतारों के आगे की निष्पक्ष तुलना नहीं। ३. नाम या हैश से तुलना, आगमन क्रम से नहीं। आगमन क्रम ही एकमात्र निष्पक्ष कुंजी है। ४. किसी भी इंडेक्स पर remove। हमेशा उस प्रकार की कतार के आगे से लो। ५. एनक्यू के बाद क्रम बदलना। टिकट आगमन पर तय हो जाता है। ६. क्रम पास हों तो गलत कतार से निकालना। दोनों भरे हों तो हमेशा दोनों पीक करो; आदत से कुत्ता/बिल्ली न बारी-बारी करो।

कम से कम इस्तेमाल:

AnimalQueue shelter = new AnimalQueue();
shelter.enqueue(new Dog("Rex"));
shelter.enqueue(new Cat("Mimi"));
Animal any = shelter.dequeueAny(); // Rex
Dog dog = shelter.dequeueDog();    // null if no dogs left
Cat cat = shelter.dequeueCat();    // Mimi if still present

७. दोस्त को समझाने वाला सार

एनिमल शेल्टर प्रकार-फ़िल्टर वाली कतार डिज़ाइन है:

१. कुत्ते एक कतार में, बिल्लियाँ दूसरी में। दोनों फीफो रहें। २. हर आगमन पर बढ़ता हुआ क्रम नंबर लगाओ। ३. dequeueDog / dequeueCat सिर्फ उसी कतार से पोल करें। ४. dequeueAny दोनों आगे झाँके और छोटा क्रम (पुराना जानवर) ले। एक तरफ खाली हो तो दूसरी। ५. कुत्ते-बिल्लियाँ Animal आधार साझा करें ताकि dequeueAny दोनों प्रकार लौटा सके।

दो लाइनें खींच सको, टिकट नंबर समझा सको, और दोनों कक्षों में आगे जानवर हो तो dequeueAny चला सको, तो समस्या ३.६ तुम्हारी है। अध्याय ३ लगभग दो कतारों और एक तुलना वाली संरचना पर बंद होता है।