Problem 🤔

An animal shelter holds only dogs and cats and works on a FIFO basis.

FIFO -> First in, First out

Adopters must select the oldest animal in the shelter, or can pick the oldest dog/cat.

Implement a class to support this shelter. Let’s implement the following methods:

Real World Applications 🌎

We can build a customer relation management system (CRM) for animal shelters! Yayyyyyy

This CRM will always be ready to accept new dogs and cats and will always know how to find:

• the longest tenured animal in the shelter
• the longest tenured dog in the shelter
• the longest tenured cat in the shelter

The Finer Details 🔎

Needing to keep track of the longest tenured animals at any given time… Hmmm.. Like we’ve said before, keeping track of min or max should always hint at using a heap! In this case, we’re going to want to maintain 2 heaps:

1) A dog max tenure heap 2) A cat max tenure heap

If a customer doesn’t have a cat / dog preference then we can return max(-dogMaxHeap[0], -catMaxHeap[0])

Note

• As I’ve mentioned before, python doesn’t natively support max heaps. To mimic this functionality we can use a minheap and multiply by -1 before every insertion and extraction.
• On enqueue, we need to know if we’re receiving a dog or cat, so we’ll define our own internal type for that.

Solution 💡

Complexity Analysis 🧮

Time Complexity

enqueue -> Insert into heap, O(log(n))

dequeueDog, dequeueCat, dequeueAny -> Extract from heap and reorder, O(log(n))

Space Complexity

O(n)

Queues maintained for dogs && cats.

Resources 📚

Cracking the Coding Interview, 3.6, Animal Shelter