Amazon Interview Question


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 3 vote

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.

static int maxYear(int[] births, int[] deaths) {
	int counts[] = new int[101];
	for(int i : births)
		counts[i-1900]++;
	for(int i : deaths)
		counts[i-1900]--;
	
	int max = counts[0];
	int year = 0;
	int pop = counts[0];
	for(int i=1; i<counts.length; i++) {
		pop += counts[i];
		if(pop > max) {
			max = pop;
			year = i;
		}
	}
	return year + 1900;
}

- Sunny November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This answer is incorrect. The required answer is: people alive not sub of dead and porn people in this year ;)

- MTA March 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Mahesh Venkatesh Shet April 01, 2019 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
	}

- Anonymous November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

- Anonymous November 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks it's working

- dominic November 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think above solution wont work if events have multiple entries of same years

- Anonymous April 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think above solution wont work if the birth or death arrays contain mutiple entries of same year

- Anonymous April 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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).

- Ankit Bhardwaj November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- yangxh92 November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does the above algorithm works in a scenario where first 100 people born and than 20 people will die?e.g. in year 1900, 100 people born first and than 20 people die.

- Anonymous November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes, the above approach should work fine.

- Anonymous November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes, the above approach should work fine.

- Anonymous November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Anonymous November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Victor November 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

;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

- Anonymous November 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
*
*/
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 );

}

}

- paramjit1992singh November 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- llamatatsu May 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 };
}

- Anonymous October 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- sv November 23, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More