Amazon Interview Question for Developer Program Engineers


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)

- Epic_coder June 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Arun Kumar Gupta June 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 June 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good One

- Jerry June 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 votes

@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

- sapy June 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Dev October 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 5 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.

- Anil June 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Shazzi June 10, 2013 | Flag
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.

- PKT June 08, 2013 | Flag Reply
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

- dn June 08, 2013 | Flag Reply
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");
	}
}

- Murali Mohan June 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Arun Kumar Gupta June 09, 2013 | Flag
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;
    }

- testjay June 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the second line of the code should be

typedef pair<int, int> StartEnd;

- testjay June 08, 2013 | Flag
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)

- Anonymous June 09, 2013 | Flag Reply
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]])

- Anonymous June 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@anonymous: logic please?

- aka June 09, 2013 | Flag
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)
                                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;

}

- ashu June 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ashu June 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

sites.google.com/site/spaceofjameschen/home/sort-and-search/find-period-when-maximum-number-of-animals-lived----amazon

- Anonymous June 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

May be use interval tree?

- Anonymous June 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

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?

- Murali Mohan June 09, 2013 | Flag


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