Solve Search Speed and String Product
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are asked to solve two coding problems.
### Problem 1: Find the Minimum Constant Processing Speed
You are given an array `piles`, where `piles[i]` is the number of items in the `i`-th pile, and an integer `h`, the maximum number of hours available.
Each hour, you may choose exactly one non-empty pile and process up to `k` items from that pile. If the pile has fewer than `k` items remaining, you finish that pile during the hour and do not use the remaining capacity on another pile.
Return the minimum positive integer speed `k` such that all piles can be processed within `h` hours.
Example:
```text
Input: piles = [3, 6, 7, 11], h = 8
Output: 4
```
Explain both a brute-force approach and an optimized approach. For the optimized approach, analyze the time complexity carefully.
### Problem 2: Compute the Product of Two Large Non-Negative Integers
You are given two non-negative integers `num1` and `num2` represented as decimal strings. The integers may be too large to fit into built-in numeric types.
Return their product as a decimal string.
Constraints:
- `num1` and `num2` contain only digits `0-9`.
- Neither string contains leading zeros unless the number is exactly `"0"`.
- You may not directly convert the full strings into built-in integer types.
Example:
```text
Input: num1 = "123", num2 = "456"
Output: "56088"
```
Write several test cases, including edge cases, and explain the algorithmic complexity.
Quick Answer: This pair of problems evaluates algorithm design and implementation skills, focusing on efficient search/optimization for constrained processing speed and manual arbitrary-precision string multiplication for very large integers.
Part 1: Find the Minimum Constant Processing Speed
You are given a list of pile sizes `piles`, where `piles[i]` is the number of items in the `i`-th pile, and an integer `h` representing the maximum number of hours available. In each hour, you may choose exactly one non-empty pile and process up to `k` items from it. If a pile has fewer than `k` items left, you finish that pile during the hour, and any unused capacity is lost.
Return the minimum positive integer `k` such that all piles can be processed within `h` hours.
A brute-force idea is to try every speed from `1` to `max(piles)`, but that can be too slow for large inputs. Design an efficient solution.
Constraints
- 1 <= len(piles) <= 100000
- 1 <= piles[i] <= 1000000000
- len(piles) <= h <= 100000000000000
Examples
Input: ([3, 6, 7, 11], 8)
Expected Output: 4
Explanation: At speed 4, the required hours 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 speed must be at least the largest pile size.
Hints
- For a fixed speed `k`, the hours needed for a pile of size `p` is `ceil(p / k)`.
- If a speed `k` works, then every speed larger than `k` also works. That monotonic property suggests binary search.
Part 2: Compute the Product of Two Large Non-Negative Integers
You are given two non-negative integers `num1` and `num2` represented as decimal strings. The values may be too large to fit into built-in numeric types.
Return their product as a decimal string.
You may not directly convert the full input strings into built-in integer types. Instead, simulate multiplication the way you would do it by hand.
Constraints
- 1 <= len(num1), len(num2) <= 200
- `num1` and `num2` contain only characters '0' through '9'
- Neither input has leading zeros unless the value is exactly "0"
- You may not convert the entire strings to built-in integer types
Examples
Input: ("123", "456")
Expected Output: "56088"
Explanation: Standard example: 123 × 456 = 56088.
Input: ("0", "52")
Expected Output: "0"
Explanation: If either number is zero, the product is zero.
Hints
- The result of multiplying numbers with lengths `m` and `n` has at most `m + n` digits.
- When multiplying digits from right to left, each pair contributes to positions `i + j` and `i + j + 1` in a result array because of carry.