Amazon Interview Question
Developer Program EngineersCountry: India
Interview Type: Phone Interview
nice,
but i think this will also work
1.Firstly take an array arr[100],initialize it to zero.
2.for every interval do +1 for eg, [5, 7] ,do arr[5]++,arr[6]++.arr[7]++;
3.now traverse again and you got all intervals for max value.
i think in this case time complexity is O(n).
@rdx:
I think your solution majorly depends on the range in the intervals rather than no of intervals.
so, e.g [1,1000], [2,2000] your solution will need array of 2000 which not dependent on no of intervals or constant either.
n loop will run 1000 + 1988 = 2988...
which is not a good
Maintain an array/hashtable as a counter.
e.g. for [2,5] ( Assuming the animal was born at time 2 and died at 5 )
increment count of 2,3,4 and 5 by one
repeat the step for each set.
at the end parse the array/hash to get the max and min and respective year.
Do you mean to say for
[2, 5] --> 2=1(value), 3 = 1, 4 = 1, 5 = 1.
[5, 11] --> 5 = 2(value) and 6 to 11 has value 1
[6, 18] --> 6 to 11 has value 2 and 12 to 18 has value 1
[3,12] --> 3 to 4 has value 2 and 5 has value 3 and 6 to 11 has value 3 and 12 has value 2
can you please elaborate little more
[i/p] : [5, 11], [6, 18], [2, 5],[3,12]
Logic:
-Sort input birth component and death component separately
birthSortedList = [2,3,5,6]
deathSortedList = [5,11.12.18]
-Now we will perform a kind of merge sort where we have two sorted list of births & deaths and in resultant array we will enter char '{' in case birth is selected and '}' in case death is selected.
resultantArray = { { { } { } } }
-now have a counter,MaxLivingAnimalEndYearIndex and MaxLivingAnimal(initialized with zero) and start traversing resultant array and increase counter with 1 for each '{' and decrese it for each '}'
-In case (counter > MaxLivingAnimal) copy counter into MaxLivingAnimal and copy current index into MaxLivingAnimalEndYearIndex
counter = 2
MaxLivingAnimalEndYearIndex = 3 (indicate index in resultantArray)
-At last we will have MaxLivingAnimal and MaxLivingAnimalEndYearIndex. Just before MaxLivingAnimalEndYearIndex we will have MaxLivingAnimalStartYearIndex .
MaxLivingAnimalEndYearIndex = 3 (indicate index in resultantArray)
MaxLivingAnimalStartYearIndex =2 (indicate index in resultantArray)
-Traverse resultantArray upto index 'MaxLivingAnimalstartYearIndex' and count no. of '{' upto' resultantArray[MaxLivingAnimalstartYear]' that will give you index of 'MaxLivingAnimal start Year' in birthSortedList
-Traverse resultantArray upto index 'MaxLivingAnimalEndYear' and count no. of '}' upto 'resultantArray[MaxLivingAnimalEndYearIndex]' that will give you index of 'MaxLivingAnimal End Year' in birthSortedList
-We have Start and end year for max animal alive.
1. Maintain a hash table H and for each of the intervals, store the boundaries as keys and an int as a value. Increment the value if the key is a starting boundary, and decrement if it is an ending boundary.
For eg, for [5, 11], [6, 18], [2, 5],[3,12]
5 -> 1
11 -> -1
6 -> 1
18 -> -1
2 -> 1
5 -> 0
3 -> 1
12 -> -1
Run a loop from 1 to the maximum ending boundary. Maintain running counters and global counters to sum up the values as we see in the hash table and print out the sub-interval that overlaps maximum number of given intervals. Time complexity O(n): Space complexity O(n)
Java implementation below: Input need to be given as:
5,11
6,18
2,5
3,12
import java.util.HashMap;
import java.util.Scanner;
import java.util.regex.Pattern;
public class MaxOverlappingIntervals {
static HashMap<Integer, Integer> intervals = new HashMap<Integer, Integer>();
static int endMax = 0, gblIntervalOverlappingCount = 0,
localIntervalOverlappingCount = 0;
static int subIntBegin = 0, subIntEnd = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Pattern pattern = Pattern.compile(System.getProperty("line.separator") + "|\\s");
scanner.useDelimiter(pattern);
while (scanner.hasNextLine()) {
String input = scanner.next();
if (input.length() == 0) break;
Integer begin = Integer.parseInt(input.split(",")[0]);
Integer end = Integer.parseInt(input.split(",")[1]);
intervals.put(begin,
!intervals.containsKey(begin) ? 1
: intervals.get(begin) + 1);
intervals
.put(end,
!intervals.containsKey(end) ? -1 : intervals
.get(begin) - 1);
endMax = end > endMax ? end : endMax;
}
int val = 0;
for (int i = 0; i <= endMax; i++) {
if (intervals.get(i) != null) {
val = intervals.get(i);
if (val > 0) {
localIntervalOverlappingCount += val;
subIntBegin = i;
/*if (localIntervalOverlappingCount - val == 0) {
subIntBegin = i;
}*/
} else if (val < 0) {
localIntervalOverlappingCount += val;
if ((localIntervalOverlappingCount - val) >= gblIntervalOverlappingCount) {
gblIntervalOverlappingCount = localIntervalOverlappingCount - val;
subIntEnd = i;
}
}
}
}
if (subIntEnd > subIntBegin)
System.out.println("Maximum number(=" + gblIntervalOverlappingCount + ") of species live between: "
+ subIntBegin + "," + subIntEnd + " years of age");
else
System.out.println("No overlapping intervals found");
}
}
I take Dumbo's approach, but just use one array to indicate the start and end on each period and then scan the array once to find out the max period based on the running sum
const int YEARS = 100;
pair<int, int> StartEnd;
StartEnd findMaxNumAnimals(vector<StartEnd>& animalLifes)
{
int startEndIndicators[YEARS];
int i;
for ( i = 0; i < YEARS; i++)
startEndIndicators[i] = 0;
for ( i = 0; i < animalLifes.size() ; ++i )
{
StartEnd& oneAnimal = animalLifes[i];
startEndIndicators[oneAnimal.first]++; // start: +1
startEndIndicators[oneAnimal.second]--; // end : -1
}
int maxNo = 0;
int currentNo = 0;
StartEnd maxPeriod;
bool isInMaxPeriod = false;
for ( i = 0 ; i < YEARS; ++i )
{
currentNo += startEndIndicator[i];
if ( currentNo > maxNo )
{
maxNo = currentNo;
maxPeriod.first = i;
isInMaxPeriod = true;
}
else if ( isInMaxPeriod )
{
if ( currentNo < maxNo )
{
maxPeriod.second = i -1;
isInMaxPeriod = false;
}
}
}
if ( isInMaxPeriod )
maxPeriod.second = YEARS -1;
return maxPeriod;
}
def maxPeriod(age_range):
counts = {}
for start, end in age_range:
for i in xrange(start, end + 1):
if i in counts:
counts[i] += 1
else:
counts[i] = 1
return max(counts.iteritems(), key=lambda x: x[1])
print maxPeriod([[5, 11], [6, 18], [2, 5], [3,12]])
static void Main(string[] args)
{
var list = new List<KeyValuePair<int, int>>();
List<int[]> data = new List<int[]>() { new int[] { 5, 11 }
, new int[] { 6, 18 }
, new int[] { 2, 5 }
, new int[] { 3, 12 } };
GetMaxAndMinYear(data);
for (int year = minYear; year <= maxYear; year++)
{
for (int i = 0; i < data.Count; i++)
{
if (data[i].Length > 0)
{
if (year >= data[i][0] && year <= data[i][data[i].Length - 1])
{
int index = isKeyExists(list, year);
if (index == -1)
list.Add(new KeyValuePair<int, int>(year, 1));
}
}
}
}
int maxNoOfAnimals = 0;
foreach (var element in list)
if (maxNoOfAnimals < element.Value) maxNoOfAnimals = element.Value;
bool isFirstYear = false;
foreach (var element in list)
{
if (!isFirstYear && element.Value == maxNoOfAnimals)
{
minYear = element.Key;
maxYear = element.Key;
isFirstYear = true;
}
if (isFirstYear && element.Value == maxNoOfAnimals)
maxYear = element.Key;
}
Console.WriteLine("the max no of animals lived in the years {0} to {1}", minYear, maxYear);
}
static int maxYear;
static int minYear;
public static void GetMaxAndMinYear(List<int[]> data)
{
for (int i = 0; i < data.Count; i++)
{
if (data[i].Length > 0)
{
for (int j = 0; j < data[i].Length; j++)
{
if (maxYear < data[i][j]) maxYear = data[i][j];
if (minYear == 0 || minYear > data[i][j]) minYear = data[i][j];
}
}
}
}
public static int isKeyExists(List<KeyValuePair<int, int>> data, int key)
{
int index = -1;
int value;
foreach(var element in data)
{
index++;
if (element.Key.Equals(key))
{
value=element.Value;
data.Remove(element);
data.Add(new KeyValuePair<int, int>(key, value + 1));
return 0;
}
}
return -1;
}
/* The logic here is first create scale of range lying from min year to max year from the
* given set of input where animals lived.
* Then loop through the scale and find out during each years how many animals lived
* and yes before that create list of key Value pair so that u can set key as the year
* and value stating the no of animals lived in that year and then get the max no of animals.
* Based on the max no of animals you got, again loop through the scale of given input
* duration and find out from which year to which year those many max no of animals
* lived and u ll get the answer.*/
I don't think using an interval tree can simplify the problem. any further. AFAIK, Interval tree can be used to identify if there exists any interval in the tree, encompassing the given interval.
I tried to think on those lines, but could not find an effective solution. Could you please articulate your thoughts?
I'll explain my algorithm with an example:
Time complexity = O(nLogn), because of sorting in step 1.
- Epic_coder June 09, 2013Space complexity = O(n)