Animal Shelter

An animal shelter, which holds only dogs and cats, 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 specific animal 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.

👉 Link here to the repo to solve the problem

👌 Tips

We could consider keeping a single linked list for dogs and cats, and then iterating through it to find the first dog (or cat).What is the impact of doing this?

Let's suppose we kept separate lists for dogs and cats. How would we find the oldest animal of any type? Be creative!

Think about how you'd do it in real life.You have a list of dogs in chronological order and a list of cats in chronological order. What data would you need to find the oldest animal? How would you maintain this data?

👊 Solution 1

We could explore a variety of solutions to this problem. For instance, we could maintain a single queue. This would make dequeueAny easy, but dequeueDog and dequeueCat would require iteration through the queue to find the first dog or cat. This would increase the complexity of the solution and decrease the efficiency.

An alternative approach which is simple, clean and efficient is to simply use separate queues for dogs and cats, whilst maintaining an arrayList with the order.

The only negative trade off is that whenever you insert or remove you have to iterate through the order list prior dequeuing, which could take O(N).

public class AnimalShelter {
    private LinkedList<Animal> dogList = new LinkedList<>();
    private LinkedList<Animal> catList = new LinkedList<>();
    private ArrayList<Animal> order = new ArrayList<>();

    public void enqueue(Animal animal) {
        switch (animal.animalType) {
            case DOG:
                dogList.add(animal);
            case CAT:
                catList.add(animal);
            default:
                order.add(animal);
        }
    }

    public Animal dequeueDog() {
        Animal dog = dogList.removeFirst();
        order.remove(dog);
        return dog;
    }

    public Animal dequeueCat() {
        Animal cat = catList.removeFirst();
        order.remove(cat);
        return cat;
    }

    public Animal dequeueAny() {
        Animal animal = order.remove(0);

        switch (animal.animalType) {
            case DOG:
                dogList.remove(animal);
            case CAT:
                catList.remove(animal);
        }
        return animal;
    }
}

public class Animal {
    public AnimalType animalType;
    public String name;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

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

    public AnimalType getAnimalType() {
        return animalType;
    }

    public void setAnimalType(AnimalType animalType) {
        this.animalType = animalType;
    }
}

public enum AnimalType {
    CAT,
    DOG
}

---

Question borrowed from “Cracking the coding interview”