Queue Removals

Straight to the Point !

Are you landed to this page and rushing for the immediate solution in javascript. here you go !!

Step 1: goes_here
Step 2: goes_here
Step 3: goes_here

1Code Solution Goes here.

On High level note, It worth to read in detail for a better understanding. This is one of the Facebook interview question and Leet code problem as well - 1460. leetCodetitle

Problem Statement
Constraints
Expected
Test Cases
Foot Note
Solution Intro
Solutions
Other Possible Questions

Problem Statement

You're given a list of n integers arr, which represent elements in a queue (in order from front to back). You're also given an integer x, and must perform x iterations of the following 3-step process: a list of n integers arr, which represent elements in a queue (in order from front to back). You're also given an integer x, and must perform x iterations of the following 3-step process:

Pop x elements from the front of queue (or, if it contains fewer than x elements, pop all of them)
Of the elements that were popped, find the one with the largest value (if there are multiple such elements, take the one which had been popped the earliest), and remove it
For each one of the remaining elements that were popped (in the order they had been popped), decrement its value by 1 if it's positive (otherwise, if its value is 0, then it's left unchanged), and then add it back to the queue

Compute a list of x integers output, the ith of which is the 1-based index in the original array of the element which had been removed in step 2 during the ith iteration.

1int[] findPositions(int[] arr, int x)

Constraints

x is in the range [1, 316].
n is in the range [x, x*x].
Each value arr[i] is in the range [1, x].

Expected

Return a list of x integers output, as described above.

Test Cases

n = 6, arr = [1, 2, 2, 3, 4, 5], x = 5 so output = [5, 6, 4, 1, 2]
n = 13, arr = [2, 4, 2, 4, 3, 1, 2, 2, 3, 4, 3, 4, 4], x = 4 so output = [2, 5, 10, 13]

Foot Note

The initial queue is [1, 2, 2, 3, 4, 5] (from front to back).

In the first iteration, the first 5 elements are popped off the queue, leaving just [5]. Of the popped elements, the largest one is the 4, which was at index 5 in the original array. The remaining elements are then decremented and added back onto the queue, whose contents are then [5, 0, 1, 1, 2].
In the second iteration, all 5 elements are popped off the queue. The largest one is the 5, which was at index 6 in the original array. The remaining elements are then decremented (aside from the 0) and added back onto the queue, whose contents are then [0, 0, 0, 1].
In the third iteration, all 4 elements are popped off the queue. The largest one is the 1, which had the initial value of 3 at index 4 in the original array. The remaining elements are added back onto the queue, whose contents are then [0, 0, 0].
In the fourth iteration, all 3 elements are popped off the queue. Since they all have an equal value, we remove the one that was popped first, which had the initial value of 1 at index 1 in the original array. The remaining elements are added back onto the queue, whose contents are then [0, 0].
In the final iteration, both elements are popped off the queue. We remove the one that was popped first, which had the initial value of 2 at index 2 in the original array.