Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

convert periods into pairs
{day#, discount change}
start day of period has a positive discount change value, end day negative.
sort by day.
scan pairs, updating max total discount. when max is changed that is the starting day of the max period and the end day of the period is reset.
when we have max starting day and find a drop in total discount we set that pair as the end of the period.
O(nlgn)

- Omri Bashari April 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please explain with the above example

- Shrunga July 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a segment tree. Perform updates with the discount value and perform query on each of the n days. Solution will be of O(n log n) complexity.

- V Manikantan April 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//This method will pre process first to make an array for each period and then goes through this array to find the interval with max discount.

Space and Time complexity is O(MaxEndPeriod - MinStartPeriod)

public class Interval {
public class DiscountPeriod{
		int start;
		int end;
		double discount;
		public DiscountPeriod(int start, int end, double discount){
			this.start = start;
			this.end = end;
			this.discount = discount;
		}
		
		public DiscountPeriod(){
			
		}
		
		@Override
		public String toString(){
			StringBuffer sb  = new StringBuffer();
			sb.append(this.start + " - "+this.end + " = "+ this.discount);
			return sb.toString();
		}
	}
	public DiscountPeriod getMaxDiscountPeriod(List<DiscountPeriod> periods){
		
		//preprocess 
		int minPeriod = Integer.MAX_VALUE;
		int maxPeriod = Integer.MIN_VALUE;

		for(int i=0;i< periods.size();i++){
			DiscountPeriod currPeriod = periods.get(i);
			if(currPeriod.start < minPeriod)
				minPeriod = currPeriod.start;

			if(currPeriod.end > maxPeriod)
				maxPeriod  = currPeriod.end;
		}

		int [] periodDiscounts = new int[maxPeriod-minPeriod+1];

		for(int i=0;i < periods.size(); i++){
			DiscountPeriod currPeriod = periods.get(i);
			for(int j = currPeriod.start -minPeriod; j <= currPeriod.end - minPeriod;j++){
				periodDiscounts[j]+=currPeriod.discount;
			}
		}	
		
		for(int i=0;i< periodDiscounts.length;i++){
			System.out.print(periodDiscounts[i]+" ");
		}
		//find max
		int maxDiscount = 0;
		int maxStart = 0;
		int maxEnd = 0;
		int start = 0 ;
		int end = 1;

		while(end < periodDiscounts.length){
			if(periodDiscounts[start] != periodDiscounts[end]){
				if(periodDiscounts[end-1] > maxDiscount){
					maxStart = start;
					maxEnd = end-1;
					maxDiscount = periodDiscounts[end-1];
					start = end;
					
				}
			}
			end++;
		}

		if(periodDiscounts[start] >  maxDiscount){
			maxStart = start;
			maxEnd = end-1;
			maxDiscount = periodDiscounts[end-1];

		} 

		DiscountPeriod returnPeriod  = new DiscountPeriod();
		returnPeriod.start = minPeriod + maxStart;
		returnPeriod.end = minPeriod + maxEnd;
		returnPeriod.discount = maxDiscount;

		return returnPeriod;
	}

public static void main(String[] args) {
		Interval i  = new Interval();
				
		ArrayList<DiscountPeriod> discounts = new ArrayList<DiscountPeriod>();
		discounts.add(i.new DiscountPeriod(1,5,10));
		discounts.add(i.new DiscountPeriod(2,8,5));
		discounts.add(i.new DiscountPeriod(4,6,20));
		
		
		System.out.println("\nGreatest discount found from "+i.getMaxDiscountPeriod(discounts));
	}

}

- akella.mahesh April 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution is not generic...days could be replaced by time or some decimal values..

- Dinesh Pant April 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

To make this truly generic, the problem can be expanded to multiple dimensions. Ex. discount being based on a combination of day + weather + location.

Ends up generalizing into a problem where given a set of n-dimensional objects, find the most that intersect.

Taking it yet another step further, not only report the max number of intersections, but which objects constitute the max number of intersections.

- JW April 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class DiscountRange
    {
        public int StartDay { get; set; }
        public int EndDay { get; set; }
        public float Discount { get; set; }
    }

    public static class DiscountFinder
    {
        public static DiscountRange FindMaxDiscountRange(IList<DiscountRange> discountRanges)
        {
            if(discountRanges==null) throw new ArgumentNullException("No discount Ranges list available");
            if(!discountRanges.Any())
                return new DiscountRange();

            var dayRange = new SortedDictionary<int, float>();
            var discountRange = new DiscountRange();
            foreach (var range in discountRanges)
            {
                for (int i = range.StartDay; i <= range.EndDay; i++)
                {
                    if (dayRange.ContainsKey(i))
                    {
                        dayRange[i] += range.Discount;
                    }
                    else
                    {
                        dayRange.Add(i, range.Discount);
                    }
                }
            }


            foreach (var day in dayRange)
            {
                if (day.Value > discountRange.Discount)
                {
                    discountRange.Discount = day.Value;
                    discountRange.StartDay = day.Key;
                    discountRange.EndDay = day.Key;
                }
                else if (Equals(day.Value, discountRange.Discount))
                {
                    discountRange.EndDay = day.Key;
                }
            }
            return discountRange;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var ranges = new List<DiscountRange>();
            ranges.Add(new DiscountRange() { StartDay = 2, EndDay = 8, Discount = 5 });
            ranges.Add(new DiscountRange() { StartDay = 1, EndDay = 5, Discount = 10 });
            ranges.Add(new DiscountRange() { StartDay = 4, EndDay = 6, Discount = 20 });
            var result = DiscountFinder.FindMaxDiscountRange(ranges);
            Console.ReadLine();
        }
    }

- Ashish April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would define the following method signature:

short* findMaxDiscountPeriods(const short * periods, const short * discounts)

, where

/// pointer to a periods array. Ex. day 1-5, 0001 1111 = 31
const short * periods
/// pointer to a corresponding discounts array
const short * discounts

method returns array with a sum of discounts. After only max values are printed.

#include <iostream>

using namespace std;

const int PeriodCounter = 3;

short* findMaxDiscountPeriods(const short * periods, const short * discounts)
{
	static short results[sizeof(short) * 8] = {};
	for (int i = 0; i < PeriodCounter; i++){
		short k = 0;
		short period = periods[i];
		while (k < sizeof(short) * 8){
			if (period & 1){
				results[k] = results[k] + discounts[i];
			}
			period = period >> 1;
			k++;
		}
	}
	return results;
}

void printMaxDiscounts(const short* results)
{
	short max = -1;
	// find max
	for (int i = 0; i < sizeof(short) * 8; i++){
		if (results[i] > max){
			max = results[i];
		}
	}

	for (int i = 0; i < sizeof(short) * 8; i++){
		if (results[i] == max){
			cout << i << " : " << max<<"\n";
		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	short periods[PeriodCounter] = { 31, 254, 24 };
	short discounts[PeriodCounter] = { 10, 5, 20 };
	short* maxRange = findMaxDiscountPeriods(periods, discounts);
	printMaxDiscounts(maxRange);
	return 0;
}

Complexity: O(numberOfPeriods*(max period))

- Marcello Ghali April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use HashMap with key as day1..Day6 and value=discount.

- som April 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use Interval tree concept and create one with above days. Below is the code for the same.

public class DiscountTree {

    private IntervalNode root;
    private static int[] dayArray = new int[8];

    //Inner Node class 
    private class IntervalNode {
        IntervalNode left; 
        int start;
        int end;
        int maxEnd;
        int discount;
        IntervalNode right;
        //Constructor
	    public IntervalNode(IntervalNode left, int start, int end, int maxEnd, IntervalNode right, int discount) {
	        this.left = left;
	        this.start = start;
	        this.end = end;
	        this.maxEnd = maxEnd;
	        this.right = right;
	        this.discount = discount;
	    }
    }
    
    //To check for valid intervals
    private void checkInterval(int start, int end) {
        if (start >= end) 
        {
            throw new IllegalArgumentException("The end " + end + " should be greater than start " + start);
        }
    }
    
    
    /**
     * Adds an interval to the the calendar
     * 
     * @param start the start of interval
     * @param end   the end of the interval.
     */
    public void add (int start, int end, int discount) {
    	
    	checkInterval(start,end);

        IntervalNode inode = root;
        while (inode != null) {
            
        	inode.maxEnd = (end > inode.maxEnd) ? end : inode.maxEnd;
            
            if (start < inode.start) {
                if (inode.left == null) {
                    inode.left = new IntervalNode(null, start, end, end, null,discount);
                    return;
                }
                inode = inode.left;
            } 
            else {
                if (inode.right == null) {
                    inode.right = new IntervalNode(null, start, end, end, null,discount);
                    return;
                }
                inode = inode.right;
            }
        }
        root =  new IntervalNode(null, start, end, end, null,discount);
    }

    //Mathod call to check for discount
    public void overlap() {
    	
    	checkMaxDiscount(root);
    }
    
    private static void checkMaxDiscount(IntervalNode root){
    	
    	if(root == null){
    		return;
    	}
    	
    /*	if(day >= root.start && day <= root.end){
    		dayArray[day-1]+= root.discount;
    	}
    */	
    	for(int i=root.start; i<=root.end; i++){
    		dayArray[i-1]+= root.discount;
    	}
    	
    	checkMaxDiscount(root.left);
    	checkMaxDiscount(root.right);
    	
    }

    public static void main(String[] args) {
    	DiscountTree intervalSearchTree = new DiscountTree();
        intervalSearchTree.add(1,5,10);
        intervalSearchTree.add(2,8,5);
        intervalSearchTree.add(4,6,20);

        intervalSearchTree.overlap();
        
        /*
        for(int i=1; i<=8; i++){
        	intervalSearchTree.overlap(i);
        }
        */
        PrintArray();
    }
    
    private static void PrintArray(){
		
		for(int i : dayArray){
			System.out.print(i+ " ");
		}
	}
}

- Ram April 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple one : use Interval Tree

public class DiscountTree {

    private IntervalNode root;
    private static int[] dayArray = new int[8];

    //Inner Node class 
    private class IntervalNode {
        IntervalNode left; 
        int start;
        int end;
        int maxEnd;
        int discount;
        IntervalNode right;
        //Constructor
	    public IntervalNode(IntervalNode left, int start, int end, int maxEnd, IntervalNode right, int discount) {
	        this.left = left;
	        this.start = start;
	        this.end = end;
	        this.maxEnd = maxEnd;
	        this.right = right;
	        this.discount = discount;
	    }
    }
    
    //To check for valid intervals
    private void checkInterval(int start, int end) {
        if (start >= end) 
        {
            throw new IllegalArgumentException("The end " + end + " should be greater than start " + start);
        }
    }
    
    
    /**
     * Adds an interval to the the calendar
     * 
     * @param start the start of interval
     * @param end   the end of the interval.
     */
    public void add (int start, int end, int discount) {
    	
    	checkInterval(start,end);

        IntervalNode inode = root;
        while (inode != null) {
            
        	inode.maxEnd = (end > inode.maxEnd) ? end : inode.maxEnd;
            
            if (start < inode.start) {
                if (inode.left == null) {
                    inode.left = new IntervalNode(null, start, end, end, null,discount);
                    return;
                }
                inode = inode.left;
            } 
            else {
                if (inode.right == null) {
                    inode.right = new IntervalNode(null, start, end, end, null,discount);
                    return;
                }
                inode = inode.right;
            }
        }
        root =  new IntervalNode(null, start, end, end, null,discount);
    }

    //Mathod call to check for discount
    public void overlap() {
    	
    	checkMaxDiscount(root);
    }
    
    private static void checkMaxDiscount(IntervalNode root){
    	
    	if(root == null){
    		return;
    	}
    	
    /*	if(day >= root.start && day <= root.end){
    		dayArray[day-1]+= root.discount;
    	}
    */	
    	for(int i=root.start; i<=root.end; i++){
    		dayArray[i-1]+= root.discount;
    	}
    	
    	checkMaxDiscount(root.left);
    	checkMaxDiscount(root.right);
    	
    }

    public static void main(String[] args) {
    	DiscountTree intervalSearchTree = new DiscountTree();
        intervalSearchTree.add(1,5,10);
        intervalSearchTree.add(2,8,5);
        intervalSearchTree.add(4,6,20);

        intervalSearchTree.overlap();
        
        /*
        for(int i=1; i<=8; i++){
        	intervalSearchTree.overlap(i);
        }
        */
        PrintArray();
    }
    
    private static void PrintArray(){
		
		for(int i : dayArray){
			System.out.print(i+ " ");
		}
	}
}

- Ram April 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Make 3 bit vector and set 1 on the discount days.
2. And'&' them. This will give common days having discounts.
3. If all are 0 then '&' between next two highest discount day groups bit vector.

- King@Work May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u please explain with a piece of code

- anonymous May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@king@Work can you please explain with code

- Anonymous May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pair<int, int> getPeriodOfMaxCount(int start[], int end[], int count[], int n)
{
	assert(start != NULL && end != NULL && count != NULL && n != 0);

	int minTime = *min_element(start, start + n), maxTime = *max_element(end, end + n), len = maxTime - minTime + 2;

	int *sum = new int[len]();
	
	for (int i = 0; i < n; ++i)
	{
		sum[start[i] - minTime] += count[i]; sum[end[i] - minTime + 1] -= count[i];
	}

	int maxCount = sum[0], s = 0, t = 0;

	for (int i = 1; i < len;)
	{
		sum[i] += sum[i - 1];

		if (sum[i] > maxCount)
		{
			maxCount = sum[i]; s = i;
			
			while (i < len - 1 && sum[++i] == 0);

			t = i - 1; sum[t] = maxCount;
		}
		else ++i;
	}

	delete[] sum;

	return make_pair(minTime + s, minTime + t);
}

- malinbupt May 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int[] dayArray = new int[8]; //should be declared at class level

public void add(int start, int end, int discount) 
    {	
        for(int i=start-1; i<end; i++)
        {
        	dayArray[i] = dayArray[i] + discount;
        }
    }

- Anonymous May 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int[] dayArray = new int[8]; //should be declared at class level

public void add(int start, int end, int discount) 
    {	
        for(int i=start-1; i<end; i++)
        {
        	dayArray[i] = dayArray[i] + discount;
        }
    }

- Darakshan May 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaxDiscount {
	public static void main(String[] args) {
		int start[] = new int[10],end[]=new int[10],discount[]=new int[10];
		int maxDiscount[] = new int[10];
		
		int i = 0;
		start[i]=1;
		end[i]=5;
		discount[i]=10;
		
		i++;
		start[i]=2;
		end[i]=8;
		discount[i]=5;
		

		i++;
		start[i]=4;
		end[i]=6;
		discount[i]=20;
		
		for(int j=0;j<=i;j++){
			
			for(int k=start[j];k<=end[j];k++)
			{
				maxDiscount[k]+=discount[j];
			}
		}
		for(int j=0;j<maxDiscount.length;j++){
			
				if(maxDiscount[j]!=0)
				System.out.println(j+" day : "+maxDiscount[j] +" ");
			}
			
	} 
	
	

}

- Ganesh June 05, 2016 | 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