Goldman Sachs Interview Question


Country: United States




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

- jack September 14, 2018 | Flag Reply
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));
}

- Abdelrahman August 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

memo = new int[p.length];
		memo[0] = p[0];
		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]);
				}
			}
		}

- Abdelrahman August 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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

Please let me know if I understood your logic right.
Also , time complexity will be 2^n of recursive algo, right?

- Ankita August 23, 2018 | Flag Reply
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[0];
		$e = $details[1];
		$p = $details[2];
		if($p * ($e - $s + 1) > $maxProfit) {
			$maxProfit = $p * ($e - $s + 1);
			$maxIndex = $offer;
		}
	}
	return $maxIndex;
}

- Khoubeib Bouthour August 23, 2018 | Flag Reply
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.

- Abdelrahman August 23, 2018 | Flag Reply
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?

- StackSmasher AKA KhurrumWala August 26, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do it in n*log(n)

- maoz August 28, 2018 | Flag Reply
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[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))

- Anonymous September 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using n stacks to store each scenario

- Anonymous September 03, 2018 | Flag Reply
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][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]);
}
};

- jack September 14, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More