Animal Shelter in Java

I have been working my way through the problems in the book Cracking the Coding Interview. The instructions were to maintain an animal shelter that operates on a first in, first out basis (i.e. it is a queue). People must adopt the "oldest" (based on arrival time) of all animals at the shelter, or if they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot choose which specific animal they would like.

AnimalShelter.java

package problem_2_9;

import java.util.LinkedList;
import java.util.NoSuchElementException;

public class AnimalShelter {

    public enum AnimalType{
        DOG, CAT 
    }

    private int animalId;
    LinkedList cats;
    LinkedList dogs;

    public AnimalShelter(){
        cats = new LinkedList();
        dogs = new LinkedList();
    }

    public void enqueue(AnimalType type){
        switch(type){
        case DOG:
            dogs.add(animalId);
            animalId++;
            break;
        case CAT:
            cats.add(animalId);
            animalId++;
            break;
        }
    }
    public Integer dequeueCat(){
        if(cats.isEmpty()) throw new NoSuchElementException("There are no cats in the animal shelter.");
        return cats.pop();
    }

    public Integer dequeueDog(){
        if(dogs.isEmpty()) throw new NoSuchElementException("There are no dogs in the animal shelter");
        return dogs.pop();
    }

    public Integer dequeueAny(){
        if(dogs.isEmpty() && cats.isEmpty()) throw new NoSuchElementException("There are no animals in the animal shelter.");
        if(dogs.isEmpty()){
            return cats.pop();
        }
        else if(cats.isEmpty()){
            return dogs.pop();
        } else{
            if(cats.peek() < dogs.peek()){
                return cats.pop();
            }
            else{
                return dogs.pop();
            }
        }
    }
}

I've tested the AnimalShelter class using this code:

Main.java

```
package proble

The model has failed

I would expect from an animal shelter to actually store animals.
(Well, in programming terms, a representation of animals.)
Your implementation is not an animal shelter, it's an animal-relative-arrival-time shelter. I cannot add animals to it, and cannot retrieve animals from it. I can only add animal types, and retrieve meaningless sequence numbers. This is not an acceptable model of an animal shelter.

Failure to generalize

It's important to read the problem description attentively.
Notice that dogs and cats are not part of the essence of the problem,
they are casually mentioned examples. The target system should support animals of all types, and that seems to be a reasonable expectation.

I think the expected interface is something like this:

interface AnimalShelter {

    add(Animal animal);

    Animal get(AnimalType type);

    Animal get();    
}

Notice that I didn't call these methods enqueue and dequeue.
Those are implementation terms,
not the terms of the problem domain.
(Probably they could be improved, if I knew anything about the real-world domain of animal shelters.)
Different animal shelters may have different policies for adding and getting animals.
Your task is to implement one with a specific policy,
which could be reflected in the name of the class in your implementation,
but this interface can stay as is.

Testing

What you called "testing" is "demonstrating".
It's not testing anything.
Testing should involve assertions (of truths) about the implementation.
Here's an example:

@Test
public void should_return_the_right_type_in_fifo_order() {
    AnimalShelter shelter = new FifoAnimalShelter();

    Animal fluffy = new Cat("fluffy");
    shelter.add(fluffy);

    Animal sparky = new Dog("sparky");
    shelter.add(sparky);

    Animal smelly = new Cat("smelly");
    shelter.add(smelly);

    assertThat(shelter.get(AnimalTypes.CAT)).isEqualTo(fluffy);
    assertThat(shelter.get(AnimalTypes.CAT)).isEqualTo(smelly);
}

Discussion

For all problems in this book, it's important to carefully consider the time and space complexity of the implementation. In your current implementation, this was trivial: all the dequeue* methods have \$O(1)\$ complexity. That should have been a warning sign, indicating that there's more to this exercise. Indeed, if you extend to support all animal types, the complexity analysis becomes more interesting.

Take for example the get() and get(AnimalType) methods. If you use one queue per type, then get(AnimalType) will be \$O(1)\$, and get() will be \$O(k)\$, where \$k\$ is the number of types. If you use one queue for all animals, then get(AnimalType) will be \$O(n)\$, and get() will be \$O(1)\$. Further variations and optimizations will be possible, it's good to think about them and practice calculating their time and space complexity tradeoffs.

StackExchange Code Review Q#144312, answer score: 12