Google Interview Question
- 3of 3 votes
Suppose you have a incoming stream of numbers and a method like T* readNextNumber() to read them, and each time there is only limited amont of them coming in and readNextNumber would return null if no more available. implement a method to calculate the median of all numbers you have read.- lucifer1986 August 28, 2015 in United States
The key point to the question is figure out the data structure to store those numbers you have read and I stopped at a balance tree, the interviewer told me it should be 2 heaps, one ascending and one descending, plus a median value between them. The final algorithm I figure out based on it is each time compare the new number with median, if bigger than it insert to the descending heap at the right side of the median else to the left, recalculate the median by checking heap sizes, the new median would be either current median, max of the left heap or min of the right heap.
| Report Duplicate | Flag | PURGE
Google Data Structures
Interview Type: Phone Interview
Open Chat in New Window