Find The Order In Which Pets Are Bought From The Pet Shop

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
15 upvotes
Asked in companies
FacebookMicrosoftUber

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2
1 4 0
2 2    
6
1 2 0
1 1 0
1 3 1
2 1
2 0
2 2
Sample Output 1 :
4
3 2 1

Explanation Of Sample Output 1 :

Test case1:

Let’s say ith operation takes place at t=i. The status after each operation is as follows.
1 4 0 - A dog is brought into the shop with uID 4.
2 2 - A person comes to the shop and wants to adopt any animal. So, the oldest animal from the shop is given to him i.e dog with uID 4.

Therefore the order in which pets were adopted was 4.

Test case 2:

Let’s say ith operation takes place at t=i. Status after each operation is as follows.
1 2 0 - A dog is brought into the shop with uID 2.
1 1 0 - A dog is brought into the shop with uID 1.
1 3 1 - A cat is brought into the shop with uID 3.
2 1 - A person comes to the shop and wants to adopt a cat. So, the oldest cat from the shop is given to him i.e cat with uID 3.
2 0 - A person comes to the shop and wants to adopt a dog. So, the oldest dog from the shop is given to him i.e dog with uID 2.
2 2 - A person comes to the shop and wants to adopt any animal. So, the oldest animal from the shop is given to him i.e dog with uID 1.
Therefore the order in which pets were adopted was 3,2,1.

subsequence

Sample Input 2 :
2
4
1 1 1
1 3 0
2 1
2 0
8
1 1 0
1 2 1
1 3 0
1 4 1
2 2
2 2
2 1
2 2
Sample Output 2 :
1 3
1 2 4 3
Hint

Maintain an array/list to check if a pet has been adopted or not.

Approaches (2)
Storing Whether cat/dog Has Been Adopted Or Not.

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’.
Time Complexity

O(N^2), where ‘N’ denotes the number of operations.

 

For each operation of type 2, we need to traverse through the list of pets and find the oldest cat, dog, or animal which has not been adopted yet.

Space Complexity

O(N), where ‘N’ denotes the number of operations.

 

As we perform operations of type 2 we also need to maintain whether the pet has been already adopted or not.

Code Solution
(100% EXP penalty)
Find The Order In Which Pets Are Bought From The Pet Shop
Full screen
Console