Google Interview Question for Interns

Team: Software Engineering
Country: Brazil
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
of 4 vote

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

- Chris January 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
of 1 vote

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) {

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

    return median;

- Mike L January 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

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(;
    while(true) {
      int num = sc.nextInt();

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

  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;

- obed.tandadjaja January 31, 2017 | Flag Reply

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More


CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More