Cracking The Coding Interview Together – Problem 3.6: Animal Shelter

In this edition of Cracking The Coding Interview — Together, we explore a problem that sits at the intersection of business logic and data structure design. We aren’t just sorting numbers; we are building a system that must respect time, category, and strict fairness.

When you first read the prompt, it sounds like a simple queue implementation. But as you dig deeper, you realize that the "either/or" nature of the selection creates a technical conflict. How do you maintain a global order while allowing filtered access? Let’s break it down as if we were designing the backend for a real-world adoption agency.

As always, we’ll follow the same structure that you would use in a real interview.

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

Animal Shelter: An animal shelter, which holds only dogs and cats, 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. You may use the built-in LinkedList data structure.

The Goal:

• If someone wants a Dog, they get the dog that has been there the longest.
• If someone wants a Cat, they get the cat that has been there the longest.
• If someone wants Any animal, they get whichever animal (cat or dog) has the overall earliest arrival time.

Analyse the problem statement together

The core of this problem is FIFO (First-In, First-Out). In the world of computer science, FIFO equals a Queue.

However, we have two different "flavors" of data (Dogs and Cats) and three ways to retrieve them:

1. Give me a Dog (Oldest dog).
2. Give me a Cat (Oldest cat).
3. Give me Anything (The absolute oldest animal regardless of species).

If we put all animals into one single LinkedList<Animal>, we face a massive performance issue. If someone wants a Dog, and the first 500 animals in the queue are Cats, we have to iterate through the entire list to find that first dog. In the world of big O notation, that is an O(N) operation. For a high-scale system, O(N) on a basic retrieval is a failure.

If we create two separate queues—one for dogs and one for cats—we solve the specific retrieval problem. dequeueDog becomes O(1) because the oldest dog is always at the head of the dog queue. But we run into a new problem: How do we know which animal arrived first globally?

If the dog queue has "Buddy" at the front and the cat queue has "Mittens" at the front, who has been in the shelter longer? Without extra metadata, the queues are silos. They don't talk to each other.

Questions for the interviewer

Before jumping into the implementation, a senior engineer always clarifies the boundaries. In a system involving living entities (or any real-world simulation), the edge cases are where the bugs hide. Here is what we should ask to define our "Animal Shelter" constraints:

1. What is the scale of the shelter?

• Why ask this? If the shelter only holds 50 animals, almost any solution works. But if this is a national database for thousands of shelters (scale), we need to ensure our dequeueAny logic is $O(1)$. It confirms our choice to use separate queues rather than a single list.

2. How do we handle "Arrival Time" collisions?

• Why ask this? If two animals are registered at the exact same second, how is "older" defined? By asking this, you lead the interviewer toward the "Sequence Number" or "Timestamp" solution. You are essentially hinting that System.currentTimeMillis() might not be granular enough.

3. Are there more animal types coming?

• Why ask this? Right now, it's just Dogs and Cats. But what if they add Birds or Rabbits tomorrow? Asking this shows you are thinking about Extensibility. If the number of types grows to 100, our if/else logic in dequeueAny would become a nightmare. This prepares the ground for a more robust Object-Oriented design.

4. Can we modify the Animal objects?

• Why ask this? We need to know if we can add an order or timestamp field to the Animal class. If the Animal objects are "read-only" from an external library, we might need a "Wrapper" class or a Pair structure to store the metadata.

Think about the Solution

To solve the silo problem, we need a "Global Clock" or a Sequence Number. Every time an animal enters the shelter (the enqueue operation), we "stamp" it with an incrementing integer.

The Architecture:

1. Base Class (Animal): Holds the name and the "arrival timestamp" (the order).
2. Subclasses (Dog, Cat): Inherit from the base class.
3. The Shelter Manager: Holds two separate LinkedList queues.

The "Aha!" Moment: Comparing the Heads

When a user calls dequeueAny(), we look at the "Head" of the Dog queue and the "Head" of the Cat queue. We compare their timestamps. The animal with the lower timestamp is the one that arrived earlier. We then remove and return that animal.

This keeps all operations—enqueue, dequeueDog, dequeueCat, and dequeueAny—at a lightning-fast $O(1)$ time complexity.

How It Works

Before we look at the code, let's address the parts that usually trip up engineers during an interview.

1. Class Hierarchy and Abstract Logic

Why use an abstract class for Animal? Because we don't want anyone to be able to create just an "Animal." In our shelter, an animal must be either a Dog or a Cat. By using an abstract class, we can share the order logic and the isOlderThan comparison logic without duplicating code in the subclasses.

2. The Integer "Timestamp"

Why not use System.currentTimeMillis()?

In a high-concurrency environment, two animals could theoretically be enqueued at the exact same millisecond. While rare in a physical shelter, it’s a bad practice in software. Using a simple int order that increments by 1 ensures that every single arrival has a unique, deterministic sequence.

3. Avoiding "InstanceOf" in Business Logic

While we use instanceof to route the animal to the correct queue during enqueue, we want to avoid it in the dequeue logic. By delegating the comparison to the Animal class (using the isOlderThan method), we keep the Shelter class focused on managing the lists, not the internals of the animals.

Write code and explain

Now let’s translate this idea into code.

Java code

import java.util.LinkedList;

abstract class Animal {
    private int order;
    protected String name;

    public Animal(String n) {
        name = n;
    }

    public void setOrder(int ord) {
        order = ord;
    }

    public int getOrder() {
        return order;
    }

    /* Compare arrival times of two animals */
    public boolean isOlderThan(Animal a) {
        return this.order < a.getOrder();
    }
}

class Dog extends Animal {
    public Dog(String n) {
        super(n);
    }
}

class Cat extends Animal {
    public Cat(String n) {
        super(n);
    }
}

class AnimalShelter {
    // Separate queues for O(1) specific retrieval
    LinkedList<Dog> dogs = new LinkedList<Dog>();
    LinkedList<Cat> cats = new LinkedList<Cat>();
    
    private int order = 0; // The global timestamp

    public void enqueue(Animal a) {
        // Stamp the animal with its global arrival sequence
        a.setOrder(order);
        order++;

        if (a instanceof Dog) {
            dogs.addLast((Dog) a);
        } else if (a instanceof Cat) {
            cats.addLast((Cat) a);
        }
    }

    public Animal dequeueAny() {
        // Edge cases: One queue is empty
        if (dogs.isEmpty()) {
            return dequeueCat();
        } else if (cats.isEmpty()) {
            return dequeueDog();
        }

        // Both queues have animals, compare the oldest of each
        Dog dog = dogs.peek();
        Cat cat = cats.peek();

        if (dog.isOlderThan(cat)) {
            return dequeueDog();
        } else {
            return dequeueCat();
        }
    }

    public Dog dequeueDog() {
        return dogs.poll();
    }

    public Cat dequeueCat() {
        return cats.poll();
    }
}

The Enqueue Operation

Notice that we don't just add the animal to a list. We perform a "Check-in" process. The assignment of the order variable is essentially the "Ticket Number" the animal gets when it enters. Because the number only goes up, we are guaranteed a perfect timeline.

The DequeueAny Operation

This is where most juniors fail. They try to find a way to merge the lists or iterate. Our approach is much cleaner:

1. Peek at the oldest Dog O(1).
2. Peek at the oldest Cat O(1).
3. Compare the two integers O(1).
4. Poll the winner O(1).

By using peek(), we look at the data without removing it. We only call poll() (which removes the element) once we are certain which animal is the global "oldest."

Time & Space Complexity

This is where the interview gets serious. You need to explain why this isn't the most efficient sort in the world, but why it's the best we can do under these rules.

Time Complexity

• enqueue(): O(1). We are simply adding to the end of a LinkedList and incrementing an integer.
• dequeueAny(): O(1). We are only looking at the heads of two lists.
• dequeueDog() / dequeueCat(): O(1). Standard queue removal.

Space Complexity

• O(N). We are storing N animals. Whether they are in one list or two, the total memory consumed is the same. We have a tiny bit of overhead for the order integer in each object, but it doesn't change the Big O classification.

Why This Problem Matters

You might think, "When am I ever going to be limited to just two stacks?"

The truth is, you probably won't be. But this problem isn't about stacks. It's about In-Place Processing and Data Integrity.

1. State Management: You have to keep track of two different "states" (a random pile and a sorted pile) and move data between them without losing a single integer.
2. Constraint Satisfaction: It forces you to stop reaching for the "easy" tools (like Collections.sort()) and understand how data actually moves in memory.
3. Buffer Logic: This "shuffling" between two containers is the foundation of many low-level data processing tasks, including how some database redo-logs and undo-logs manage transactions.

The Senior Perspective: Why This Matters

In 14 years of building systems, I’ve seen this pattern—The Multi-Queue Wrapper—countless times.

Imagine you are building a Priority Notification System.

• You have "Urgent" notifications and "Standard" notifications.
• You want to process "Urgent" ones first, but you also want to make sure "Standard" ones don't sit in the queue forever (Starvation).
• You might use a similar timestamping system to ensure that an "Urgent" notification sent 5 minutes ago doesn't wait behind a "Standard" one sent 1 second ago, or vice-versa depending on your business rules.

This problem isn't about dogs and cats. It's about Composition. It’s about taking two simple structures (LinkedLists) and wrapping them in a Manager class that provides a smarter interface.

Real-World Considerations (Beyond the Interview)

If this were a production system in 2026, we’d need to worry about:

1. Thread Safety: If two people adopt an animal at the same time, we need to synchronize the dequeue methods so the same dog isn't given to two people.
2. Persistence: What happens if the server restarts? Our order counter would reset to 0. In a real system, that counter and the lists would be backed by a database like PostgreSQL or Redis.
3. Scalability: If the shelter grows to millions of animals (unlikely for a physical shelter, but common for "digital assets"), we might need to shard the queues across different servers.

Final Thoughts

Problem 3.6 is a favorite of interviewers because it reveals how you think about data redundancy vs. data access. By "duplicating" the arrival time logic into two separate queues, we created a system that is incredibly fast for the user.

Most software engineering is exactly this: Finding the right way to organize data so that the most common operations are the cheapest.

Are you ready to implement this in your next project? Try adding a third animal type—say, "Rabbits"—and see how the dequeueAny logic scales. You’ll find that the "comparison" logic becomes a bit more complex, perhaps requiring a Min-Heap of the queue heads. But that's a story for another post.

I’ll see you in the next one.

Happy Coding.