Median in a Stream Problem Statement

Your task is to determine the median of integers as they are read from a data stream. The median is the middle value in the ordered list of numbers. If the list length is even, calculate the median as the floor of the average of the two central numbers.

Example:

Input:

[2,3,4], [2,3]

Output:

3, 2

Explanation:

For [2,3,4], the median is 3.
For [2,3], the median is floor((2+3)/2) = 2.

Input:

T
N
D₁, D₂, ..., D_N

Output:

print median after each new incoming element separated by space

Constraints:

1

Question

Median in a Stream Problem Statement

Your task is to determine the median of integers as they are read from a data stream. The median is the middle value in the ordered list of numbers. If the list length is even, calculate the median as the floor of the average of the two central numbers.

Example:

Input:

[2,3,4], [2,3]

Output:

3, 2

Explanation:

For [2,3,4], the median is 3.
For [2,3], the median is floor((2+3)/2) = 2.

Input:

T 
 N 
 D₁, D₂, ..., D_N

Output:

print median after each new incoming element separated by space

Constraints:

1 <= T <= 10
1 <= N <= 10⁴
0 <= data <= 10⁸
Time Limit: 1 sec

Note:

Return a vector of medians after each element is read from the stream for each test case.

Accepted Answer

Find median of integers in a data stream as they are read.

Use two heaps - max heap for lower half of numbers and min heap for upper half.
Keep the size of two heaps balanced to find the median efficiently.
Handle even and odd number of elements separately to calculate median.
Return vector of medians after each element is read from the stream.

Median in a Stream Problem Statement

Example:

Input:

Output:

Explanation:

Input:

Output:

Constraints:

Note:

Amazon SDE-2 interview questions & answers

Popular interview questions of SDE-2