i recently participated in amazon SDE coding round and got the following question

Give a queue of N people numbered from 1 to N,where N is in front and are in order,

there are three type of queries

query 1: 1 X

remove the first person from the queue,(X represents any number,doesn’t matter for this query,consider X = 0)

query 2: 2 X

remove the person with value X from the queue(X is not the position it is the value)

query 3:3 X

print the position of person X in the current queue

input given is

n (number of people)

q (number of queries)

q lines of queries of above format

We have to output the sum of output of all query 3.

eg;

input

5

4

1 0

2 3

3 2

3 5

Output

4

explanation:

first there are 5 people {1,2,3,4,5},after first query we remove 1 from front

we remain with {2,3,4,5}

after 2’d query we remove person with value 3,so we now have {2,4,5}

after 3’rd query we ask for position of person with value 2 which is “1”

after 4’th query we ask for position of person with value 5 which is “3”

So final output is sum of all output of query of type 3: 1+3 = 4.

I was able to implement a sub-optimal answer but it failed for last two test cases with TLE, can someone tell me how this can be done, can figure out any algorithm.

PS: Simply deleting from the array doesn’t work.gives TLE.