Last Updated: 4 Nov, 2021

Anish and Queues!

Hard

Asked in companies

Solve now

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) .

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

We can store the front and rear element of every queue and every next free index of every index so that we can process the queries in a constant time.

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 front element index of all the queues.
Initialize an array name REAR of length N with -1 to store the rear element index of all the queues.
Initialize an array NEXT of length N with NEXT[i] initialized as i + 1.
Initialize a variable named FREE with 0 to store the free index in ARR.
Iterate from 0 to Q. (Let’s say the iterator be i).
- If A is equal to 1,
  - If FREE is -1, add -1 to ANS.
  - Else,
    - Update N_FREE as NEXT[FREE].
    - If FRONT[B] is equal to -1,
      - Update FRONT[B] and REAR[B] to FREE.
    - Else,
      - Update NEXT[REAR[B]] to FREE.
      - Update REAR[B] to FREE.
    - Update NEXT[FREE] to -1.
    - Update ARR[FREE] to C.
    - Update FREE to N_FREE.
    - Add 0 to ANS.
- Else,
  - If FRONT[B] is equal to -1, add -1 to ANS.
  - Update F_INDEX as FRONT[B].
  - Update FRONT[B] as NEXT[F_INDEX].
  - Update NEXT[F_INDEX] as FREE.
  - Update FREE as F_INDEX.
  - Add ARR[F_INDEX] to ANS.

Solve now