Implement Portfolio Trading Optimizer
Company: Point72
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given an array `prices`, where `prices[i]` is the price of one stock on day `i`.
You may perform multiple buy/sell transactions over the period, but you may hold at most one share at any time. Each transaction must buy before it sells. Your goal is to maximize total profit and report the optimal set of non-overlapping transactions.
Input constraints:
- `0 <= len(prices) <= 30000`
- `0 <= prices[i] <= 10000`
- Every price must be a non-negative integer.
Implement the following functions:
```python
def validate_prices(func):
"""
Decorator that validates the input prices list before calling func.
It should reject invalid inputs according to the constraints.
"""
pass
@validate_prices
def find_transactions(prices):
"""
Return the optimal transactions as a list of tuples:
(buy_day, buy_price, sell_day, sell_price, profit)
If no profitable transaction exists, return an empty list.
"""
pass
def generate_report(prices):
"""
Return a human-readable report containing one line per transaction
and a final line with total profit.
"""
pass
```
Example:
```python
prices = [7, 1, 5, 3, 6, 4]
```
One valid report is:
```text
buy_day=1 buy_price=1 sell_day=2 sell_price=5 profit=4
buy_day=3 buy_price=3 sell_day=4 sell_price=6 profit=3
total_profit=7
```
Your implementation should be efficient enough for the maximum input size.
Quick Answer: This question evaluates algorithmic problem-solving, array processing, input validation via decorators, and the ability to produce concise transaction reports for maximizing non-overlapping buy/sell profits.
You are given a list `prices`, where `prices[i]` is the stock price on day `i`. You may complete as many buy/sell transactions as you want, but you may hold at most one share at a time, and each buy must happen before its matching sell. Your task is to return a human-readable report of the transactions that achieve the maximum total profit.
To make the answer deterministic when multiple optimal solutions exist, use this rule while scanning from left to right:
1. Skip every flat-or-falling stretch and buy at the last local minimum.
2. Continue through the entire flat-or-rising stretch and sell at the last local maximum.
3. Repeat until the end of the list.
Each transaction line must have the format:
`buy_day=X buy_price=A sell_day=Y sell_price=B profit=P`
The final line must be:
`total_profit=T`
If no profitable transaction exists, return only `total_profit=0`.
Your implementation must also validate the input the same way a `validate_prices` decorator would:
- `prices` must be a list
- `0 <= len(prices) <= 30000`
- every element must be an integer
- `0 <= prices[i] <= 10000`
If the input is invalid, raise `ValueError`.
Constraints
- 0 <= len(prices) <= 30000
- 0 <= prices[i] <= 10000
- Every price must be a non-negative integer
- Raise ValueError if the input violates the constraints
Examples
Input: [7, 1, 5, 3, 6, 4]
Expected Output: "buy_day=1 buy_price=1 sell_day=2 sell_price=5 profit=4\nbuy_day=3 buy_price=3 sell_day=4 sell_price=6 profit=3\ntotal_profit=7"
Explanation: Buy at day 1 and sell at day 2 for profit 4, then buy at day 3 and sell at day 4 for profit 3. Total profit is 7.
Input: [1, 2, 3, 4, 5]
Expected Output: "buy_day=0 buy_price=1 sell_day=4 sell_price=5 profit=4\ntotal_profit=4"
Explanation: The whole array is one rising run, so the deterministic answer is a single transaction from the first day to the last day.
Input: [7, 6, 4, 3, 1]
Expected Output: "total_profit=0"
Explanation: Prices never rise after a buy, so no profitable transaction exists.
Input: []
Expected Output: "total_profit=0"
Explanation: With no prices, there are no transactions.
Input: [3, 3, 5, 0, 0, 3, 1, 4]
Expected Output: "buy_day=1 buy_price=3 sell_day=2 sell_price=5 profit=2\nbuy_day=4 buy_price=0 sell_day=5 sell_price=3 profit=3\nbuy_day=6 buy_price=1 sell_day=7 sell_price=4 profit=3\ntotal_profit=8"
Explanation: Using the required tie-breaking rule, buy on the last day of each flat valley and sell on the last day of each flat/rising peak.
Input: [5]
Expected Output: "total_profit=0"
Explanation: A single day cannot form a buy/sell transaction.
Hints
- An optimal strategy can be found in one left-to-right scan by identifying local minima and local maxima.
- If prices keep rising across consecutive days, merging them into one buy-at-valley / sell-at-peak transaction preserves the same total profit.