Animal Shelter

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 specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog and dequeueCat.

Example:

int CAT = 0
int DOG = 1

enqueue("james", DOG);
enqueue("tom", DOG);
enqueue("mimi", CAT);
dequeueAny();  // should return "james"
dequeueCat();  // should return "mimi"
dequeueDog();  // should return "tom"

Challenge:

Single Queue, or Single LinkedList

Solution:

1. Two Priority Queue: one queue for cat, another for dog. When dequeueAny(), compare the top elements of both two queue and choose the latest one. O(logn) overall.

2. Single Queue:

   1. Any: return first element. O(1)
   2. Dog\/Cat: remove the first element and put it to the back of the queue. If found the first dog\/cat return it, then keep moving first element to the end until every element is processed. O(n)

3. Using a single linked list to simulate a queue. Create three headers: 1) first element, 2) first cat, 3) first dog and three tails: 1) last element, 2) last cat, 3) last dog O(1) for all operations.

Code:

//version 1
class Animal {
    String name;
    int timestamp;
    public Animal(String inName, int inTimestamp) {
        name = inName;
        timestamp = inTimestamp;
    }
}

public class AnimalShelter {

    private final static int CAT = 0;
    private final static int DOG = 1;
    private Queue<Animal> dogs;
    private Queue<Animal> cats;
    private Comparator<Animal> animalComparator = new Comparator<Animal>() {
        public int compare(Animal a, Animal b) {
            return a.timestamp - b.timestamp;
        }
    };
    private int timestamp;
    public AnimalShelter() {
        dogs = new PriorityQueue<Animal>(5, animalComparator);
        cats = new PriorityQueue<Animal>(5, animalComparator);
        timestamp = 0;
    }

    void enqueue(String name, int type) {
        Animal a = new Animal(name, getTimestamp());
        if (type == CAT) {
            cats.offer(a);
        } else if (type == DOG) {
            dogs.offer(a);
        }
    }

    public String dequeueAny() {
        if (dogs.isEmpty() && cats.isEmpty()) {
            return "NO MORE ANY";
        }
        if (dogs.isEmpty()) {
            return cats.poll().name;
        }
        if (cats.isEmpty()) {
            return dogs.poll().name;
        }
        if (animalComparator.compare(dogs.peek(), cats.peek()) < 0) {
            return dogs.poll().name;
        } else {
            return cats.poll().name;
        }
    }

    public String dequeueDog() {
        if (dogs.isEmpty()) {
            return "NO MORE DOG";
        }
        return dogs.poll().name;
    }

    public String dequeueCat() {
        if (cats.isEmpty()) {
            return "NO MORE CAT";
        }
        return cats.poll().name;
    }

    private int getTimestamp() {
        timestamp++;
        return timestamp;
    }
}