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.
4 Likes
Maybe self balancing binary tree works here 
Check it on Google or geeksforgeeks. Along with map or something.
1 Like
Its a standard implicit treap problem :+)
5 Likes
can you provide a good tutorial for it, i did read on it but am still confused to implement this problem.
1 Like
sikander the solution:
when query(3 X) how many numbers below it have been removed count them and minus it from the X and sum it
the code i built is working with this logic no need to search the array and its location
where did u give amazon sde coding round
Any link to learn it would be helpful
I think this can be easily solved using Segment Trees for O( log N ) per query. As all numbers are in range 1 to N and in sequence (You haven’t mentioned range of N but if it is till 1e6, Seg Tree should work fine). Segment Tree will store number of values in range l, r currently in our queue. Initially in range 1 -> N, there will be N values obviously.
Type 1: Traverse the segment tree and find the first present value. For a range l to r, if l == r, just set it 0, else if number of values in range l -> mid > 1, go left, else go right.
Type 2: For range l -> r, if x lies in l -> mid, go left. Else go right and when l == r, just set it 0.
Type 3: Just find number of people in range (1, x)
did the same still got TLE
I haven’t tested this but I think it should work.
Please Let me know if it doesn’t.
Let \Delta x be the change in position of a person x’s rank.
We store this in an array for all the 1…n persons.
Initially ofcourse \Delta x is 0 for all of them.
For type 1 query at some point Whatever active i…n range is remaining at that point for that range \Delta x will be reduced by 1. so for range i+1…n update by reducing 1 from all.
For type 2 query at person j the \Delta x for a person before j won’t change. And for people after j it will be reduced by 1. that is for j+1 … n update by reducing 1 from \Delta x
And answer to the 3rd query for a person i is just i - \Delta x . Since i is initial position and \Delta x is the reduced position.
Also, we don’t have to handle unnecessary deletions as we won’t be querying a person not in the queue.
All of this can be done using a segment tree quite easily.
1 Like
Lazy Propagation Segment Tree should work, I guess. 
Update:
I think this approach should work- While deleting an element at index i, increment the count of every element in the range [i+1, R], this can also be generalized to Query 1, where you are removing the first person from the queue. Effectively deleting the element at index 0. If you use a regular Segment Tree then the update operation would take O(N) time but this can be optimised to log(N) if you use Lazy Propagation on Segment Tree.
What ? how O(n) ?
I think idea given by @naman_bhalla is O(log(n)).
No need of lazy propagation here.
Basically for query one he is going to left child only if there are more than 0 numbers in left child.
So go to leftmost child having non zero number of elements. hence its O(log(n)).
Instead of all these complex Seg tree solutions, can’t we just use a C++ set? Set elements always remain ordered due to balanced b tree.
Push all elements from 1 to N.
For 1, erase(s.cbegin) = average O(1)
For 2, erase(b) = average O(1)
For 3, sum+=distance(s.begin, s.find(k))+1 = O(n)
Is this not feasible?
There is no need to go for segment trees. We can implement all the three operations in 0(1) time by using the Doubly linked list implementation of queue and storing the value and its corresponding address in a Hashamap
Type1: Just remove the first element in the doubly linked list
Type2: Remove the element X by finding it’s address by using HashMap and then remove that element from the hashmap as well.
Type3: In order to return the position of the value, then subtract the address of the front from the address of the value X.
The above three operations take 0(1) time if we implement this using a doubly linked list and a HashMap.
This implementation gave TLE.
A simple approach would be to treat all the type 1 queries as range update query i.e.Decrement by 1 all the indexes from 1 to n.
All queries of type 2 x is decrementing all cells from x to n by 1.
Then…type 3 queries can easily be answered by just printing the value @ index x.
You can also use Lazy propagation technique to update, in which case all the type 3 queries will have to be answered considered as Offline queries.
2 Likes
When you say address, do you mean the address in literal terms(their address in the Heap)? If that is the case then I don’t think it is going to work. Allocation in Heap is not guaranteed to be in a continuous sequence.
Sorry I don’t get you, may be we are not on the same page. I wasn’t talking about @naman_bhalla 's approach in my previous comment. I was talking about my own approach. The way it works is that you update the position of each element in the range[i+1, R] by decrementing it’s current value by 1. Ofcourse there will be some elements whose values need not be updated as they are already removed(but that’s fine as we are not going to query them again).
May be I am wrong but if we do all updates in the range [i+1, R], are they not O(N) unless we are doing a Lazy Propagation?
Exactly what I talked about and correct me if I am wrong but if you follow this approach then you must do a Lazy Propagation, am I right?
Hi, I dont really believe you need any data structure except for an array of size n or a LL or if in python a list.
The approach would be
1)Keep a start variable initialized with 1.
2) For each query of type 1, increment start with 1
3) For each query of type 2, append that number to the array.
4) For query of type 3
Read the number
Index =0
For I in range(start,end):
If(I in ar):
continue
Else:
Index+=1
If(index==num):
Break
Do the rest. This is the best solution i can think of. Sorry for poor editing, typing in mobile. Hope this helps