Cracking The Coding Interview/Q 3.7

From Software Engineers Wiki
Jump to: navigation, search

An animal shelter holds only dogs and cats, and operates on a strictly "first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specificanimal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog and dequeueCat.You may use the built-in LinkedList data structure.

Answer

#include <iostream>
#include <mutex>
#include <list>

class CAnimal {
public:
        enum { NotAnimal, Dog, Cat };
private:
        int m_kind;
        std::string m_name;
public:
        CAnimal() : m_kind {NotAnimal} {}
        CAnimal(int kind, const char *name) : m_kind {kind}, m_name {name} {}
        int getKind(void) { return m_kind; }
        void print(void) {
                if (m_kind == Dog)
                        std::cout << "Dog: ";
                else if (m_kind == Cat)
                        std::cout << "Cat: ";
                else
                        std::cout << "Unknown: ";
                std::cout << m_name << std::endl;
        }
};

class CAnimalShelter {
private:
        std::mutex m_mutex;
        std::list<CAnimal> m_animals;
public:
        CAnimalShelter() {}
        void enqueue(CAnimal animal);
        bool dequeueAny(CAnimal &animal);
        bool dequeueDog(CAnimal &animal);
        bool dequeueCat(CAnimal &animal);
protected:
        bool dequeueKind(CAnimal &animal, int kind);
};

void CAnimalShelter::enqueue(CAnimal animal)
{
        m_animals.push_back(animal);
}

bool CAnimalShelter::dequeueAny(CAnimal &animal)
{
        std::lock_guard<std::mutex> lock(m_mutex);
        if (m_animals.empty())
                return false;
        animal = m_animals.front();
        m_animals.pop_front();
        return true;
}

bool CAnimalShelter::dequeueDog(CAnimal &animal)
{
        return dequeueKind(animal, CAnimal::Dog);
}

bool CAnimalShelter::dequeueCat(CAnimal &animal)
{
        return dequeueKind(animal, CAnimal::Cat);
}

bool CAnimalShelter::dequeueKind(CAnimal &animal, int kind)
{
        std::lock_guard<std::mutex> lock(m_mutex);
        auto il = m_animals.begin();
        while (il != m_animals.end()) {
                if (il->getKind() == kind) {
                        animal = *il;
                        m_animals.erase(il);
                        return true;
                }
                ++il;
        }
        return false;
}

A test program.

int main(void)
{
        CAnimalShelter shelter;
        CAnimal animal;

        shelter.enqueue(CAnimal(CAnimal::Dog, "DogA"));
        shelter.enqueue(CAnimal(CAnimal::Cat, "CatA"));
        shelter.enqueue(CAnimal(CAnimal::Dog, "DogB"));
        shelter.enqueue(CAnimal(CAnimal::Cat, "CatB"));
        shelter.enqueue(CAnimal(CAnimal::Dog, "DogC"));
        shelter.enqueue(CAnimal(CAnimal::Cat, "CatC"));

        shelter.dequeueAny(animal);
        animal.print();
        while (shelter.dequeueDog(animal))
                animal.print();
        while (shelter.dequeueAny(animal))
                animal.print();

        return 0;
}

Test result.

Dog: DogA
Dog: DogB
Dog: DogC
Cat: CatA
Cat: CatB
Cat: CatC
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox