How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding 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.

Company: Uber

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Implement two Python functions: (1) sqrt_newton(x, tol=1e-12) returning the principal square root for float x ≥ 0, without using sqrt/pow; handle x ∈ [0, 1e308], return 0 for x=0, +∞ for x=+∞, and raise ValueError for x<0. Choose a numerically stable initial guess that avoids overflow/underflow for very large/small x, and stop when |y^2−x|/max(x,1) ≤ tol or after 100 iterations. Ensure no division-by-zero and discuss how to guard against catastrophic cancellation. (2) isqrt_bisect(n) returning ⌊√n⌋ for integer n with 0 ≤ n < 2^63, using binary search with O(log n) iterations and no intermediate overflow (e.g., compare mid ≤ n//mid instead of mid*mid ≤ n). Then answer: a) Prove Newton’s method for √x is quadratically convergent near the root; b) For worst-case x in [1e−12, 1e12] with y0 = max(1, x), estimate the iterations to reach tol and justify; c) Compare per-iteration cost and total operations versus binary search for 64-bit n; d) Briefly outline how you would extend sqrt_newton to support complex results for x<0 under IEEE‑754 and why naive branching can be unsafe.

Quick Answer: 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.

sqrt_newton — principal square root via Newton's method

Implement `sqrt_newton(x, tol=1e-12)` returning the principal square root of a nonnegative float `x` WITHOUT using `sqrt` or `pow`. Requirements: - Domain: `x` in `[0, 1e308]`. - Special cases: return `0.0` for `x == 0`; return `+inf` for `x == +inf`; raise `ValueError` for `x < 0`. - Numerical stability: pick an initial guess that avoids overflow/underflow for very large or very small `x` (scale via the binary exponent, e.g. `frexp`). - Iteration: Newton update `y <- 0.5 * (y + x/y)`; stop when `|y^2 - x| / max(x, 1) <= tol` or after 100 iterations. - Robustness: never divide by zero, and guard against catastrophic cancellation in the stopping test by evaluating `|y^2 - x|` as `|y| * |y - x/y|` (reuse the quotient `u = x/y`). Return the float `y`. (Tests use exactly-representable perfect squares where the iteration converges to the exact value.)

Constraints

0 <= x <= 1e308 (IEEE-754 double)
tol > 0 (default 1e-12)
Do not use sqrt or pow
Raise ValueError for x < 0; return 0.0 for x == 0; return +inf for x == +inf

Examples

Input: (0.0,)

Expected Output: 0.0

Explanation: Special case: sqrt(0) is exactly 0.0.

Input: (1.0,)

Expected Output: 1.0

Explanation: sqrt(1) = 1; the guess starts at 1 and the residual is already 0.

Input: (4.0,)

Expected Output: 2.0

Explanation: Perfect square; Newton converges to the exact double 2.0.

Input: (16.0,)

Expected Output: 4.0

Explanation: Power-of-two perfect square; frexp-scaled start lands exactly on 4.0.

Input: (64.0,)

Expected Output: 8.0

Explanation: sqrt(64) = 8.0 exactly.

Input: (1024.0,)

Expected Output: 32.0

Explanation: Larger perfect square (2^10); converges to exact 32.0, exercising the scaled initial guess.

Input: (0.25,)

Expected Output: 0.5

Explanation: Sub-unit input (x < 1): normalizer max(x,1)=1; result 0.5 exactly.

Input: (0.0625,)

Expected Output: 0.25

Explanation: Small input edge case (1/16); exact result 0.25, confirming no underflow in the initial guess.

Hints

Decompose x = m * 2**e with frexp; an initial guess of 2**(e//2) keeps you within a factor of sqrt(2) of the root, so no overflow even for x ~ 1e308.
The Newton step for f(y)=y^2-x is y <- 0.5*(y + x/y); reuse u = x/y for both the stopping test and the update.
Compute the residual as |y|*|y - x/y| instead of |y*y - x|: this avoids overflow of y*y near 1e154 and avoids cancellation between two large near-equal numbers.

isqrt_bisect — integer floor square root via binary search

Implement `isqrt_bisect(n)` returning `floor(sqrt(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` so the product never overflows. - Use a tight upper bound derived from `n.bit_length()` to roughly halve the iteration count. Return the integer floor of the square root.

Constraints

0 <= n < 2**63
O(log n) iterations
Must not compute mid*mid (overflow); compare mid <= n // mid

Examples

Input: (0,)

Expected Output: 0

Explanation: Edge case: floor(sqrt(0)) = 0 via the n<2 short-circuit.

Input: (1,)

Expected Output: 1

Explanation: Edge case: floor(sqrt(1)) = 1.

Input: (2,)

Expected Output: 1

Explanation: Non-perfect square: floor(sqrt(2)) = 1.

Input: (3,)

Expected Output: 1

Explanation: floor(sqrt(3)) = 1 (just below the next perfect square).

Input: (4,)

Expected Output: 2

Explanation: Perfect square boundary: floor(sqrt(4)) = 2.

Input: (8,)

Expected Output: 2

Explanation: floor(sqrt(8)) = 2 (8 < 9).

Input: (15,)

Expected Output: 3

Explanation: floor(sqrt(15)) = 3 (just below 16).

Input: (16,)

Expected Output: 4

Explanation: Perfect square: floor(sqrt(16)) = 4.

Input: (24,)

Expected Output: 4

Explanation: floor(sqrt(24)) = 4 (16 <= 24 < 25).

Input: (1000000,)

Expected Output: 1000

Explanation: Large perfect square: floor(sqrt(1_000_000)) = 1000.

Input: (9223372036854775807,)

Expected Output: 3037000499

Explanation: Boundary n = 2**63 - 1; floor(sqrt) = 3037000499. Confirms the mid <= n // mid guard prevents overflow at the largest allowed input.

Hints

For 0 and 1, floor(sqrt(n)) == n, so short-circuit n < 2.
From k = n.bit_length(), floor(sqrt(n)) < 2**ceil(k/2); start hi at 2**((k+1)//2) to cut iterations.
Binary search on the candidate root; the overflow-safe predicate is mid <= n // mid, which is equivalent to mid*mid <= n for positive mid.

Quick Overview