Maintain streaming median and loosemedian

Q: Maintain streaming median and loosemedian

This question evaluates understanding of online streaming algorithms, running-median maintenance, and bit-level computations for identifying logarithmic intervals (the 'loose median').

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Design a data structure for an online stream of positive integers supporting insert (x). After each insertion, output: (a) the median of all values seen so far (for an even count, define the median as the average of the two middle values); and (b) the 'loose median' interval [2^k, 2^(k+ 1)] where k is the unique integer satisfying 2^k < median < 2^(k+ 1). Describe the algorithms and data structures, their time and space complexities, and how to implement bit operations to compute 2^k from the median. Discuss how you would handle boundary cases (e.g., median equals a power of two, zero/negative numbers, or non-integer medians).

Maintain streaming median and loosemedian

Overview

Comments (0)