How do you find the median of a large dataset?

When tasked with finding the median of a large dataset, especially in a technical interview for a FAANG company, it's crucial to demonstrate both your understanding of the problem and the efficiency of your solution. The median is the middle value in a dataset when it is ordered. If the dataset is large, or cannot fit entirely into memory, we need to consider efficient algorithms and data structures to find the median without sorting the entire dataset.

1. Streaming Algorithm Approach:
   • For very large datasets that cannot fit into memory, you can use a streaming algorithm with two heaps (or priority queues) to keep track of the median efficiently.
   • Use a max-heap to store the lower half of the numbers and a min-heap to store the upper half.
   • Ensure that the heaps are balanced in size (or off by one if odd number of elements).
   • The median will be the root of the max-heap if the total number of elements is odd, or the average of the roots of both heaps if even.

Key Talking Points:

• Efficiently find the median without sorting the entire dataset.
• Use a two-heap approach for real-time or streaming data.
• Balance the heaps to ensure correct median calculation.

NOTES:

Reference Table:

Pseudocode:

import heapq

class MedianFinder:
    def __init__(self):
        self.min_heap = []  # For the larger half
        self.max_heap = []  # For the smaller half

    def add_num(self, num):
        heapq.heappush(self.max_heap, -num)
        heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))

        if len(self.max_heap) < len(self.min_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def find_median(self):
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        else:
            return (-self.max_heap[0] + self.min_heap[0]) / 2

Follow-Up Questions and Answers:

1. What if the data stream is continuous and potentially unbounded?

   • Answer: The two-heap solution is particularly well-suited for continuous data streams since it allows for efficient insertion and median retrieval without needing the entire dataset in memory.

2. How would you handle the situation if the dataset is distributed across multiple machines?

   • Answer: You could use a distributed approach where each machine computes a local median, and then these local medians are aggregated to determine the global median. Techniques such as MapReduce can be employed to facilitate this process.

3. Could you optimize space if memory constraints are very tight?

   • Answer: If memory is a critical constraint, you might consider an approximation algorithm that provides a statistically acceptable median estimate instead of the exact median, which could reduce space requirements.

By understanding and explaining these concepts, you demonstrate not only your technical ability but also your problem-solving skills in managing large-scale data, which is essential for backend roles at FAANG companies.