4
\$\begingroup\$

Well known problem:

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 cat (and will receive oldest of that type). They cannot select which specific animal they would like. Create the data structure to maintain this system and implement operations such as enqueue, dequeueAny, dequeDog, and dequeCat. You may use the built-in linked list data structure.

It took me 2 hours to implement (reading problem to coding), which for 12 years exp is a lot. Basically I got messed up in my head while choosing proper interface which I changed two times (hence the time).

I think If I thought about correct interface at first instance before starting to code it should've been 30 mins code at the max. And only way to know for sure about that is to let one of you optimize it in c++. What and how would you optimize it? E.g. is dog cat and animal class ok? dequeueCat() dequeue() et.al. signature look awful.

#include <iostream>
#include <string>
#include <list>
#include <cassert>

enum class shout
{
  unknown,
  bark,
  purr
};

struct animal
{
  animal(std::string n = std::string(), shout t = shout::unknown) : name(n), shoutingTraits(t) {}

  // properties
  std::string name;
  shout shoutingTraits;
};

struct dog : public animal
{
  dog(std::string n = std::string()) : animal(n, shout::bark) {}
};

struct cat : public animal
{
  cat(std::string n = std::string()) : animal(n,shout::purr) {}
};

class adopt;
std::ostream& operator<<(std::ostream& out, const adopt& center);

class adopt
{
  public:
  bool enqueue(const animal& animal)
  {
    if(animal.shoutingTraits == shout::unknown) {
      throw std::runtime_error("only dogs and cats accepted");
    }
    animals.push_back(animal);
    return true; //implement size restrictions
  }

  bool dequeOldestTrait(shout trait, animal& a)
  {
    assert(trait != shout::unknown);

    for(std::list<animal>::iterator it = animals.begin() ; it != animals.end() ; it++) {
      if(it->shoutingTraits == trait) {
        a = *it;
        animals.erase(it);
        return true;
      }
    }
    return false;
  }

  bool dequeAnimal(animal& a, shout trait = shout::unknown)
  {
    if(animals.empty()) {
      throw std::runtime_error("Sheleter not opened yet");
    }
    if(trait == shout::unknown){
      a = animals.front();
      animals.pop_front();
      return true;
    }
    return dequeOldestTrait(trait, a);
  }

  bool dequeDog(dog& dog) //reference to derived type
  {
     return dequeAnimal(dog, shout::bark);
  }

  bool dequeCat(cat& cat)
  {
     return dequeAnimal(cat, shout::purr);
  }

  friend std::ostream& operator<<(std::ostream& out, const adopt& center);

  private:
  std::list<animal> animals;
};

std::ostream& operator<<(std::ostream& out, const adopt& center)
{
  out << "Adoption Center animals queue => ";
  for(auto a : center.animals) {
    out << "(" << a.name << ","<< (int)a.shoutingTraits << "), ";
  }
  out << std::endl;
  return out;
}

void createCenter(adopt& adoptionCenter)
{
  dog d0("dog0");
  dog d1("dog1");
  dog d2("dog2");
  dog d3("dog3");
  dog d4("dog4");
  dog d5("dog5");

  cat c0("cat0");
  cat c1("cat1");
  cat c2("cat2");
  cat c3("cat3");
  cat c4("cat4");
  cat c5("cat5");


  adoptionCenter.enqueue(d0);

  adoptionCenter.enqueue(c1);
  adoptionCenter.enqueue(c0);

  adoptionCenter.enqueue(d3);
  adoptionCenter.enqueue(d4);

  adoptionCenter.enqueue(c5);

  adoptionCenter.enqueue(d1);

  adoptionCenter.enqueue(c3);

  adoptionCenter.enqueue(d2);

  adoptionCenter.enqueue(c4);
  adoptionCenter.enqueue(c2);

  adoptionCenter.enqueue(d5);

  std::cout << adoptionCenter;
}

void unitTests(adopt& adoptionCenter)
{
  std::cout << "\nRemoving dog (d0 should be removed)" << std::endl;
  dog tmp;
  if(!adoptionCenter.dequeDog(tmp)) {
    std::cout << "dog removal failed" <<std::endl;
  }
  std::cout << adoptionCenter;


  std::cout << "\nRemoving one more dog (d3 should be removed)" << std::endl;
  if(!adoptionCenter.dequeDog(tmp)) {
    std::cout << "dog removal failed" <<std::endl;
  }
  std::cout << adoptionCenter;

  std::cout << "\nRemoving cat (c1 should be removed)" << std::endl;
  cat tCat;
  if(!adoptionCenter.dequeCat(tCat)) {
    std::cout << "cat removal failed" <<std::endl;
  }
  std::cout << adoptionCenter;


  std::cout << "\nRemoving other cat (c0 should be removed)" << std::endl;
  if(!adoptionCenter.dequeCat(tCat)) {
    std::cout << "cat removal failed" <<std::endl;
  }
  std::cout << adoptionCenter;
}

int main()
{
  adopt adoptionCenter;

  std::cout << "AdoptionCenter should be empty" << std::endl;
  std::cout << adoptionCenter;
  std::cout << "Removing on empty queue" << std::endl;
  animal a;
  try {
    std::cout << adoptionCenter.dequeAnimal(a) << std::endl;
  } catch (const std::runtime_error& e) {
    std::cout << e.what() << std::endl;
  }

  createCenter(adoptionCenter);

  unitTests(adoptionCenter);

  return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I believe the easy route here will be maintaining two queues, and on dequeueAny return something like std::variant, but to simplify you could just supply animal_cast<>, so that when people will try accessing wrong type of animal, they will get exception. \$\endgroup\$ – Incomputable Sep 5 '17 at 3:04
  • \$\begingroup\$ @Incomputable: Two queues won't work: Is the dog or the cat the longer-term-tenant`? \$\endgroup\$ – Deduplicator Sep 5 '17 at 11:00
  • \$\begingroup\$ @Deduplicator, it would be possible to use a bool or enum flag to differentiate on the longest arendator. So, when performing a dequeue, it would be if (last_pet == pets::dog && !sheltered_dogs.empty()). \$\endgroup\$ – Incomputable Sep 5 '17 at 13:30
3
\$\begingroup\$

Wrong type identifier

A barking animal is not a dog. With regard to how you built the Cat and Dog, you are using the abstraction "something that barks is a dog" and "something that purrs" is a cat. That would not really be sufficient, deriving from your classes I could smuggle a purring Leopard into the adoption agency that would be handed out to the clients instead of a cat. Yes it's a made up case but basically this is 'duck typing' in the wrong place.

While this is a small somewhat contrived example i think it is important to understand what you modeled here. Right somebody could write something like this

Animal dogimal("dogimal", bark);

In this context I would interpret this as not a dog, but animal that barks. It's a small difference that could be important once the animal interface grows. Had you not subclassed this would probably not have been as much as an issue to me. Again with the scope of the example this would be ok.

For example you could make the animal constructor protected, this would only let subclasses call it. This would also entail having to change the type from struct to class. For a more complex class making it virtual would also be an option.

Wrong classname

adopt is a verb, this should be something like adoptionAgency or another suitable noun

Modern C++

In dequeOldestTrait i would have liked to have seen the use of std::find_if rather than an explicit for loop.

Unit tests

The unit tests only check whether the correct animal type has been removed, they don't check if the actual animal e.g. d0 was correctly returned. The unit tests don't check for edge cases, empty shelter, animal type not available

Inconsistent interface

There is a mix between failures represented as bool results and exceptions (empty shelter, only dogs and cats are accepted vs animal not found). For this scenario that is probably an unnecessary differentiation. Bools would be good enough for all of these cases. Additionally you return an unconditional true in the enqueue method.

Outputs magic number

The << method for adopt write out ints for the noise that the animals make, that is really not helpful for most people.

Notes

The dequeDog signature that you noted doesn't look bad, you are returning bool for success or failure and using a reference as an ouput parameter. I probably would have liked to have seen methods for checking on the state of the adoption agency, isEmpty(), size() hasDogs(), hasCats() for completeness. In the interview I would have asked you what you would add to your class to make it easier to use. Depending on the time that we have and how the interview was set up i might have asked where and why you got hung up and how you figured out which direction to take. I might ask you what would change in behavior if you'd use an array as a backing structure and why one would prefer one over the other. These days one followup question would always be on thread safety and how to achieve it.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Important question that I alluded to was what would better data structure for this problem look like? animal and derived cat dog classes required? or just animal would've been better? or only cat and dog \$\endgroup\$ – PnotNP Sep 5 '17 at 23:39
  • \$\begingroup\$ @NulledPointer I extended the explanation a bit, polymorphism (using cat and dog as animal) is a valid solution to what you where trying to do. But I would consider the fact that misuse was not prevented as a problem. \$\endgroup\$ – Harald Scheirich Sep 6 '17 at 2:00
1
\$\begingroup\$

Classes vs. Simpler Types

My first question when looking at this code is why are there classes for animal, cat, and dog? If the point is to show polymorphism, then it's fine, but I don't see mention of that in the problem description. It seems like you needed to add extra data (shoutTraits) just to justify having the classes. If I were implementing something like this, I'd probably make an enumerated type for the animals unless there was some reason not to. Something like:

typedef enum animal_t {
    none = 0,
    cat,
    dog
} animal_t;

Or maybe a class that contains an animal_t and a name, as you have.

Error Handling

Your enqueue() method throws an exception if it gets an unknown type of animal. Your dequeueOldestTrait() method asserts that the trait is not unknown. It also can return false if no animal with the desired trait is found. dequeueAnimal() throws if the shelter is empty.

None of these things is bad by itself, but it feels inconsistent. If enqueue throws on an unknown trait, it seems like dequeueOldestTrait should as well. Alternately, maybe a bool isn't enough for a return value in dequeueAnimal? Maybe the caller would like to distinguish between an empty shelter and an open shelter that has no cats/dogs. Doing that currently would require having one case handled in a try/catch block, and the other handled by checking the return value. It would be nice to be able to handle those 2 cases consistently.

If I were an interviewer, I would ask why you chose to return an exception in one case and an error in the other case. There are different philosophies on when to use each. (Some say a normal situation like an incorrect password is an error message, but not being able to connect to the database to check a user's password would be an exception, for example. Others say to always use error codes, while still others say always exceptions. So long as you have an answer you can explain, an interviewer will be more impressed than if you don't.)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I think, it was deliberate effort to impress interviewer with polymorphism rather than solving the problem, agree with the enum animal_t type. For exception vs error, my philosophy matches your former statement. \$\endgroup\$ – PnotNP Sep 6 '17 at 5:27

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.