8
\$\begingroup\$

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());
            }
        }
    }
\$\endgroup\$
  • 2
    \$\begingroup\$ Suppose the shelter now has to support cockatoos and snakes. Would you add more data structures and methods to your class? Your code will have scaling issues (i.e copy pasta) as more and more animals are added to the shelter. Additionally, do you think it might be a better idea to allow for someone to check for the existence of an animal instead of throwing an exception when there isn't one? (Of course, then you have to worry about synchronisation....) \$\endgroup\$ – Dan Pantry Oct 15 '16 at 21:48
  • \$\begingroup\$ If it is only a dog or cat then I like this. Given shelters rarely run out a animals I don't even mind the exceptions. \$\endgroup\$ – paparazzo Oct 16 '16 at 1:56
  • \$\begingroup\$ '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.) specific animal the would like They can not choose which specific animal they would like.' --- What?? Just based upon this, the problem is fundamentally flawed to the paradoxial point that no solution can possibly be coded. I think that you need to rephrase exactly what the specification is. It should also be noted that the answers below are NOT THREAD SAFE. \$\endgroup\$ – Luke A. Leber Oct 16 '16 at 21:29
  • \$\begingroup\$ @LukeA.Leber actually, it's not a broken spec. They can ask for the oldest animal at the shelter, without caring about the species, or they can ask for the oldest animal of a certain species, but what they cannot do is choose a random animal from the list. It has to be the oldest animal on the list from that type. \$\endgroup\$ – Nzall Oct 17 '16 at 7:48
  • \$\begingroup\$ Nzall. I had a typo in the problem statement originally, Jamal fixed it. \$\endgroup\$ – newToProgramming Oct 17 '16 at 9:22
12
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for such a constructive answer. Would you be willing to expand on that last point more? I do know the basics of complexity analysis. In what way is the complexity analysis trivial? Is it because I have hardcoded in two types of animals? \$\endgroup\$ – newToProgramming Oct 16 '16 at 10:24
  • 2
    \$\begingroup\$ Yes. I added more explanation. \$\endgroup\$ – Stop ongoing harm to Monica Oct 16 '16 at 10:42
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Excellent answer, obviously a lot to learn from this. I will say though that this is one of those interview questions where time/space complexity are supposed to be considered. I am sure in reality it is much better to maintain a single queue because it makes the code more readable and maintainable but it does also make lookup O(n) in general. I guess the way to go would be to mention these sort of trade-offs if one was doing this for an interview, is that a fair assesment? \$\endgroup\$ – newToProgramming Oct 15 '16 at 22:49
  • 2
    \$\begingroup\$ Definitely, and the trade off of having the one homogenous list is that you can't find the first element in it without iterating through the collection up until that point. Your approach works, but in my opinion it is much more prone to developer error (and or frustration). If I were interviewing you, I'd prefer to see this approach than the other one, but I'd be even more impressed if you could justify why you took your approach over this one. In general, though, don't optimise unless you see an issue. Until that point, you should code for the programmer, not for the computer. \$\endgroup\$ – Dan Pantry Oct 15 '16 at 22:53
  • \$\begingroup\$ BTW I would consider leaving your question open for a little longer rather than accepting my answer (if you were considering it) to attract more answers from more experienced java developers than myself :) \$\endgroup\$ – Dan Pantry Oct 15 '16 at 22:56
  • \$\begingroup\$ "package names should not have underscores": This is a misunderstanding. Underscores are perfectly acceptable and even encouraged since they makes the names more readable. \$\endgroup\$ – Lii Oct 16 '16 at 10:00
  • 1
    \$\begingroup\$ Thanks for the feedback. I'll remove the erroneous point about package names. With regards to the code snippet I posted, while you are correct maybe is not a great variable name, the code snippet was not intended to be a "do it exactly like this", but a way of visually explaining my approach. \$\endgroup\$ – Dan Pantry Oct 16 '16 at 11:16
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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();
    }
}
\$\endgroup\$
  • \$\begingroup\$ You could also use an EnumMap instead of a HashMap. \$\endgroup\$ – Roland Illig Oct 16 '16 at 9:35
  • \$\begingroup\$ Oh yes I forgot about EnumMap you are right :). \$\endgroup\$ – MAG Oct 16 '16 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.