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

It's not the legit way to solve the problem I fear. For example, consider the test case

interval = ((1,10),(5,8),(4,14))

price_interval = (100,99,101)

Here we are getting the best profit per time in the second interval but in order to maximize the profit we rent it out in the 3rd interval even though that does not pay the best money per time.

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?