Coding questions · ByteDance

Compute square root with precision

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 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.

Compute Square Root with Precision

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

Example 1

Input: (10, 3)
Output: 3.162

Explanation: sqrt(10) ≈ 3.162277..., and truncating to 3 decimal places gives 3.162.

Example 2

Input: (2, 5)
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).