Animal Shelter in Java

Question

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<Integer> cats;
    LinkedList<Integer> dogs;

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

    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 problem_2_9;

import problem_2_9.AnimalShelter.AnimalType;

    public class Main {

        public static void main(String[] args){
            // dogs = 0 2 4 6
            // cats = 1 3 5 7
            AnimalShelter shelter = new AnimalShelter();
            for(int i = 0; i < 4; i++){
                shelter.enqueue(AnimalType.DOG);
                shelter.enqueue(AnimalType.CAT);
            }

            for(int i = 0; i < 4; i++){
                System.out.println(shelter.dequeueCat());
                System.out.println(shelter.dequeueDog());
            }
        }
    }

Answer 1

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.

Answer 2

Okay, so there are a few points here, let's mainly touch on the stylistic ones first and then take a look at an alternative way of doing things.

1. You should refer to LinkedList<T> by its List<T> (or Collection<T>!) interface, unless you are actually needing to couple yourself to its implementation. See here.

2. You will have to add a new method and a lot of new logic for every new type of animal you add to the shelter. The code will quickly become a mess of copy pasting.

3. You're throwing an exception in a very expected circumstance (i.e, no cat exists). Consider returning null (better) or returning Optional<T>.

4. AnimalType means you will need to create a new dequeueXXX method, add the logic behind it to the dequeueAny method, create the new LinkedList and add it to the AnimalType enum. There are a lot of places here that you could screw up and forget.

---

This is the alternative way of doing things. Note that this might not compile, but let's go through it; it should give you an idea of the direction I am taking.

interface Animal {}

class AnimalShelter<T implements Animal> {
  private final List<T> list = new LinkedList<T>();

  public Optional<T> dequeue(Class<T> clazz) {
    Optional<T> maybe = Optional.empty();
    Iterator<T> iterator = list.iterator();

    while (iterator.hasNext()) {
      T element = iterator.next();
      if (element.getClass().equals(clazz)) {
        maybe = Optional.of(element); 
      }
      iterator.remove();
    }

    return maybe;
  }
}

So, the first change is that instead of storing animals separately, we are now storing them in one contiguous list and we don't check if the list is empty; instead, we use iterators. Note that I use the List<T> interface to refer to the list and not the LinkedList<T> interface; you should always code to an interface, not an implementation.

You no longer need to add new dequeueXXX methods every time a new type of animal is added; as long as the class you pass to dequeue descends from something that implements Animal, you can just pass the class object instead - for example, Cat.class †.

You picked a LinkedList<T> but I'm not sure if you understand the reason why it is the right choice here. Basically, a LinkedList<T> has much, much faster removals than an ArrayList<T> does because in order for an ArrayList<T> to remove an item that isn't at the end it must 'shift' all elements in order to do so. LinkedList<T> does not have this issue.

I'm also returning an Optional<T> rather than throwing an exception when an element doesn't exist. This is much nicer on the programmer. Don't use exceptions for control flow, and an animal not being in a shelter is most definitely not an exceptional circumstance.

The performance of this code is pretty good: We only take, at most, one iteration through the list in order to find an animal and the removal of the element via iterator is in constant time. This is not quite as fast as your code (as your code uses constant time operations as well), but it allows us to simplify things drastically.

One thing I dislike about my own code is that this kinda breaks the idea of OOP a bit (because we are checking classes at runtime), but I'm okay with that if it means that we get a simpler user-facing API with decent performance that isn't hell to maintain. If there are any other 'nice' ways of doing this I am all ears.

---

† I'm unsure of the performance impact of using getClass(). I'm under the impression that using Reflection can be expensive, which may make this approach quite costly as we use getClass() in a loop over every element. If this is the case, it may be worth instead creating a Record class which lazily stores the class object. Premature optimisation, but maybe a point of consideration.

Answer 3

Prefer interfaces as types

    LinkedList<Integer> cats;
    LinkedList<Integer> dogs;

In this case, the interface that fits the methods that you use is Deque<Integer>.

    private final Deque<Integer> cats = new LinkedList<>();
    private final Deque<Integer> dogs = new LinkedList<>();

Note that you can get rid of the constructor if you initialize these when you declare them.

You never set them again, so you can mark them final. You don't have to -- it's a judgment call whether it just makes the declaration more verbose or provides useful information.

I'd declare the object fields as private. There doesn't seem to be any need to access them outside the class.

Don't Repeat Yourself (DRY)

        switch(type){
        case DOG:
            dogs.add(animalId);
            animalId++;
            break;
        case CAT:
            cats.add(animalId);
            animalId++;
            break;
        }

You can shorten this by moving the common code outside the switch.

        switch(type){
        case DOG:
            dogs.add(animalId);
            break;
        case CAT:
            cats.add(animalId);
            break;
        }

        animalId++;

An alternative

Animal.java

public class Animal {

    private int id;
    private AnimalType type;

    Animal(int id, AnimalType type) {
        this.id = id;
        this.type = type;
    }

    public int getID() {
        return id;
    }

    public AnimalType getType() {
        return type;
    }

    public String toString() {
        return type.toString() + " " + id;
    }

}

This couples an identifier with a type.

AnimalShelter.java

public class AnimalShelter {

    private final Map<AnimalType, Queue<Animal>> animalQueues = new EnumMap<>(AnimalType.class);
    private int animalId = 1;

    public void enqueue(AnimalType type) {
        Queue<Animal> queue = animalQueues.get(type);
        if (queue == null) {
            queue = new LinkedList<>();
            animalQueues.put(type, queue);
        }

        queue.add(new Animal(animalId, type));
        animalId++;
    }

    public Animal dequeue(AnimalType type) {
        Queue<Animal> queue = animalQueues.get(type);

        return (queue == null || queue.isEmpty()) ? null : queue.poll();
    }

    public Animal dequeueAny() {
        int minimum = animalId;
        Queue<Animal> next = null;
        for (Queue<Animal> queue : animalQueues.values()) {
            Animal animal = queue.peek();
            if (animal == null) {
                continue;
            }

            int id = animal.getID();

            if (id < minimum) {
                next = queue;
                minimum = id;
            }
        }

        return (next == null) ? null : next.poll();
    }
}

With this code, adding a new type of animal is as simple as adding a new entry to the AnimalType enum.

The enqueue method will automatically create any missing type of queue. \$\mathcal{O}(1)\$.

Rather than a dequeue method for each type of animal, this has one dequeue method that takes an animal type as a parameter. This is \$\mathcal{O}(1)\$.

Rather than have a separate named queue for each animal type, this uses a EnumMap to store a queue for each type. More generally you can use a HashMap when the keys aren't enum values.

The dequeueAny method loops over the queues. This is \$\mathcal{O}(m)\$ where \$m\$ is the number of entries in the AnimalType enum. But note that your original method was also \$\mathcal{O}(m)\$. You just had to manually add another case for each new type. This gave it the appearance of constant time while still increasing in complexity with each new type.

Answer 4

Excluding what other answers have already stated you can also use a EnumMap to map a AnimalType to a queue. The running time will be \$O(1)\$ for dequeue of a single type and \$O(t)\$ for dequeueAny, \$t\$ being the number of animal types.

import java.util.Comparator;
import java.util.EnumMap;
import java.util.Map;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.Optional;


public class AnimalShelter {

    int size;
    Map<AnimalType, Queue<Animal>> map;

    public AnimalShelter() {
        size = 0;
        map = new EnumMap<>(AnimalType.class);
    }

    public void enqueue(AnimalType type) {
        map.computeIfAbsent(type, a -> map.put(a, new ArrayDeque<>()));
        map.get(type).add(new Animal(++size, type));
    }

    public Optional<Animal> dequeue(AnimalType type){
        return Optional.ofNullable(map.get(type))
                       .filter(q -> !q.isEmpty())
                       .map(q -> q.poll());
    }

    public Optional<Animal> dequeue() {
        return map.values()
                .stream()
                .filter(q -> !q.isEmpty())
                .min(Comparator.comparingInt(q -> q.peek().getId()))
                .map(Queue::poll);
    }
    public int size() {
        return size;
    }
}

enum AnimalType { DOG, CAT }
public final class Animal {
    private final int id;
    private final AnimalType type;

    public Animal(int id, AnimalType type) {
        this.id = id;
        this.type = type;
    }
    public int getId() {
        return id;
    }
    public AnimalType getType() {
        return type;
    }

    @Override
    public String toString() {
        return id + " " + type.name();
    }
}