How should I practice Square Root Function?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Citadel phone screen problems in FastPrep.

Is Square Root Function associated with Citadel?

FastPrep tags this as a Citadel phone screen coding practice problem when the problem catalog has that company and stage context.

Square Root Function

Citadel● MediumFULLTIMEPHONE SCREEN

Problem statement

Write a function that returns the square root of a number x.

You can use the four basic operations: add, subtract, multiply and divide. Do not call a built-in square root or power function. The tests check only the returned value, so they cannot catch a built-in call. Keeping to this rule is up to you.

An answer is accepted when its distance from the true square root is at most 10^-6 * max(1, root). So the allowed error is 10^-6 when the root is at most 1, and 10^-6 times the root when the root is above 1.

Interview follow-up

This follow-up came up in the interview. It is not part of the judged function, and the editorial covers it.

What if we are sure that the input number is an integer?

Function

squareRoot(x: double) → double

Examples

Example 1

x = 2.0return = 1.4142135623730951

1.4142135623730951 * 1.4142135623730951 is about 2. The root is above 1, so the allowed error here is 10^-6 times the root, about 1.4 * 10^-6.

Example 2

x = 0.25return = 0.5

0.5 * 0.5 = 0.25. The root is larger than the input here, so a search for the root cannot stop at x.

Example 3

x = 16.0return = 4.0

4 * 4 = 16, so this integer input has an exact root.

Constraints

x = 0 or 10^-6 <= x <= 10^12
x and the result are double-precision numbers.