I got an interview question asking for data structure and algorithm. The question is: Given we have unlimited space, We need to insert a key in $O(logn)$ and find a median in $O(logn)$. Min heap/ Max heap are good candidates to insert a key in $O(logn)$ but sorting requires $O(nlogn)$. How can we design a data structure so that it can find a median in $O(logn)$? The hint given by the interviewer is confused to me, the interviewer said we need two heaps. How can two heaps work?

  • 2
    $\begingroup$ You need max-heap for the first half and min-heap for the second half. Insert a new element into the correct heap; if heap sizes differ by more than 1, move a root of one heap into another heap. BTW, the most straightforward solution is to use binary search trees. If you augment the nodes with sizes (i.e. each node stores the number of nodes in its subtree), which are easy to maintain, then you can answer queries "return the $i$-th element" in $O(\log n)$ time. $\endgroup$ – Dmitry Aug 26 '20 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.