Last Updated: 24 Feb, 2021
Find The Order In Which Pets Are Bought From The Pet Shop
Moderate
Asked in companies
The pet shop holds only dogs and cats. It operates on a “first-in, first-out” basis. People must adopt either the oldest of all animals in the shop or they can select whether they would prefer a dog or a cat but they cannot select which specific animal they would like. Each cat or dog that is bought into the shop is represented by a unique identification number.
There are two types of operations:-
1 ‘uID’ ‘type1’ - where 1 represents an animal is being brought into the shop. ‘uID’ represents a unique identification number allotted to the animal. ‘type1’ is 0 if animal is dog or 1 if animal is cat.
2 ‘type2’ - where 2 represents an animal is being adopted. ‘type2’ is 0 if the oldest dog is preferred. ‘type2’ is 1 if the oldest cat is preferred. ‘type2’ is 2 if either of them is preferred.
You have been given ‘n’ operations which you need to perform in the shop. Your task is to return a vector/list that contains the unique identification number of pets that are adopted in the order they are adopted.
Example :
Let's say the pet shop's oldest dog’s uID that has not yet been adopted is 4 and that of the oldest cat is 3.
If operation 2 0 is performed then the oldest dog will be adopted i.e uID 4.
If operation 2 1 is performed then the oldest cat will be adopted i.e uID 3.
If operation 2 2 is performed then the animal older among them will be adopted.
Input Format :
The first line contains a single integer ‘T' representing the number of test cases.
The first line of each test case contains a single integer ‘N’ representing the number of operations.
Next ‘N' lines contain operations that have to be performed on the shop. Each operation is either of type 1 or 2.
Output Format :
For each test case print a vector/list that contains the unique identification number of pets that are adopted in the order they are adopted.
Note :
1. All the operations are valid.
2. You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 1000
1 <= uID <= 10^6
0 <= type1 <= 1
0 <= type2 <= 2
Time Limit: 1sec
Approaches
We can maintain a list of pets in the order they arrive at the shop. The list must contain 3 parameters unique ID of each pet, whether the pet is a dog or cat, and whether it has been adopted or not.
We can declare a list ‘pets’ which contains all the above details. Declare a list ‘ans’ that is initially empty and stores the unique ID in the order in which they are adopted.
We perform each query as follows:-
- If the query is of type 1 then add the animal to the list with their unique ID, whether it is a dog or cat, and a check variable ‘adoption’ as false which implies it has not been adopted yet.
- If the query is of type 2 do as follows:-
- If a dog is preferred then iterate through the list of ‘pets’ check if it is a dog and then if the dog has not yet been adopted, update its variable ‘adoption’ to true as it will now be adopted. Push its unique ID into the list ‘ans’.
- If a cat is preferred then iterate through the list of ‘pets’ check if it is a cat and then if the cat has not yet been adopted, update its variable ‘adoption’ to true as it will now be adopted. Push its unique ID into the list ‘ans’.
- If either of them is preferred then iterate through the list of pets and find the oldest animal that has not yet been adopted. Update its variable ‘adoption’ to true as it will now be adopted. Push its unique ID into the list ‘ans’.
- After performing all the queries return ‘ans’.
We can maintain a list of pets in the order they arrive at the shop. The list must contain 3 parameters unique ID of each pet, whether the pet is dog or cat, and the position of the next dog in the list if this animal is a dog or the position of the next cat in the list if this animal is a cat.
We can declare a list ‘pets’ which contains all the above details. Declare a list ‘ans’ that is initially empty and stores the unique ID in the order in which they are adopted.
We will declare variables ‘firstCat’, ‘lastCat’, ‘firstDog’, and ‘lastDog’.
- ‘firstCat’- Stores position of the first cat in the list. Initially, we will initialize it as ‘n’+1 and update it when the first cat comes to the shop with the position of this cat in the list.
- ‘lastCat’ - Stores position of the last cat in the list. Initially, we will initialize it as ‘n’+1 and update it whenever the cat comes to the shop with the position of that cat in the list.
- ‘firstDog’- Stores position of the first dog in the list. Initially, we will initialize it as ‘n’+1 and update it when the first dog comes to the shop with the position of this dog in the list.
- ‘lastDog’ - Stores position of the last dog in the list. Initially, we will initialize it as ‘n’+1 and update it whenever the dog comes to the shop with the position of that dog in the list.
We perform each query as follows:-
- If the query is of type 1 then add the animal to the list with their unique ID, whether it is a dog or cat and:-
- If it is the first cat/dog in the list, initialize ‘firstCat’/‘firstDog’ with its position.
- Else first update ‘nextCat’/‘nextDog’ of the cat/dog that came into the list before it with the position of this cat/dog.
- Initialize ‘nextCat’/‘nextDog’ for current position with ‘n’+1
- Update ‘lastCat’/‘lastDog’ with the position of this cat/dog.
- If the query is of type 2 do as follows:-
- If a dog is preferred, push the unique ID of ‘firstDog’ to the list ‘ans’. Update ‘firstDog’ with ‘nextDog’ of the dog who was just adopted.
- If a cat is preferred, push the unique ID of ‘firstCat’ to the list ‘ans’. Update ‘firstCat’ with ‘nextCat’ of the cat who was just adopted
- If either of them is preferred then compare the position of ‘firstCat’ and ‘firstDog’.
- If ‘firstCat’ is smaller than ‘firstDog’, then push the unique ID of ‘firstCat’ to the list ‘ans’. Update ‘firstCat’ with ‘nextCat’ of the cat who was just adopted.
- Else push the unique ID of ‘firstDog’ to the list ‘ans’. Update ‘firstDog’ with ‘nextDog’ of the dog who was just adopted.
- After performing all the queries return ‘ans’.