trjhtr

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;

HashMap is overkill here.

Depending on the constraints of the problem (mainly the minimum and maximum allowable years), you could simply use an array instead of a HashMap.

Sure HashMaps have a O(1) complexity, but nothing is going to beat just indexing an array.

Better algorithm

Coming up with a better algorithm is very tricky.

Your solution is O(NL) where N is the number of people and L is the average lifetime. But keep in mind that L is practically a constant, so it does not really matter that much.

You could most certainly come up with a O(NlogN) solution, based on creating a sorted list of relevant dates. This would outperform your current solution for small values of N, but better performance at the low end is rarely useful (it can be, but that's the exception, not the rule).

Edit Thinking about this, I suspect that's the "trick" part of that interview question. Overlapping intervals is a classic interview problem. However, making the intervals happen on a fully discretized space makes the hashmap solution viable, whereas it can't be used when dealing with "traditional" float-bound intervals.

Nothing wrong with using the HashMap, but…

… all you actually need to store is the overall change for each year. Not even total births or deaths, just the total change. You can iterate at the end, and (keeping a high water mark) to find the maximum you only need to check when your change for the year is positive.

Things that might help

• Sort by birth, and keep a priority queue of deaths.


• Separate the birth and death, sort both lists.

Plenty wrong with the question, though

(the interviewer’s, not your posting here).

• Should changes be considered to happen at the start of the year?


• The end?


• When do you measure?


• Is it the average number for the year, or the maximum possible? Do any of the births happen before any of the deaths?

.. and so on. The problem is a little under-specified.