Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Maximize Capital

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

If yes, then should be More examples.

A

Anonymous

· 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

A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 5 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

Reading Progress

0%

Vote for new content