## Amazon Interview Question for Developer Program Engineers

• 4

Country: India
Interview Type: Phone Interview

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

I'll explain my algorithm with an example:

``````Input intervals (or lifetimes): [5, 11], [6, 18], [2, 5], [3,12]

1. Put the end and start times of the intervals in one array. Sort it!. Always put the start time before end time in case they are equal. Maintain flags to identify a start/end interval. For above input I'll do something like:
2S, 3S, 5S, 5E, 6S, 11E, 12E, 18E

2. Now scan the array from left to right keeping track of how many intervals we are in. (This would be equal to total numbers of start intervals - total number of end intervals encountered so far). For above input I'll get something like:
1, 2, 3, 2, 3, 2, 1, 0

3. Now pick the maxima points from step 2. All the maxima points will be Start intervals and the point next to a maxima point will always be an end interval (which will be the end of the maxima start interval). So we'll get:
[5S,5E] and [6S,11E].

Hence the result is [5,5], [6,11]``````

Time complexity = O(nLogn), because of sorting in step 1.
Space complexity = O(n)

Comment hidden because of low score. Click to expand.
0

Nice !!! :) it's awesome ..

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Good One

Comment hidden because of low score. Click to expand.
-1

@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

Comment hidden because of low score. Click to expand.
0

Can you please explain Step 2 ?
How you got 1, 2, 3, 2, 3, 2, 1, 0

Comment hidden because of low score. Click to expand.
2
of 4 vote

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.

Comment hidden because of low score. Click to expand.
0

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

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

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

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

The first part sounds like a simplified "rabbit and eel" problem, see apps.topcoder.com/wiki/display/tc/SRM+580

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

it's not correct see for test case
2,3
4,5
result

Maximum number(=1) of species live between: 2,5 years of age
it should be
it should be either 2,3 or 4,5

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

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

Comment hidden because of low score. Click to expand.
0

the second line of the code should be

``typedef pair<int, int> StartEnd;``

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

maintain a prioritybasedQ of events
two types of events 1-> life and death
keep a counter ...increment at life event, decrement at death....maxvalue is your answer......

O(nlogn)

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

``````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]])``````

Comment hidden because of low score. Click to expand.
0

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

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

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

}

Comment hidden because of low score. Click to expand.
0

``````/*  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.*/``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Comment hidden because of low score. Click to expand.
-1
of 1 vote

May be use interval tree?

Comment hidden because of low score. Click to expand.
0

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?

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.

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