Overview

The InterviewStreet Median Challenge is a programming problem that tests a candidate's ability to calculate the median of a dynamic set of numbers efficiently. This challenge is a common feature in technical interviews, as it assesses both algorithmic thinking and data structure management.

Problem Description

The challenge involves processing a sequence of integers. For each number added to the sequence, you are required to output the median of the current sequence.

Given the nature of the problem, it requires not only understanding the definition of median but also devising an efficient algorithm to compute it as numbers are added one by one.

Definition of Median

The median is a fundamental statistical measure that represents the middle value of a data set:

• For a set with an odd number of elements, the median is the middle element when sorted.
• For a set with an even number of elements, the median is the average of the two middle elements when sorted.

For example:

• In the list [1, 3, 3, 6, 7, 8, 9] , the median is 6 .
• In the list [1, 2, 3, 4, 5, 6, 8, 9] , the middle elements are 4 and 5 , so the median is (4 + 5) / 2 = 4.5 .

Technical Explanation

Naive Approach

A naive solution to this problem would involve inserting each number into a list and then sorting the list to find the median after each insertion. While this approach is straightforward, it is inefficient. The sorting step has a time complexity of $O(n \log n)$, which makes this approach infeasible for a large number of updates.

Efficient Approach Using Heaps

A more efficient approach involves using two heaps (priority queues):

1. Max-Heap: To store the first half of the numbers, allowing access to the maximum of the lower half.
2. Min-Heap: To store the second half of the numbers, allowing access to the minimum of the upper half.

Algorithm

• When a new number x is added:
  • Compare x to the max element of the Max-Heap (let's call it max_l ):
    • If x <= max_l , insert x into the Max-Heap.
    • Else, insert x into the Min-Heap.
• Balance the heaps:
  • If the size of the Max-Heap is greater than one more than the size of the Min-Heap, move the root of the Max-Heap to the Min-Heap.
  • If the size of the Min-Heap is greater than the size of the Max-Heap, move the root of the Min-Heap to the Max-Heap.
• The median is:
  • The root of the Max-Heap if it has more elements.
  • The root of the Min-Heap if both heaps are of equal size, the median is the average of both roots.

Example

Consider the sequence: [6, 10, 2, 4, 3, 8, 7]

Complexity Analysis

Using heaps results in operations that can be executed in logarithmic time with respect to the number of elements, leading to the following complexities:

• Time Complexity: $O(\log n)$ for each insertion and balancing operation.
• Space Complexity: $O(n)$ for storing the elements in the two heaps.

Conclusion

The InterviewStreet Median Challenge is an excellent test of one's ability to handle dynamic data using sophisticated data structures. By leveraging Max and Min Heaps, one can efficiently compute the median in a stream of numbers with an optimal time complexity, thereby making this approach highly scalable and suitable for real-world applications where latency and performance are critical factors.