How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Uber during technical interviews.

Implement sqrt with Newton vs binary search

Quick Overview

This question evaluates numerical methods and algorithmic robustness, testing understanding of Newton’s method for root-finding, floating‑point stability and IEEE‑754 edge cases, and integer binary-search techniques for exact floor square roots within the Coding & Algorithms domain for a Data Scientist role.

Implement numerically robust square-root routines and analyze convergence

Task 1 — sqrt_newton(x, tol=1e-12)

Implement a Python function that returns the principal square root of a nonnegative float x without using sqrt or pow.

Requirements:

Input domain: x ∈ [0, 1e308].
Special cases: return 0.0 for x = 0; return +∞ for x = +∞; raise ValueError for x < 0.
Numerical stability: choose an initial guess that avoids overflow/underflow for very large/small x. Do not use sqrt/pow.
Iteration: use Newton's method and stop when |y^2 − x| / max(x, 1) ≤ tol or after 100 iterations.
Robustness: avoid division by zero and guard against catastrophic cancellation in the stopping test.

Task 2 — isqrt_bisect(n)

Implement a Python function that returns ⌊√n⌋ for an integer n with 0 ≤ n < 2^63 using binary search.

Requirements:

Complexity: O(log n) iterations.
No intermediate overflow: compare mid ≤ n // mid instead of mid*mid ≤ n.

Theory

Answer the following:

a) Prove Newton’s method for √x is quadratically convergent near the root.

b) For worst-case x in [1e−12, 1e12] with starting guess y0 = max(1, x), estimate the number of iterations needed to reach tol = 1e−12 (per the stop rule) and justify.

c) Compare per-iteration cost and total operations of Newton’s method versus binary search for 64-bit n.

d) Briefly outline how to extend sqrt_newton to support complex results for x < 0 under IEEE‑754 and why naïve branching can be unsafe.

Quick Overview

Task 1 — sqrt_newton(x, tol=1e-12)

Implement a Python function that returns the principal square root of a nonnegative float x without using sqrt or pow.

Requirements:

Input domain: x ∈ [0, 1e308].

Special cases: return 0.0 for x = 0; return +∞ for x = +∞; raise ValueError for x < 0.

Numerical stability: choose an initial guess that avoids overflow/underflow for very large/small x. Do not use sqrt/pow.

Iteration: use Newton's method and stop when |y^2 − x| / max(x, 1) ≤ tol or after 100 iterations.

Robustness: avoid division by zero and guard against catastrophic cancellation in the stopping test.

Theory

Answer the following:

a) Prove Newton’s method for √x is quadratically convergent near the root.

b) For worst-case x in [1e−12, 1e12] with starting guess y0 = max(1, x), estimate the number of iterations needed to reach tol = 1e−12 (per the stop rule) and justify.

c) Compare per-iteration cost and total operations of Newton’s method versus binary search for 64-bit n.

d) Briefly outline how to extend sqrt_newton to support complex results for x < 0 under IEEE‑754 and why naïve branching can be unsafe.

Implement sqrt with Newton vs binary search

Quick Overview

Implement numerically robust square-root routines and analyze convergence

Task 1 — sqrt_newton(x, tol=1e-12)

Task 2 — isqrt_bisect(n)

Theory

Solution

Submit Your Answer

Implement sqrt with Newton vs binary search

Quick Overview

Implement numerically robust square-root routines and analyze convergence

Task 1 — sqrt_newton(x, tol=1e-12)

Task 2 — isqrt_bisect(n)

Theory

Solution

Submit Your Answer