Amazon Interview Question
Country: India
Interview Type: In-Person
This answer is incorrect. The required answer is: people alive not sub of dead and porn people in this year ;)
The logic is partially correct. The question is to find year where population is max. Death of a person, in a given year also means he was leaving in that year. Subtracting for a death is not required. It is also possible that there could be many years in the range where the max population would exists.
private class Event implements Comparable<Event> {
int time;
boolean born;
public Event(int time, boolean born) {
this.time = time;
this.born = born;
}
@Override
public int compareTo(Event other) {
if (this.time < other.time) {
return -1;
} else if (this.time > other.time) {
return 1;
} else {
return 0;
}
}
}
public int maxAlive(int[] born, int[] die) {
Event[] events = new Event[born.length + die.length];
for (int i = 0; i < born.length; i++) {
events[i] = new Event(born[i], true);
}
for (int i = 0; i < die.length; i++) {
events[i+born.length] = new Event(die[i], false);
}
Arrays.sort(events);
int maxAlive = 0;
int currentAlive = 0;
for (int i = 0; i < events.length; i++) {
if (events[i].born) {
currentAlive++;
} else {
currentAlive--;
}
if (currentAlive > maxAlive) {
maxAlive = currentAlive;
}
}
return maxAlive;
}
Made a mistake there. I needed to add an int maxAliveYear which gets set when the maxAlive is set in
if (currentAlive > maxAlive) {
maxAlive = currentAlive;
maxAliveYear = events[i].time;
}
return maxAliveYear;
1) Take an array of 1000 elements and intialize each entry with 0.
2) Now for each birth do increment in that year and for each death decrement in that year.
3) Now the problem reduced to : Find max sum in an array, maintain sum as well as index and then add 1900 to that index to give the exact answer.
Complexity is O(n).
Put those years into an array, then you get an array with length 2n. Sort those years, sequence through the array and maintain a variable count. If you meet a birth year, plus one to count, otherwise minus one. Every time you need to update, compare count with the maximum result so far, if count > maximum, then you need to update maximum and the year which maximum occurs.
class Year {
public:
int year;
string type;
friend bool operator<(const Year &y1, const Year &y2) {
return y1.year < y2.year;
}
};
//The following function returns the last period that max people were alive
pair<int, int> maxAlive(vector<People> people) {
vector<Year> years;
for (People p : people) {
Year birth, death;
birth.year = p.birth;
birth.type = "birth";
death.year = p.death;
death.type = "death";
years.push_back(birth);
years.push_back(death);
}
sort(years.begin(), years.end());
int maximum = 0, count = 0, max_beg = 1900, max_end = 1900;
for (Year y : years) {
if (y.type == "birth") {
count++;
if (maximum <= count) {
maximum = count;
max_beg = y.year;
}
}
else {
if (maximum == count)
max_end = y.year;
count--;
}
}
return pair<int, int>(max_beg, max_end);
}
findMaxAlive m = fst $ foldl f (0, 0) diff
where
diff :: [Int]
diff = map snd (sort yearDiff)
yearDiff = foldl g defaultMap m
defaultMap :: [(Int, Int)]
defaultMap = zip [1900..2000] (repeat 0)
g :: [(Int, Int)] -> (Bool, Int) -> [(Int, Int)]
g m (False, year) = upd year (al (lookup year m) - 1) m
g m (True, year) = upd year (al (lookup year m) + 1) m
upd :: Int -> Int -> [(Int, Int)] -> [(Int, Int)]
upd k v m = m & traverse.filtered ((== k).fst)._2 .~ v
f :: (Int, Int) -> Int -> (Int, Int)
f (m, s) n = (max m (s + n), s + n)
I would like to bring in a discussion about this problem.
I can think of two approaches:
1. for each year between 1900 and 2000, iterate through the list ahd check how many people were alive at that year. Return the max.
Complexity: O(ny), where n is the number of people and y is the number of years (1000).
This is better than sorting the list and keep a counter of how many people are alive. Why? Because O(ny) is very very likely to be less than O(nlogn), since n >> y.
2. A more clever solution is to use interval tree. However, it's not worth it in this case.
To build the interval tree, it would take O(nlogn): n insertions in the binary tree of intervals. Following the tree construction, we would need to perform y searches in the tree. Bear in mind however that search in interval tree for ALL conflicting intervals is not O(logn), but O(n) worst-case.
Complexity: O(nlogn) (interval tree construction) + O(ny) (searches)
This is a good example of how better data structures not always result in better solutions.
;1) Create a hash table containing the year as key ,birth count and death count and maxalive as value.
2) loop through the data and update the hash table birth count and death count value and maxalive value as difference between birth and death count according to the key(year).
3) continue step 2 till all values are updated.
4) loop through the hash table (it would contain 100 elements) and fetch the highest maxalive value
complexity is o(n) for creating hashtable
/**
*
*/
package h;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
/**
* @author vaio
*
*/
public class birthdaeth {
/**
* @param args
* @throws IOException
* @throws NumberFormatException
*/
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
int i=0,j,year=0,n,b,d;
int birth[]=new int[1000];
int dead[]=new int[1000];
int startRange=1900,endRange=2000;
for(;startRange<=endRange;startRange++)
{
i++;
System.out.println("How many People are born in the year" + startRange);
b=Integer.parseInt(br.readLine());
birth[i]=b;
System.out.println("How many People died in the year" + startRange);
d=Integer.parseInt(br.readLine());
if(d>b){
System.out.println("How can dead be greater than born!!! Re-enter");
i--;
startRange--;
}else{
dead[i]=d;
}
}
startRange=endRange-i;
i=0;
int alive=0;
for(;startRange<=endRange;startRange++)
{
i++;
j=birth[i]-dead[i];
if(j<0 ||j<alive){
continue;
}
if(j>alive){
alive=j;
year=startRange+1;
}
}
System.out.println("Max people ie "+alive+" where alive in the year"+ year );
}
}
Input:
n - number of lifespans
2D array [n, 2] with births and deaths
Algorithm:
1. Create hashtable<year, frequency> to hold population frequencies
2. Parse through lifespans - O(n)
2a. Insert frequencies in the Hashtable; +1 for births, -1 for deaths - O(1)
3. Sort Hashtable by year to compute running frequency - O(nlogn)
4. Parse through the Hashtable and find year with Max population - O(n)
Time complexity: O(nlogn)
Improvement:
Clearly sorting takes most amount of time here. Looking for a way to do this without sorting.
C# Code:
#region Find year with max population given Births and Deaths
public void MaxPopulationYear()
{
// Given a list of people with birth and death years
int[,] lifeSpan = { { 2000, 2010 },
{ 1975, 2005 },
{ 1975, 2003 },
{ 1803, 1809 },
{ 1750, 1869 },
{ 1840, 1935 },
{ 1803, 1921 },
{ 1894, 1921 }};
int[,] lifSpan = { { 1900, 1910 },
{ 1910, 1975 },
{ 1910, 1980 },
{ 1905, 1945 },
{ 1950, 1960 },
{ 1970, 1995 },
{ 1950, 1980 },
{ 1990, 1995 }};
MaxPopulationYear(lifeSpan);
MaxPopulationYear(lifSpan);
}
public void MaxPopulationYear(int[,] lifeSpan)
{
// Hashtable to hold value of Population by frequency
Dictionary<int, int> popFreqByYear = new Dictionary<int, int>();
// Loop through the lifespan to create the hashtable - O(p); p - people
for (int i = 0; i < lifeSpan.GetLength(0); i++)
{
UpdateFreq(popFreqByYear, lifeSpan[i, 0], 1);
UpdateFreq(popFreqByYear, lifeSpan[i, 1], -1);
}
int maxPopYear = GetMaxPopYear(popFreqByYear);
Console.WriteLine(maxPopYear);
}
private int GetMaxPopYear(Dictionary<int, int> popFreqByYear)
{
int maxPop = 0;
int maxPopYear = 0;
int currentPop = 0;
// Orderby is an implementation of stable quick sort = O(nlogn); O(pLogp)
// Foreach gros through the hash table p times; O(p)
foreach (var pop in popFreqByYear.OrderBy(o => o.Key))
{
currentPop += pop.Value;
if (maxPop < currentPop)
{
maxPop = currentPop;
maxPopYear = pop.Key;
}
}
return maxPopYear;
}
// Looks if value is present in Hashtable - O(1)
// Returns updates if present or updates it
private void UpdateFreq(Dictionary<int, int> popFreqByYear, int year, int update)
{
int value;
if (popFreqByYear.TryGetValue(year, out value))
{
popFreqByYear[year] = value + update;
return;
}
popFreqByYear[year] = update;
}
#endregion
const highestLivingPeopleYear = (arr) => {
let year = currPeopleAlive = maxPeopleAlive = 0;
let birthYearsMap = {};
let deathYearsMap = {};
let yearsSet = [];
arr.forEach(pair => {
const { birth, death }
= updateHashForBirthAndDeaths(pair, birthYearsMap, deathYearsMap);
yearsSet.push(birth);
yearsSet.push(death);
});
yearsSet = [...(new Set(yearsSet))].sort();
yearsSet.forEach(y => {
currPeopleAlive += birthYearsMap[y] || 0;
currPeopleAlive -= deathYearsMap[y] || 0;
if (currPeopleAlive > maxPeopleAlive){
maxPeopleAlive = currPeopleAlive;
year = y;
}
});
return year;
}
const updateHashForBirthAndDeaths = (pair, birthYearsMap, deathYearsMap) => {
const birth = pair[0];
const death = pair[1] + 1;
birthYearsMap[birth] = (birthYearsMap[birth] || 0) + 1;
deathYearsMap[death] = (deathYearsMap[death] || 0) + 1;
return { birth, death };
}
Create a hash table containing the year as key ,birth count and death count and maxalive as value.
2) loop through the data and update the hash table birth count and death count value and maxalive value as difference between birth and death count according to the key(year).
3) continue step 2 till all values are updated.
4) loop through the hash table (it would contain 100 elements, as number of years is 100(1900-2000)) and fetch the highest maxalive value.since finding the max element in 100 values the time complexity is insignificant.
complexity is o(n) for creating hashtable
Create an array that holds the births-deaths offset for each year between 1900 and 2000. Iterate through the birth/death years and increment/decrement the corresponding count. Then just iterate through the counts and keep track of the max count and the corresponding year.
- Sunny November 22, 2014