Katkat

Solve Search Speed and String Product

ByteDanceSoftware Engineer · Onsite

Last 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:

  • 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:

Input: num1 = "123", num2 = "456"
Output: "56088"

Write several test cases, including edge cases, and explain the algorithmic complexity.