Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
//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));
}
}
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.
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();
}
}
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))
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+ " ");
}
}
}
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+ " ");
}
}
}
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.
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);
}
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] +" ");
}
}
}
convert periods into pairs
- Omri Bashari April 26, 2015{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)