Microsoft

www.microsoft.com
www.microsoft.com
Work in HR? Unlock Free Profile

## Interview Question

Software Development Engineer Interview(Student Candidate) Mountain View, CA

# Create a data structure that minimizes time complexity of

retrieving median and inserting new element. Getting median should be O(1) and insertion should be O(log(n)).
Tags:

0

A heap in which the root is the median and it has max heap of the lower half on left and min heap of the rest on right.

Interview Candidate on Jul 13, 2012
4

Can we not use a BST which is kept balance after every insertion using AVL ? The median is always the root of this tree, so median is retrieved in O(1) and insertion/deletion is O(log n) for balanced tree.

Cijo Thomas on Oct 28, 2012
0

I guess a Red-Black tree would be a more appropriate data structure to use. Since it is a perfectly balanced tree data structure, the median would always be at the root. The insertion takes time proportional to the height of the tree i.e. O(logn)

RohanD on Mar 2, 2013