Minimum Stock Supply
Filed under Goldman Sachs
Free read 3 of 3Confirm that stock quantities are unlimited and that the objective is to minimize the total count of stocks.
The question
Given share stock equations and infinite supply options for certain items, find the minimum number of stocks needed to meet a target value, akin to the coin change problem.
Constraints
- Stock supply options are positive integers.
- Target value is a non-negative integer.
- Return -1 or a specific indicator if the target cannot be met.
Examples
- Input
- stocks = [1, 2, 5], target = 11
- Output
- 3
- Why
- 11 can be formed with 5 + 5 + 1, requiring 3 stocks.
Approach
Confirm that stock quantities are unlimited and that the objective is to minimize the total count of stocks.
Recursively explore all combinations of stock additions to reach the target, resulting in exponential time complexity.
Use bottom-up Dynamic Programming. Maintain an array dp where dp[i] represents the minimum stocks needed to reach target i, transitioning from dp[i - stock].
Target is 0, empty stock list, or target smaller than all stock values.
Solution
O(target * len(stocks)) time, O(target) space
def min_stocks(stocks, target):
dp = [float('inf')] * (target + 1)
dp[0] = 0
for i in range(1, target + 1):
for s in stocks:
if i - s >= 0:
dp[i] = min(dp[i], dp[i - s] + 1)
return dp[target] if dp[target] != float('inf') else -1
Tips
- What they are testing: Test with a target of 0, targets impossible to reach with given stock values, and single stock availability.
- Common mistake: Using a greedy approach instead of dynamic programming, which fails for non-canonical coin/stock systems.
Related Goldman Sachs questions
Collected from public candidate posts and coding forums. Updated Nov 2026.