Special Queue

Moderate
0/80
4 upvotes
Asked in companies
AmazonD.E.Shaw

Problem statement

Your task is to design a special type of Queue having three positions front, middle, and back to push or pop the element. You have to define a class having the following functions:

1. SPECIAL_QUEUE() is a function that initializes your queue.

2. PUSH_FRONT(VAL) inserts the VAL in the front of the queue.

3. PUSH_BACK(VAL) inserts the VAL at the back of the queue.

4. PUSH_MIDDLE(VAL) inserts the VAL at the middle position of the queue.

5. POP_FRONT(VAL) removes the first element from the queue and returns the value of the removed element.

6. POP_BACK(VAL) removes the last element from the queue and returns the value of the removed element.

7. POP_MIDDLE(VAL) removes the middle element from the queue and returns the value of the removed element.

Note:

If the queue is empty and any type of ‘POP’ function is called, return -1.
If there are two middle positions available, operate on the position close to the front of the queue.
For Example 
If the functions calls are as follows:
‘PUSH_FRONT’(10).
‘PUSH_FRONT’(20)’.
‘PUSH_MIDDLE’(30)
‘POP_BACK’().
 So after each operation queue will changes like [ ] -> [10] -> [20, 10] -> [20, 30, 10] ->[20,30].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, 'N’, denoting the number of function calls.

The second line contains a list of ‘N’ function names.

The third line of each test case contains ‘N’ integers denoting the parameters passed in each function call. (Parameter value corresponding to  any pop() function is -1.)
Output Format: 
For each test case, output the value of the popped element for each pop() function call in a separate line.
For push() function ,do not print anything.  

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10000.
0 <= ‘VAL’ <= 10^6 .  

Time limit: 1 sec
Sample Input 1:
2
4
pushFront pushFront pushMiddle popBack
10 20 30 -1
4
pushMiddle pushMiddle popFront popFront 
10 100 -1 -1
Sample Output 1:
10
100
10
Explanation of sample input 1:
For the first test case,
Initially, the queue is empty.[]
pushFront(10) ,the queue will be become [10].
pushFront(20) ,the queue will be become [20, 10].
pushMiddle(30) ,the queue will be become [20, 30, 10].
popFront() ,the queue will be become [20,30].10 will be popped out and will be printed.

Hence, 10 will be printed.

For the second test case:
Initially, the queue is empty.[]
pushMiddle(10) ,the queue will be become [10].
pushMiddle(100) ,the queue will be become [100, 10].
popFront(), the queue will be become [10].100 will be popped out and will be printed.
popFront(), the queue will be become [ ].10 will be popped out and will be printed.


Hence, 100 and 10 will be printed.
Sample Input 2:
2
6
pushBack pushBack pushBack popMiddle popMiddle popMiddle
10 20 30 -1 -1 -1
3
popBack pushMiddle popFront
-1 100 -1
Sample Output 2:
20
10
30
-1
100
Hint

Try to implement the special queue using a dynamic array.

Approaches (3)
Brute Force

In this approach, we will implement this special queue using a  simple dynamic array.

In push functions, we will shift the elements of the array and insert the new element.

In pop functions, we will remove the element from the specified position and update the array.

In these functions, we will use additional space to change the array according to the function.  


 

Algorithm:

  • Defining SPECIAL_QUEUE():
    • Declare a dynamic array ‘ARR’.
  • Defining PUSH_BACK(‘VAL’):
    • Append ‘VAL’ to the end of the ‘ARR’.
  • Defining PUSH_FRONT(‘VAL’):
    • Declare an array ‘TEMP’.
    • Insert ‘VAL’ into the ‘TEMP’.
    • For each element ‘i’ in the array ‘ARR’, do the following:
      • Insert ‘i’ into ‘TEMP’.
    • Set ‘ARR’ as ‘TEMP’.
  • Defining PUSH_MIDDLE(‘VAL’):
    • Declare an array ‘TEMP’.
    • Set ‘i’ as 0.
    • Set ‘j’ as  0.
    • Set ‘IDX’ as (length of ‘ARR’) / 2 . (Index where ‘VAL’ should be inserted.)
    • While ‘j’ is less than (length of ‘ARR’ +1):
      • If ‘j’ is equal to ‘IDX’:
        • Insert ‘VAL’ into ‘TEMP’.
      • Else:
        • Insert ‘ARR’[i] into ‘TEMP’.
        • Set ‘i’ as ‘i+1’.
      • Set ‘j’ as j+1.
    • Set ‘ARR’  as ‘TEMP’.
  • Defining POP_BACK():
    • If the length of ‘ARR’ is equal to 0, return -1.
    • Set ‘V’ as ‘ARR’[length of ‘ARR’ - 1].
    • Remove the last element from array ‘ARR’.
    • Return ‘V’.
  • Defining POP_FRONT()
    • If the length of ‘ARR’ is equal to 0, return -1.
    • Set ‘V’ as ‘ARR’[0].
    • Declare an array ‘TEMP’.
    • For i in range(1,length of ‘ARR’ -1 ):
      • Insert ‘ARR’[i] into  ‘TEMP’.
    • Set ‘ARR’ as ‘TEMP’
    • Return ‘V’.
  • Defining POP_MIDDLE()
    • If the length of ‘ARR’ is equal to 0, return -1.
    • Set ‘IDX’ as (length of ‘ARR’) / 2,if the length is odd. (Index from where the element should be removed).
    • Set ‘IDX’ as ( (length of ‘ARR’) / 2) -1,if the length is even.
    • Set ‘V’ as ‘ARR’[IDX].
    • Declare an array ‘TEMP’.
    • For i in range(0,length of ‘ARR’ -1 ):
      • If i is equal to ‘IDX’:
        • Continue.
      • Insert ‘ARR’[i] into  ‘TEMP’.
    • Set ‘ARR’ as ‘TEMP’
    • Return ‘V’.
Time Complexity

O(N *M), where ‘N’ is the maximum length of ‘QUEUE’ and ‘M’ is the number of functions calls.

 

In this approach, all functions are using O(N) time to copy the elements from the previous array. Hence the overall time complexity is O(N*M).

Space Complexity

O(N), where ‘N’ is the maximum length of ‘QUEUE’.

 

In this approach, almost all functions are using O(N) extra space to copy them and update queue array ‘ARR’.Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Special Queue
Full screen
Console