## Google Interview Question for Interns

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

Comment hidden because of low score. Click to expand.
4
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...

Comment hidden because of low score. Click to expand.
1
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;
}
if (peopleAges.length == 2) {
return (peopleAges + peopleAges) / 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;
}``````

Comment hidden because of low score. Click to expand.
0
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(System.in);
while(true) {
int num = sc.nextInt();
}
}

public MedianAge() {
ages = new ArrayList<>();
}

int index = Collections.binarySearch(ages, age);
if(index < 0) {
index = Math.abs(index)-1;
}
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;
}
}``````

Name:

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

### Books

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

### Videos

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.