Solve stock and banana problems
Company: Apple
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Solve both coding problems below.
1. **Maximum single-transaction stock profit**: Given an array `prices` where `prices[i]` is the stock price on day `i`, return the maximum profit obtainable by choosing one day to buy and a later day to sell. If no profit is possible, return `0`.
2. **Minimum banana-eating speed**: Given an array `piles` where `piles[i]` is the number of bananas in pile `i`, and an integer `h` representing the total number of hours available, find the minimum integer eating speed `k` such that a monkey can finish all piles within `h` hours. In one hour, the monkey chooses one pile and eats up to `k` bananas from that pile.
For each problem, explain your algorithm and analyze time and space complexity.
Overview: This question evaluates algorithmic problem-solving skills related to array processing, optimization under constraints, and reasoning about performance trade-offs by presenting a maximum single-transaction stock profit problem and a minimum banana-eating speed problem.
Part 1: Maximum Single-Transaction Stock Profit
You are given an array `prices` where `prices[i]` is the stock price on day `i`. Choose one day to buy the stock and a later day to sell it. Return the maximum profit you can achieve from this single transaction. If no profitable transaction is possible, return `0`.
A good algorithm scans the array once, keeping track of the minimum price seen so far and the best profit seen so far.
Constraints
- 0 <= len(prices) <= 100000
- 0 <= prices[i] <= 100000
Examples
Input: ([7, 1, 5, 3, 6, 4],)
Expected Output: 5
Explanation: Buy at 1 and sell later at 6 for a profit of 5.
Input: ([7, 6, 4, 3, 1],)
Expected Output: 0
Explanation: Prices keep decreasing, so no profitable sell is possible.
Hints
- As you move from left to right, what is the only information you need from previous days to evaluate selling today?
- Keep track of the lowest price seen so far, then compare each current price against it.
Part 2: Minimum Banana-Eating Speed
You are given an array `piles` where `piles[i]` is the number of bananas in the `i`th pile, and an integer `h` representing the number of hours available. In one hour, the monkey chooses exactly one pile and eats up to `k` bananas from that pile. Find the minimum integer eating speed `k` such that all bananas can be eaten within `h` hours.
A strong approach uses binary search on the answer: if a given speed works, then any faster speed also works.
Constraints
- 1 <= len(piles) <= 10000
- 1 <= piles[i] <= 1000000000
- len(piles) <= h <= 1000000000
Examples
Input: ([3, 6, 7, 11], 8)
Expected Output: 4
Explanation: At speed 4, the hours needed are 1 + 2 + 2 + 3 = 8, which fits exactly.
Input: ([30, 11, 23, 4, 20], 5)
Expected Output: 30
Explanation: There are 5 piles and only 5 hours, so each pile must be finished in one hour. The largest pile requires speed 30.
Hints
- For a fixed speed `k`, compute the total hours by summing the ceiling of `pile / k` for each pile.
- If speed `k` is fast enough, then any speed greater than `k` is also fast enough. That monotonic property suggests binary search.
Community answers
Answer by thanosx222
class Solution:
def minEatingSpeed(self, piles: list[int], h: int) -> int:
n = len(piles)
l = 1
r = 0
for i in piles:
r = max(r, i)
def check(k: int):
count = 0
for i in piles:
count += (i + k - 1) // k
if count > h:
return False
return True
while l < r:
mid = (l + r) // 2
if check(mid):
r = mid
else:
l = mid + 1
return l