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)).

Question

Cijo Thomas · Accepted Answer

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.

RohanD · Answer

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)

Sigiloso · Answer

We can use two heaps, one max heap, one min heap. Large values are pushed into the min heap, and small values are pushed into the max heap. Keep the difference of the number of elements in the two heaps smaller than 2. The median will be the top of the heap with more elements or the average of the tops of the two heaps if they have same number of elements. I think this is easier to implement.

Sigiloso · Answer

array?binary search when do insertion?

Sigiloso · Answer

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.

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas