Amazon coding round

Don’t cheat. You just deleted a comment which was a reply to Naman bhalla saying
" Yes and can be optimized by Lazy Propagation"
Don’t just remove it and say we are not on same page !
XD
PS: we can see edit history for 24 hours :joy:

2 Likes

Don’t waste your time here bro…these days discuss is not good for health.

1 Like

Yes that’s my bad and that is why I removed it. Sorry for that. But the comment that is not deleted I was talking about my own approach. :slightly_smiling_face:

1 Like

Yeah then you should have said that
“I replied to his comment by mistake and I was talking about my own approach not his”
Don’t just delete and say :joy::joy:
NVM no problem XD.

1 Like

Sorb1997 typing a long message :smile:
PS: my bad as well for replying to above message when you said “yes and can be optimized by Lazy”. I replied to message above it.

1 Like

There are plenty of beautiful solutions out here but most of them assume that N is iterable (ie. N <= 1e6). I am trying to propose a solution which should work for higher N.

Consider the deleted elements only and keep a record of them. In other words, we’ll maintain a set of deleted values and assume any value which is not present in the set is present in the queue.

With this approach,

  1. Deleting value X will take O(lg N) time (Just add X to the set).
  2. Finding Xth element will take O((lg N)^2) time (Binary search for the lowest value V such that
    V - the count of values less than V = X).

The average time complexities are slightly higher but I think it’s a fair tradeoff for such N.

8 Likes

:joy::joy::sweat_smile: \hspace{0mm} \hspace{0mm}

BIT + unordered map (No modifications on the map will be needed, if limits are small we can even use an array for the mapping). O(q log n). This is the most convenient implementation I can think of.

You mean something similar on the lines of this question? SPOJ.com - Problem ADALIST

Second part of this tutorial covers Implicit Treaps: Treaps : One Tree to Rule 'em all …!! Part-1

distance() takes O(n) time complexity. So this will give TLE.

Self balancing BST is not really required, as you can create the complete binary tree initially.

Just maintain the size of subtree in each node and perform modifications in O(log n) time.

Okay that was a generalized answer.
What you are asking to do is also balanced binary tree.
You need to make it complete. That is called balancing. If you start inserting elements in order 1 to n then it will be a linear tree.
And I said balanced because PBDS is inbuilt self balancing binary tree in c++ whereas I don’t know if we have an inbuilt library that makes complete binary tree. Do we have that ?
Why to implement code for making it complete binary tree ( code will be like build function of Segtree) when we have inbuilt self balancing binary tree ?
And if he uses self balancing here then it will help in many more ques as well.
Also self balancing is better as it will start reducing height of tree as soon as we remove elements. Where as simple binary tree won’t.

1 Like

The easiest and the most efficient one out there. Thank you.

I did the exact same thing, even binary search… But i still got TLE,maybe because instead of inserting in a set…i kept a list and kept inserting deleted elements into it a way to keep the list sorted(like insertion sort)… i guess that’s where i wen’t wrong… i can’t do anything to check if this would have worked, but i have a doubt.

how do i perform binary search on a set? set doesn’t allow random access as far as i know.

also if we use ordered set, won’t it take O(log n) for insertion, how O(1).

and isn’t set implemented like a balanced binary tree in cpp, Red-black tree as far as i remember… so basically the same approach as everyone else mentioned?

Yes, my mistake. Insertion will also take O(lg N) time.

I think C++ has something called ‘policy based’ data structure which can return the rank of a value in logarithmic time.

2 Likes

Yup that is one kind of balanced BST afaik.

lesson learnt, i was so close to the solution, all i had to do was use set instead of vector and i could have solved it :confused: and probably got an interview call! i wanted the interview experience atleast lol :slightly_smiling_face:

1 Like