## Goldman Sachs Interview Question

Country: United States

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

Thanks for sharing !
Here 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

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

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

Yes, for every interval we have two options either to include that or not .
This will lead to the exponential Solution of 2^n.

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

``````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]-IntervalList[i]))
{
MaxPrice=IntervalPrice[i]/(IntervalList[i]-IntervalList[i]);
bestDeal=i;
}

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

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

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

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

``````memo = new int[p.length];
memo = p;
for(int i = 1; i < p.length; i++){
for(int j = i - 1; j >= 0; j--){
if(intersect(in[i],in[j])){
memo[i] = Math.max(memo[i], p[i]);
}else{
memo[i] = Math.max(memo[i], memo[j] + p[i]);
}
}
}``````

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

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;
\$e = \$details;
\$p = \$details;
if(\$p * (\$e - \$s + 1) > \$maxProfit) {
\$maxProfit = \$p * (\$e - \$s + 1);
\$maxIndex = \$offer;
}
}
return \$maxIndex;
}``````

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

@Ankita

Yes, This what the solutions do.

The complexity is O(N^2) because the array memo caches the already calculated result.

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

Isn't this just a variation of best time to sell stock given input array that contains startring prices?

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

You can do it in n*log(n)

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

in python considering time intersection

def sort_by_start_date(arr):
return sorted(arr, key=lambda x: x) # 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[-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:

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

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

using n stacks to store each scenario

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

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]-IntervalList[i]))
{
MaxPrice=IntervalPrice[i]/(IntervalList[i]-IntervalList[i]);
bestDeal=i;
}

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

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

""
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])
if max_price < price_comp:
max_price = price_comp
best_interval = i
print('Best Interval',interval[i],'at \$',price_interval[i])

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

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.

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.