Animal Shelter

Design, Queue,

Hard

Question

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

Can you do it with single Queue?

Analysis

Two Queues

关于时间oldest优先，可以从两个角度考虑 1. Queue本身的first-in-first-out(FIFO)特性 2. 元素自带时间戳time stamp，方便比较

于是，这里可以存两个LinkedList：cats，dogs，链表中的元素除了name，还可以存入time，这样当dequeueAny()时，可以通过time来决定哪一个最先出队列。 dequeue均可以在O(1)时间内实现。

Single Queue

challenge里所说的Single Queue的方法，难点在于shift queue，因为不能用两个queue分别来track同一个type中的先后顺序，那么就需要用shift的方式来维持队列。找到对应的type，记录shift的次数，这样poll了之后，要再shift总长减去之前shift的次数，来还原queue的状态。相应的dequeue算法复杂度也高很多O(n)

Solution

Two Queues

class Node {
    int time;
    String name;

    Node(String name, int time) {
        this.name = name;
        this.time = time;
    }
    public String getName() {
        return this.name;
    }
    public int getTime() {
        return this.time;
    }
}

public class AnimalShelter {

    private static final int DOG = 1;
    private static final int CAT = 0;

    private int tot;
    private LinkedList<Node> cats, dogs;

    public AnimalShelter() {
        // do initialize if necessary
        tot = 0;
        dogs = new LinkedList<Node>();
        cats = new LinkedList<Node>();
    }

    /**
     * @param name a string
     * @param type an integer, 1 if Animal is dog or 0
     * @return void
     */
    void enqueue(String name, int type) {
        tot += 1;
        if (type == DOG) {
            dogs.add(new Node(name, tot));
        } else {
            cats.add(new Node(name, tot));
        }
    }

    public String dequeueAny() {
        if (cats.isEmpty()) {
            return dequeueDog();
        } else if (dogs.isEmpty()) {
            return dequeueCat();
        } else {
            int dogTime = dogs.getFirst().getTime();
            int catTime = cats.getFirst().getTime();
            if (catTime < dogTime) {
                return dequeueCat();
            } else {
                return dequeueDog();
            }
        }
    }

    public String dequeueDog() {
        String name = dogs.getFirst().getName();
        dogs.removeFirst();
        return name;
    }

    public String dequeueCat() {
        String name = cats.getFirst().getName();
        cats.removeFirst();
        return name;
    }
}

Single Queue

class Node {
    String name;
    int type;
    Node(String name, int type) {
        this.name = name;
        this.type = type;
    }
}
public class AnimalShelter {
    Queue<Node> queue;
    public AnimalShelter() {
        // do initialize if necessary
        queue = new LinkedList<Node>();
    }

    /**
     * @param name a string
     * @param type an integer, 1 if Animal is dog or 0
     * @return void
     */
    void enqueue(String name, int type) {
        // Write your code here
        queue.offer(new Node(name, type));
    }

    public String dequeueAny() {
        // Write your code here
        Node node = queue.poll();
        return node.name;
    }

    public String dequeueDog() {
        // Write your code here
        return dequeueType(1);
    }

    public String dequeueCat() {
        // Write your code here
        return dequeueType(0);
    }

    private String dequeueType(int type) {
        int shiftTime = 0;
        while (queue.peek().type != type) {
            queue.offer(queue.poll());
            shiftTime++;
        }
        Node node = queue.poll();
        shiftTime = queue.size() - shiftTime;
        while (shiftTime != 0) {
            queue.offer(queue.poll());
            shiftTime--;
        }
        return node.name;
    }
}