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

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

Could you please explain with the above example

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.

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

System.out.println("\nGreatest discount found from "+i.getMaxDiscountPeriod(discounts));
}

}``````

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

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

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.

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

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

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

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

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

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.overlap();

/*
for(int i=1; i<=8; i++){
intervalSearchTree.overlap(i);
}
*/
PrintArray();
}

private static void PrintArray(){

for(int i : dayArray){
System.out.print(i+ " ");
}
}
}``````

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.overlap();

/*
for(int i=1; i<=8; i++){
intervalSearchTree.overlap(i);
}
*/
PrintArray();
}

private static void PrintArray(){

for(int i : dayArray){
System.out.print(i+ " ");
}
}
}``````

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.

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

can u please explain with a piece of code

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

@king@Work can you please explain with code

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

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

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

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

}

}``````

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.