Google Interview Question
InternsTeam: Software Engineering
Country: Brazil
Interview Type: In-Person
Approach where amount of distinct numbers is border by a fixed number works well for this challenge. If we have no such limit, this challenge should be solved via heaps.
So, my implementation in Java below:
The idea is similar to ChrisK, we store everything in array: index -> age; value -> amount of people of that age.
My function receive array with all ages as a parameter, build an array, based on description above and calculate the median.
static double getMedianAge(int[] peopleAges) {
int[] ages = new int[MAX_AGE];
if (peopleAges.length == 1) {
return peopleAges[0];
}
if (peopleAges.length == 2) {
return (peopleAges[0] + peopleAges[1]) / 2.0;
}
for (int p : peopleAges) {
ages[p]++;
}
boolean isAmountOfPeopleAnOddNumber = peopleAges.length % 2 == 1;
int half = peopleAges.length >> 1;
int left;
int right = -1;
double median = 0.0;
for (int i = 0; i < MAX_AGE; i++) {
if (ages[i] != 0) {
left = right + 1;
right = left + ages[i] - 1;
if (isAmountOfPeopleAnOddNumber && left <= half && half <= right) {
median = i;
break;
}
if (!isAmountOfPeopleAnOddNumber && left <= half - 1 && half - 1 <= right) {
median += i;
if (left <= half && half <= right) {
median += i;
} else {
// find next number
while (ages[++i] == 0) {
}
median += i;
}
median /= 2;
break;
}
}
}
return median;
}
For this problem I think we should use heap to make sure that upon every insert, we keep the order in place. And to implement this heap functionality, I used Collections.binarysearch to get the index of where I should place the element. From there we can use ArrayList add which allows us to add the element to our desired index.
Insertion complexity: O(n log n)
Query complexity: O(n log n)
Space complexity: O(n)
Median complexity: O(1)
The following is my java code:
import java.util.*;
public class MedianAge {
ArrayList<Integer> ages;
public static void main(String[] args) {
MedianAge ma = new MedianAge();
Scanner sc = new Scanner(System.in);
while(true) {
int num = sc.nextInt();
ma.add(num);
}
}
public MedianAge() {
ages = new ArrayList<>();
}
public void add(int age) {
int index = Collections.binarySearch(ages, age);
if(index < 0) {
index = Math.abs(index)-1;
}
ages.add(index, age);
System.out.println(getMedian());
System.out.println(ages.toString());
}
public double getMedian() {
int mid = ages.size()/2;
if(ages.size() % 2 == 1) return ages.get(mid);
else return (ages.get(mid)+ages.get(mid-1))/2.0;
}
}
I'd assume the age is in years, so there are at most 120 different ages = buckets. I can now store, the count of ages in an array with index age where the age addreses a "bucket". I maintain as a total count. To get the mean, I just count through the 120 buckets until I reach n/2. I'd assume for simplicity that the floor median is fine, so I don't have to add 0.5 in case of even count where floor median is in one bucket and ceiling median is in the next.
- Chris January 26, 2017Insert-complexity will be constant: O(1)
Same with delete, if ever wanted.
Query median is as well O(1) since the number of buckets is constant
--
This can be optimized in terms of number of operations required to determine the mean if mean is maintained when inserting. This might be interesting if the ratio query/inserts is not very small.
--
An other interesting aspect is, how big is the error if calculated as described above...