/
AnimalShelter.java
124 lines (108 loc) · 3.89 KB
/
AnimalShelter.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package org.redquark.techinterview.ctci.stacksandqueues;
import java.util.LinkedList;
import java.util.Queue;
/**
* @author Anirudh Sharma
* <p>
* An animal shelter, which holds only dogs and cats, operates on a strictly"first in, first out" basis.
* <p>
* 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).
* <p>
* They cannot select which specific animal they would like.
* <p>
* Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny,
* dequeueDog, and dequeueCat.
* <p>
* You may use the built-in Linked List data structure.
*/
public class AnimalShelter {
public static void main(String[] args) {
AnimalQueue animals = new AnimalQueue();
// Create some objects and add them to shelter
Dog bruno = new Dog("dog");
animals.enqueue(bruno);
Dog oscar = new Dog("dog");
animals.enqueue(oscar);
Cat tiago = new Cat("cat");
animals.enqueue(tiago);
Cat lancelot = new Cat("cat");
animals.enqueue(lancelot);
Dog goofy = new Dog("dog");
animals.enqueue(goofy);
System.out.println("We are getting a: " + animals.dequeueAny().type);
System.out.println("We are getting a: " + animals.dequeueCat().type);
System.out.println("We are getting a: " + animals.dequeueDog().type);
System.out.println("We are getting a: " + animals.dequeueDog().type);
System.out.println("We are getting a: " + animals.dequeueCat().type);
}
static class AnimalQueue {
// List to store dogs
private final Queue<Dog> dogs = new LinkedList<>();
// List to store cats
private final Queue<Cat> cats = new LinkedList<>();
// Combined timestamp for each animal
private int timestamp = 0;
public void enqueue(Animal animal) {
// Set the timestamp for this animal
animal.setTimestamp(this.timestamp);
// Update timestamp
this.timestamp++;
// Add the animal to the respective list
if (animal instanceof Dog) {
dogs.add((Dog) animal);
} else if (animal instanceof Cat) {
cats.add((Cat) animal);
}
}
public Animal dequeueAny() {
// Look at both the lists and pop the oldest animal
if (dogs.isEmpty()) {
return dequeueCat();
} else if (cats.isEmpty()) {
return dequeueDog();
}
// Get the oldest element in both queues
Dog dog = dogs.peek();
Cat cat = cats.peek();
return dog.getTimestamp() < cat.getTimestamp() ? dequeueDog() : dequeueCat();
}
public Dog dequeueDog() {
if (dogs.isEmpty()) {
throw new RuntimeException("There are no dogs left");
}
return dogs.poll();
}
public Cat dequeueCat() {
if (cats.isEmpty()) {
throw new RuntimeException("There are no cats left");
}
return cats.poll();
}
}
static abstract class Animal {
// Type of the animal (e.g., dog, cat, etc.)
String type;
// Timestamp when the animal was brought into the shelter
private int timestamp;
Animal(String type) {
this.type = type;
}
public int getTimestamp() {
return this.timestamp;
}
public void setTimestamp(int timestamp) {
this.timestamp = timestamp;
}
}
static class Dog extends Animal {
Dog(String type) {
super(type);
}
}
static class Cat extends Animal {
Cat(String type) {
super(type);
}
}
}