Anish and Queues!

Hard
0/120
Average time to solve is 30m
profile
Contributed by
0 upvote
Asked in companies
IntuitAccolite

Problem statement

Anish is very sad due to the poor performance of India in WT20 and thus does not want to complete his data structures homework which says to implement N queues in a single array of length L. The queue number will be given on which the enqueue and dequeue operations will be given and you have to perform the operations on a single array of length L. Can you help him out?

Example:- 
Let, 

N = 5
L = 10
1 4 1 [ENQUEUE (4 ,1)]
1 3 1 [ENQUEUE (3 ,1)] 
2 1 [DEQUEUE(1)] 
2 2 2 [ENQUEUE(2,2)] 
2 2 [DEQUEUE(2)]

Answer:- [0, 0, 4, 0, 2] 
 (The first queue has 4 and 3 so 4 is dequeued out from queue 1 and queue 2 has integer 2 in it, so 2 is dequeued out from queue 2) .
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of each test case contains three integers ‘L’, ‘N’, and ‘Q’ denoting the number of queues to be implemented and the number of queries to be performed.

The next ‘Q’ lines of every test case contain 3 integers ‘A’, ‘B’, and ‘C’ denoting the type of operation, the queue number on which the operation is to be achieved, and the number to be enqueued if ‘T’ is 1.

The next ‘Q’ lines of every test case contain 2 integers ‘A’, and ‘B’ denoting the type of operation, and the queue number on which the operation is to be achieved.
Output Format : 
For each test case and for each query, print an integer denoting the number dequeued out if ‘A’ is 2 if there exists a number in the queue otherwise print -1. If ‘A’ is 1, if the enqueue operation is successful, print 0, otherwise print -1 if the queue is full.

The output of each test case should be printed in a separate line.
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 5
1 <= L <= 10^5
1 <= A <= 2
1 <= B <= N
1 <= C <= 10^9  

Time Limit: 1 sec
Sample Input 1 :
1
10 1 5
1 1 1
1 1 3
2 1
2 1
2 1
Sample Output 1 :
0
0
1
3
-1
Explanation for Sample Output 1 :
In the first two operations, the answer should be 0 because the enqueue operations are performed successfully. Then for the next two operations, the numbers 1 and 3 are dequeued out and they are printed. In the last operation, -1 is printed because the queue is already empty.
Sample Input 2 :
1
10 2 1
2 2
Sample Output 2 :
-1
Hint

Make equal divisions and perform normal operations on them.

Approaches (2)
Divide the array into equal sizes of N.

Approach:-

 

We can divide the full array into equal sizes of N and perform enqueue operations if the mentioned queue is not full and dequeue the first element if the queue is not empty.

 

Algorithm:-

 

 

  • Initialize an empty array named ANS to store all the answers.
  • Initialize an array name FRONT of length N with -1 to store the current front element of all the queues and REAR of length N with -1 to store the current rear element of all the queues.
  • Initialize a variable name FULL and update it with L divided by N
  • Iterate from 0 to Q. (Let’s say the iterator be i).
    • If A is equal to 1,
      • If FRONT[B] is -1 or FRONT[B] is equal to B*FULL+FULL-1, add -1 to the ANS.
      • Else
        • If FRONT[B] is -1, update FRONT[B] and REAR[B] to B*FULL-1 and update ARR[REAR[B]] to C.
        • Else, increment FRONT[B] by 1 and update ARR[REAR[B]] to C.
        • Add 0 to ANS.
    • Else,
      • If FRONT[B] is -1, update -1 to the answer.
      • Add ARR[FRONT[B]] to the answer and increment FRONT[B] by 1.
      • If FRONT[B] is greater than REAR[B], update FRONT[B] and REAR[B] to -1.
  • Return ANS.
Time Complexity

O(Q), where Q is the number of queries

Each query takes constant time, so for Q queries the total time complexity is O(Q).

Space Complexity

O(Q),

We are using an auxiliary array to store the current front and rear queues of all the queues, so the space complexity is O(Q).

Code Solution
(100% EXP penalty)
Anish and Queues!
Full screen
Console