Compute square root with precision
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Quick Answer: This question evaluates a candidate's understanding of numerical methods for root finding, floating-point precision control, and algorithmic time complexity analysis when computing square roots without built-in functions.
Constraints
- 0 <= val <= 10^12
- 0 <= precise <= 6
- Do not use any built-in square-root function
Examples
Input: (10, 3)
Expected Output: 3.162
Explanation: `sqrt(10) ≈ 3.162277...`, and truncating to 3 decimal places gives `3.162`.
Input: (2, 5)
Expected Output: 1.41421
Explanation: `sqrt(2) ≈ 1.414213...`, and truncating to 5 decimal places gives `1.41421`.
Input: (0, 4)
Expected Output: 0.0
Explanation: The square root of 0 is exactly 0, regardless of the requested precision.
Input: (27, 0)
Expected Output: 5.0
Explanation: `sqrt(27) ≈ 5.196...`, and truncating to 0 decimal places gives `5.0`.
Input: (99980001, 4)
Expected Output: 9999.0
Explanation: `99980001 = 9999^2`, so the square root is exactly `9999`.
Hints
- Binary search works because if `x*x <= val`, then every number smaller than `x` also satisfies the condition.
- To avoid floating-point precision issues, scale the problem: finding `sqrt(val)` to `precise` decimal places is equivalent to finding the integer square root of `val * 10^(2 * precise)`.