Solve Search Speed and String Product
ByteDanceSoftware Engineer · OnsiteLast updated
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.
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:
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:
num1andnum2contain only digits0-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:
Input: num1 = "123", num2 = "456"
Output: "56088"
Write several test cases, including edge cases, and explain the algorithmic complexity.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.