Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Problems: Stacks & Queues

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

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.

👉 Link here to the repo to solve the problem

imagen

👌 Tips

We could consider keeping a single linked list for dogs and cats, and then iterating through it to find the first dog (or cat).What is the impact of doing this?

Let's suppose we kept separate lists for dogs and cats. How would we find the oldest animal of any type? Be creative!

Think about how you'd do it in real life.You have a list of dogs in chronological order and a list of cats in chronological order. What data would you need to find the oldest animal? How would you maintain this data?

👊 Solution 1

We could explore a variety of solutions to this problem. For instance, we could maintain a single queue. This would make dequeueAny easy, but dequeueDog and dequeueCat would require iteration through the queue to find the first dog or cat. This would increase the complexity of the solution and decrease the efficiency.

An alternative approach which is simple, clean and efficient is to simply use separate queues for dogs and cats, whilst maintaining an arrayList with the order.

The only negative trade off is that whenever you insert or remove you have to iterate through the order list prior dequeuing, which could take O(N).

public class AnimalShelter {
    private LinkedList<Animal> dogList = new LinkedList<>();
    private LinkedList<Animal> catList = new LinkedList<>();
    private ArrayList<Animal> order = new ArrayList<>();

    public void enqueue(Animal animal) {
        switch (animal.animalType) {
            case DOG:
                dogList.add(animal);
            case CAT:
                catList.add(animal);
            default:
                order.add(animal);
        }
    }

    public Animal dequeueDog() {
        Animal dog = dogList.removeFirst();
        order.remove(dog);
        return dog;
    }

    public Animal dequeueCat() {
        Animal cat = catList.removeFirst();
        order.remove(cat);
        return cat;
    }

    public Animal dequeueAny() {
        Animal animal = order.remove(0);

        switch (animal.animalType) {
            case DOG:
                dogList.remove(animal);
            case CAT:
                catList.remove(animal);
        }
        return animal;
    }
}
public class Animal {
    public AnimalType animalType;
    public String name;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Animal(AnimalType animalType, String name) {
        this.animalType = animalType;
        this.name = name;
    }

    public AnimalType getAnimalType() {
        return animalType;
    }

    public void setAnimalType(AnimalType animalType) {
        this.animalType = animalType;
    }
}
public enum AnimalType {
    CAT,
    DOG
}

Question borrowed from “Cracking the coding interview”

Last updated on 3/11/2020
← Sort StackPath Sum →
  • 👉 Link here to the repo to solve the problem
  • 👌 Tips
  • 👊 Solution 1
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr