How to solve this Queue based question ??

Revision en6, by parv2809, 2021-01-30 16:02:57

We need to maintain a queue that is initially empty. We need to perform three types of operations on the queue:

- 1 X - add number X to the queue

- 2 0 - remove the least recently added number from the queue (basically from the front of the queue)

- 3 X - consider the current numbers in the queue and find the max size of a subset of numbers in the queue whose sum is X. If there is no such subset return -1.

A subset is defined as a sequence that can be obtained by removing some (possibly all) elements present in the queue.

input: a 2d array A containing the sequence of operations done on the queue.

~~~~~ Constraints-

1<=X<=350

|A|<=10^5

Tags #queue, #dynamic programing, #stack

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English parv2809 2021-01-30 16:02:57 2 Tiny change: ' 2d array containin' -> ' 2d array A containin'
en5 English parv2809 2021-01-30 16:00:53 0 (published)
en4 English parv2809 2021-01-30 15:59:45 13 Tiny change: 'X<=350\n\n\n|A|<=10^5\n\n\n\n~~~~~\n\n' -> 'X<=350\n\n|A|<=10^5\n\n\n'
en3 English parv2809 2021-01-30 15:59:08 48
en2 English parv2809 2021-01-30 15:57:31 136 Tiny change: 'traints-\n- 1<=X<=350\n- |A|<=10^5' -> 'traints-\n1<=X<=350 |A|<=10^5'
en1 English parv2809 2021-01-30 15:54:47 714 Initial revision (saved to drafts)