CareerCup

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.
Insert-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...

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;
  }
}