Katkat
Back

Approximate a Square Root Across Values Above and Below One

OracleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests binary search on a continuous search space and the ability to handle numerical precision for numbers both greater than and less than one.

Problem Statement

Implement a function my_sqrt(x) that calculates the principal square root of a non-negative real number x and returns it rounded to a precision of 1e-7.

You cannot use the built-in library functions like math.sqrt() or exponentiation operators (e.g., ** 0.5). Your solution must work for all non-negative floats, including values between 0 and 1 (e.g., 0.25), where the square root is greater than the input.

Function Signature

def my_sqrt(x: float) -> float:

Constraints

  • 0 <= x <= 1e9
  • The precision requirement is abs(result^2 - x) < 1e-7.

Examples

Example 1: Input: x = 4.0 Output: 2.0

Example 2: Input: x = 0.25 Output: 0.5

Example 3: Input: x = 2.0 Output: 1.41421356

Edge Cases

  • x = 0
  • x = 1
  • 0 x in this range.

Hints

Hint 1

Since the square root function is monotonically increasing, you can use binary search to narrow down the range.

Hint 2

For values of x between 0 and 1, the square root will be in the range [x, 1], whereas for x > 1, the square root is in the range [1, x].

Hint 3

Set your search range to [0, max(1, x)] to cover all possible inputs safely, and continue narrowing the window until the difference between mid*mid and x is less than the error threshold.

Follow-up questions

  • How would you optimize the solution if you needed to perform this calculation millions of times?
  • Could you implement this using Newton's Method? How does its convergence speed compare to binary search?
  • What would happen if the input were an extremely large float, potentially causing overflow in `mid * mid`?