Round 1
Questions: Implement a data structure which should support -
Insert(num) - should insert the num LooseMedian() - should return the loose median
LooseMedian is any value between the closest powers of 2 to the median. For example, if median is 7 then any value between 4 to 8 can be returned. Basically, LooseMedian can be => 2^k <= Median <= 2^(k+1); [2^k, 2^(k+1)]
Expected time and space complexity for insert and looseMedian was constant.
Candidate's Approach
I talked about brute force and then two heap solution with logn insertion and constant for loosemedian. However, the interviewer wasn’t satisfied with this and asked to optimize insertion to constant by exploiting the fact that loosemedian is 2^k <= median <= 2^k+1. I couldn’t come up with anything to optimize this.
Interviewer's Feedback
The interviewer was not satisfied with the initial approach and pushed for an optimization that would allow for constant time insertion.