Solve Search Speed and String Product
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
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.
Input: ([30, 11, 23, 4, 20], 6)
Expected Output: 23
Explanation: Speed 23 works in 6 hours, while speed 22 needs 7 hours.
Input: ([1], 1)
Expected Output: 1
Explanation: Single-pile edge case.
Input: ([1000000000], 2)
Expected Output: 500000000
Explanation: To finish a pile of size 1,000,000,000 in 2 hours, the minimum speed is 500,000,000.
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
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.
Input: ("9", "9")
Expected Output: "81"
Explanation: Single-digit multiplication with carry.
Input: ("999", "999")
Expected Output: "998001"
Explanation: Tests repeated carries across multiple positions.
Input: ("1", "1")
Expected Output: "1"
Explanation: Smallest non-zero edge case.
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.