Interview Experience 112 (Intern)

2018

Software Developer Engineer Intern

Coding Round -

• You will be given q queries. q is of the range 10^6. Each query can be one of the following three types:

1. x: Insert x into a DS.
2. y: Delete y from the DS if present.
3. Output the median of all the elements present in the DS. If there are two medians then take the average of the two.

Expected complexity: qlogn or q(logn)^2.

• How multiset is implemented in STL.