Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Maximize Capital

Problem Statement

Given a set of investment projects with their respective profits, we need to find the most profitable projects. We are given an initial capital and are allowed to invest only in a fixed number of projects. Our goal is to choose projects that give us the maximum profit. Write a function that returns the maximum total capital after selecting the most profitable projects.

We can start an investment project only when we have the required capital

.....

.....

.....

Like the course? Get enrolled and start learning!
W

Will

· 4 years ago

The time complexity should maybe just be simplified (to avoid confusion with other sources i.e. Leetcode Q502: IPO) from: O(NlogN + KlogN) to O(NlogN).

Because in the worst/ largest case of 'K' (num of projects), since we can't re-pick projects, K's worst case would just be N, since we can't pick more projects than there are projects available to choose from (since projects are not un-bounded). Therefore, it's really O(NlogN + NlogN) in the worst case 'K' value, which is O(NlogN).

Show 1 reply
M

Michelle Cheng

· 4 years ago

The problem statement is a little confusing. One has to look closely at the examples to understand one unintuitive aspect of the problem: capital doesn't get used up when invested. It would be nice if that statement was included in the problem. Makes it much a much simpler problem to solve.

Show 2 replies
L

lejafilip

· 2 years ago

If yes, then should be More examples.

Show 2 replies
M

Micky M

· 4 years ago

It's not clear from the problem statement that the capital array will always be a sequence of array indices [1,2,3,4,5...], as the solution suggests that it is. The problem statement could be more explicit.

Show 1 reply
H

hj3yoo

· 4 years ago

There seems to be an implicit assumption in the solution that the problem statement doesn't specify: wouldn't this greedy algorithm work only if you can invest in one project at a time?

What if investing in two smaller project will yield higher profit than investing in the project that yields the highest profit?

ex: capitals=[1,1,2], profits=[3,4,6], numberOfProjects=2, initialCapital=2

Show 2 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

from heapq import *

class Solution:
  def findMaximumCapital(self, capital, profits, numberOfProjects,
  initialCapital):
    
    max_heap = [(-profits[i], capital[i]) for i in range(len(profits))]
    heapify(max_heap)

    total_capital = initialCapital
    for _ in range(numberOfProjects):
      temp = []
      while max_heap:
        prof, cap = heappop(max_heap)
        if -prof + total_capital >= cap and cap <= total_capital:
          total_capital += -prof
          break
        else:
          temp.append((prof, cap))
      
      for tup in temp:
        heappush(max_heap, tup)

    return total_capital
R

rgithinji

· 2 years ago

The solution breaks if the value of an element (or elements) exceed the length of the array. An element is picked from the heap and used to search for a corresponding profit value by position and kaboooom! ArrayOutOfBounds exception.This makes it a special case solution that only works with the defined use cases. I'd rather a general solution with worse runtime complexity than a brittle special case solution

C

Chaitra

· 2 years ago

Why are we adding the indexes instead of the value in our heaps?

Parikshit Murria

Parikshit Murria

· a year ago

import java.util.*;

class Solution {
	  public static int findMaximumCapital(int[] capital, int[] profits,int numberOfProjects, int initialCapital) {
	  
	  //Two Queues MinHeap for Capital and MaxHeap for Profit
    Queue<int[]> capitalHeap = new PriorityQueue<>((a,b) -> a[0] - b[0]);
    Queue<int[]> profitHeap = new PriorityQueue<>((a,b) -> b[1] - a[1]);
    
    //Popoulate Capital Heap with array objects containing both capital and profit.
    for (int i=0; i<capital.length; i++) {
	    int [] temp = new int[2];
      temp[0] = capital[i];
      temp[1] = profits[i]; 
      capitalHeap.offer(temp);
    }
    
    //Initialize count and totalCapital
    int count = 0;
    int totalCapital = initialCapital;
    
    //Run till the required numberOfProjects are picked
Nitin Sharma

Nitin Sharma

· 9 months ago

The test case assumes, we cannot repeat the projects, while the problem description / constraints does not mention such assumption