Google Sooftware Engineer Interview Interview Experiences

Problem: Design a class that supports two operations: 1) addNum(int num) and 2) findMedian(). What They Assess: Knowledge of data structures (heaps), insight into problem properties, handling real-time data. Answer Framework: Clarify: "How should we handle even vs. odd counts? (Median is the average of the two middle numbers for even). Are we memory-constrained?" Think Aloud: "The naive approach is to store numbers in a list and sort on every query. That's O(n log n) for findMedian. We need something faster." "The median splits a sorted list into two halves. What if we kept track of the largest number in the smaller half and the smallest number in the larger half?" "A Max-Heap is perfect for the smaller half (quick access to its max). A Min-Heap is perfect for the larger half (quick access to its min)." "Rule: The max-heap can be at most one element larger than the min-heap. The top of the max-heap <= the top of the min-heap." read more