Compute square root with precision
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Given a non-negative integer `val` and a non-negative integer `precise`, compute the square root of `val` without using any built-in square-root function. Return a result whose absolute error is at most `10^-precise`. Also explain the time complexity of your approach.
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.
Given two non-negative integers `val` and `precise`, compute the square root of `val` without using any built-in square-root operation. Return the result truncated to exactly `precise` digits after the decimal point as a float. This guarantees that the absolute error is less than `10^-precise`. Be prepared to explain the time complexity of your approach.
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`.
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)`.