## Goldman Sachs Interview Question

**Country:**United States

```
public class BestDeal{
public static void main(String []args){
int [][] IntervalList = {{1,2},{2,4},{4,8}};
int [] IntervalPrice = {10, 30, 25};
int MaxPrice = 0;
int bestDeal =0;
for (int i=0 ;i< IntervalList.length; i++)
if (MaxPrice < IntervalPrice[i]/(IntervalList[i][1]-IntervalList[i][0]))
{
MaxPrice=IntervalPrice[i]/(IntervalList[i][1]-IntervalList[i][0]);
bestDeal=i;
}
System.out.println("BestDeal = " + IntervalList[bestDeal][0] + "," + IntervalList[bestDeal][1]);
}
};
```

```
static int memo[];
public static boolean intersect(Interval i2, Interval i1){
return i2.s >= i1.s && i2.s <= i1.e;
}
public static int maxPrice(int i, Interval[] in, int last,int[] prices) {
if(i >= in.length)
return 0;
if(memo[last] != -1)return memo[last];
if(intersect(in[i], in[last])){
return memo[last] = maxPrice(i + 1, in, last, prices);
}
return memo[last] = Math.max(prices[i] + maxPrice(i + 1, in, i, prices), maxPrice(i + 1, in, last, prices));
}
public static int maxPrice(Interval[] in, int[] prices) {
memo = new int[prices.length];
Arrays.fill(memo, -1);
return maxPrice(0, in, 0,prices);
}
public static void main(String[] args) {
Solution s = new Solution();
Interval []in = {s.new Interval(0, 0), s.new Interval(1, 3), s.new Interval(2, 3), s.new Interval(3, 5)};
int[]p = {0, 2,10,5};
System.out.println(maxPrice(in, p));
}
```

I think you are over complicating the problem. Why not simply look for the best:

```
function selectRenter($offers) {
$maxIndex = -1;
$maxProfit = 0;
foreach($offers => $offer as $details) {
$s = $details[0];
$e = $details[1];
$p = $details[2];
if($p * ($e - $s + 1) > $maxProfit) {
$maxProfit = $p * ($e - $s + 1);
$maxIndex = $offer;
}
}
return $maxIndex;
}
```

in python considering time intersection

def sort_by_start_date(arr):

return sorted(arr, key=lambda x: x[0]) # first idx is start date

def max_profit(requests):

global stacks, moneys

requests = sort_by_start_date(requests)

stacks = []

moneys = [] # should match number of stacks

max_money = requests[0][-1]

max_money_idx = 0

for start, end, money in requests:

time = start # current time is the start date

# initialisation

if len(stacks) == 0:

stacks.append([( start, end, money )])

moneys.append( money )

continue

# we loop through each scenario

for i in range(len(stacks)):

stack = stacks[i]

# see whether we can push this chunk into the stack

prev_start, prev_end, prev_money = stack[-1]

#print("here", time, end, money)

#print(prev_start, prev_end, prev_money)

#print(stacks)

if prev_end < time : # strictly less than

stack.append(( start, end, money ))

moneys[i] += money

# keep track of max money

if moneys[i] > max_money:

max_money = moneys[i]

max_money_idx = i

else: # this means it is a new scenario

# but there is a case we should not consider

# which is new block finishes after existing block

# with less money

if end >= prev_end and money <= prev_money:

continue # we discard this

# in this case we will need to create a new stack

# to keep track of new scenario

# new_stack = [ item for item in stacks[:-1] ] # last block is conflict -> not true could be multiple

# copy only those that dont conflict, ie end date < time

new_stack = [ item for item in stack if item[-1] < time ]

new_money = moneys[i] - prev_money + money

new_stack.append(( start, end, money ))

stacks.append(new_stack)

moneys.append(new_money)

# keep track of max money

if new_money > max_money:

max_money = new_money

max_money_idx = len(stacks)-1 # last index after appending

for money, stack in zip(moneys, stacks):

print("$%d"% money, stack )

return max_money, stacks[max_money_idx]

requests = [

(1, 10, 10),

(2,3, 2),

(7,10,8),

(1,3,5),

(8,10,7),

(4,6,8)

]

print (max_profit(requests))

public class BestDeal{

public static void main(String []args){

int [][] IntervalList = {{1,2},{2,4},{4,8}};

int [] IntervalPrice = {10, 30, 25};

int MaxPrice = 0;

int bestDeal =0;

for (int i=0 ;i< IntervalList.length; i++)

if (MaxPrice < IntervalPrice[i]/(IntervalList[i][1]-IntervalList[i][0]))

{

MaxPrice=IntervalPrice[i]/(IntervalList[i][1]-IntervalList[i][0]);

bestDeal=i;

}

System.out.println("BestDeal = " + IntervalList[bestDeal][0] + "," + IntervalList[bestDeal][1]);

}

};

""

THIS IMPLEMENTATION IS JUST A PYTHON VERSION OF AN OLDER POST WITH SOME EXPLANATION

Input: Two arrays. One for interval and other for the price of each interval.

Compute: We need to find the best value for the time duration we rent out the car, such that

there is no intersection between the time intervals. For simplicity I have just use discrete time interval with no overlap.

""

def bestDeal():

## [s,e]

interval = ((1,2),(2,4),(4,10))

price_interval = (30,20,100)

max_price = 0

best_interval = 0

for i in range(0,len(interval)):

price_comp = price_interval[i]/(interval[i][-1] - interval[i][0])

if max_price < price_comp:

max_price = price_comp

best_interval = i

print('Best Interval',interval[i],'at $',price_interval[i])

Thanks for sharing !

- Ankita August 23, 2018Here you have done is split in two cases:

- If two intervals do not intersect,then either consider it or do not consider it

- If they intersect,then without considering

Please let me know if I understood your logic right.

Also , time complexity will be 2^n of recursive algo, right?