Recently I had an interview where it was asked:
Given a list of people with their birth and end years find the year with the most number of people alive.
I implemented in Java and was trying to find the optimal solution. I am sure there might be some data structure which will be optimal to use in this scenario.
static class Person {
int born;
int died;
Person(int born, int died) {
this.born = born;
this.died = died;
}
}
/*
* (1920, 1939),
* (1911, 1944),
* (1920, 1955),
* (1938, 1939),
* (1920, 1939),
* (1911, 1944),
* (1920, 1955),
* (1938, 1939),
* (1937, 1940)
*
*/
public static void main(String[] args) {
List<Person> people = new ArrayList<>();
people.add(new Person(1933, 1989));
people.add(new Person(1920, 1939));
people.add(new Person(1911, 1944));
people.add(new Person(1920, 1955));
people.add(new Person(1938, 1939));
people.add(new Person(1920, 1939));
people.add(new Person(1911, 1944));
people.add(new Person(1920, 1955));
people.add(new Person(1938, 1939));
people.add(new Person(1937, 1940));
System.out.println(solution1(people));
}
public static int solution1(List<Person> people) {
HashMap<Integer, Integer> peopleMap = new HashMap<>();
int maxCount = 0;
int year = 0;
for (Person p : people) {
for (int i = p.born; i <= p.died; i++) {
Integer value = peopleMap.get(i);
if (value == null) {
peopleMap.put(i, 1);
} else {
value++;
if (maxCount < value) {
maxCount = value;
year = i;
}
peopleMap.put(i, value);
}
}
}
return year;
}