Quick Overview

This question evaluates a candidate's understanding of numerical methods, floating-point precision, and implementation of approximate functions when producing a square root rounded to one decimal place.

Compute square root to 1 decimal

Company: Uber

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem Given a non-negative real number `x`, implement a function `sqrt1dp(x)` that returns \(\sqrt{x}\) rounded (or truncated—clarify with interviewer) to **one digit after the decimal point**. ### Requirements - Do **not** call a built-in square root function. - Your answer must be accurate to **1 decimal place** (e.g., error < 0.05 if rounding). - Discuss how you would **optimize** the algorithm (time complexity and convergence). ### Examples - `x = 2` → `1.4` - `x = 9` → `3.0` - `x = 0` → `0.0` ### Clarifications to ask - Rounding vs truncation to 1 decimal. - Input range (e.g., up to 1e9?) and whether `x` can be non-integer. - Acceptable error tolerance if not using decimal formatting.

Quick Answer: This question evaluates a candidate's understanding of numerical methods, floating-point precision, and implementation of approximate functions when producing a square root rounded to one decimal place.

Given a non-negative real number `x`, implement `sqrt1dp(x)` that returns the square root of `x` **rounded to one digit after the decimal point**, WITHOUT calling any built-in square-root function (no `math.sqrt`, `Math.sqrt`, `**0.5`, `pow(x, 0.5)`, etc.). The result must be accurate to 1 decimal place (rounding error < 0.05). **Approach:** Use binary search (or Newton's method) to converge on the root, then round to one decimal. Binary search over the interval `[0, max(1, x)]`: each iteration halves the candidate window, so `~60` iterations already drives the error far below `1e-9`. Newton's iteration `g = (g + x/g) / 2` converges quadratically and is even faster. **Examples:** - `sqrt1dp(2)` → `1.4` - `sqrt1dp(9)` → `3.0` - `sqrt1dp(0)` → `0.0` - `sqrt1dp(10)` → `3.2`

Constraints

  • 0 <= x <= 1e9
  • x may be a non-integer real number
  • Do not call any built-in square-root function
  • Result must be accurate to 1 decimal place (error < 0.05)

Examples

Input: (2,)

Expected Output: 1.4

Explanation: sqrt(2) = 1.41421..., rounds to 1.4

Input: (9,)

Expected Output: 3.0

Explanation: Perfect square: sqrt(9) = 3.0

Hints

  1. The root of x lies in [0, max(1, x)] — note that for 0 < x < 1 the root is GREATER than x, which is why the upper bound is max(1, x), not x.
  2. Binary search: pick mid; if mid*mid < x the root is higher, else it is lower. Each iteration halves the error, so a fixed iteration count (e.g. 100-200) guarantees far better than 1-decimal precision.
  3. Newton's method converges faster: start with a guess g and repeat g = (g + x/g) / 2 until it stops changing.
  4. Only round to 1 decimal AFTER converging to full precision — rounding early loses accuracy. Use round(root, 1).

Loading coding console...