Below is the coding challenge interview question.
Question: Coding Challenge – Given a list of people with their birth year and death year (all between 1900 and 2000), find the year with the most number of people alive.
Review Our Software Engineering Coding Challenge All in One Page.
Sample Data:
Input:
[{ 'by': 1990, 'dy': 1992 }, { 'by': 1995, 'dy': 1999 }, { 'by': 1992, 'dy': 2000 }, { 'by': 1990, 'dy': 1996 }]
Output: 1995
Checkout New Palindrome Coding Challenge:
Here, we have visual Tabular data with year array and People Alive Counter which keeps tracking of population.
So, In Given Sample Input, we have:
Person 1: ‘birthyear’: 1990, ‘deathyear’: 1992
Person 2: ‘birthyear’: 1995, ‘deathyear’: 1999
Person 3: ‘birthyear’: 1992, ‘deathyear’: 2000
Person 4: ‘birthyear’: 1990, ‘deathyear’: 1996
| YEAR | People Alive Count = 0 | Death Count =0 |
|---|---|---|
| 1990 | +1 +1 = 2 | |
| 1991 | 2 | |
| 1992 | +1 => 3-1 => 2 | -1 |
| 1993 | 2 | |
| 1994 | 2 | |
| 1995 | +1 => 2+1 => 3 | |
| 1996 | 3 => 3-1 => 2 | -1 |
| 1997 | 2 | |
| 1998 | 2 | |
| 1999 | 2 | |
| 2000 | 2 => 2 – 2 => 0 | -1 -1 |
First, you can pre fill the Array with Value 0;
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Because, We have given all the year range between 1990 to 2000. So we can use 0 to 10 index. Now, using given array check for the birth year, for example if birth year is 1990 and so we will use index [1990 - 1990] which is 0 and then we will increment value by 1 at index 0, if it is 1992 then we will use 1992 - 1990 which is 2 and so on. You can repeat similar method for death year. For example if death year is 1996 and so we will use index [1996 - 1990] which is 6 and then we will decrement value by 1 at index 6, if it is 1992 then we will use 1992 - 1990 which is 2 and so on.
| 2 | 0 | 0 | 0 | 0 | 1 | -1 | 0 | 0 | -1 | -1 |
As, We have updated Array, we can loop through this array and we keep adding values and check for the maximum value. Once we get the maximum value we can return index and add that index back to 1990.
If the Max Value is 3 at index 5 then we will return 1990 + 5 which is 1995.
Let’s use that dynamic programming algorithm into actual code!
const maxPopulation = (peoplearr) => {
//Pre Fill the Array with "0"
let yearArr = new Array(11).fill(0);
//Update the value with "+1+ or "-1" for the index birthyear - 1990 or deathyear - 1990.
for (let i = 0; i < peoplearr.length; i++) {
yearArr[peoplearr[i].by - 1990] += 1;
yearArr[peoplearr[i].dy - 1990] -= 1;
}
let population = 0;
let maxpopulation = 0;
let maxYear = 0
for (let j = 0; j < yearArr.length; j++) {
population += yearArr[j];
if (maxpopulation < population) {
maxpopulation = population;
maxYear = j;
}
}
return 1990 + maxYear;
}
let people = [{ 'by': 1990, 'dy': 1992 }, { 'by': 1995, 'dy': 1999 }, { 'by': 1992, 'dy': 2000 }, { 'by': 1990, 'dy': 1996 }];
console.log(maxPopulation(people));