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 medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at J.P. Morgan.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at J.P. Morgan during technical interviews.

Implement Integer Square Root | J.P. Morgan Coding Question

Implement Integer Square Root

Company: J.P. Morgan

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a non-negative integer `x`, implement `sqrt(x)` and return the integer part of its square root, i.e., `floor(sqrt(x))`. Requirements: - Do not use a built-in square root function or exponent operator. - Your solution should handle large 32-bit signed integers without overflow. - Explain the time and space complexity. Examples: - `x = 4` returns `2`. - `x = 8` returns `2`, because `sqrt(8) = 2.828...` and the integer part is `2`. Expected approach: - First solve it using binary search. - Follow-up: discuss whether there is a more efficient practical method, such as Newton's method, and compare it with binary search.

Quick Answer: This question evaluates numerical algorithm design and integer arithmetic competence, including robustness for edge cases and overflow handling, and is categorized in the Coding & Algorithms domain.

Given a non-negative integer `x`, implement integer square root and return the integer part of its square root, i.e., `floor(sqrt(x))`. Requirements: - Do NOT use any built-in square root function or the exponent/power operator. - Handle large 32-bit signed integers without overflow (be careful with `mid * mid`). - Explain the time and space complexity. Examples: - `x = 4` returns `2`. - `x = 8` returns `2`, because `sqrt(8) = 2.828...` and the integer part is `2`. - `x = 0` returns `0`; `x = 1` returns `1`. Approach: Use binary search over the candidate answer range `[0, x]` (you can tighten the high bound to `x // 2` for `x >= 2`). For each `mid`, compare `mid * mid` against `x`. Follow-up: Newton's method converges faster in practice (quadratically) than binary search's logarithmic step count — worth discussing the trade-off.

Constraints

0 <= x <= 2147483647 (fits in a 32-bit signed integer)
Do not use any built-in square root function or exponent/power operator
Must not overflow: in Java/C++, compute mid * mid using a 64-bit type

Examples

Input: (4,)

Expected Output: 2

Explanation: 4 is a perfect square; floor(sqrt(4)) = 2.

Input: (8,)

Expected Output: 2

Explanation: sqrt(8) = 2.828..., integer part is 2.

Input: (0,)

Expected Output: 0

Explanation: Edge case: sqrt(0) = 0.

Input: (1,)

Expected Output: 1

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

Input: (2,)

Expected Output: 1

Explanation: Smallest non-perfect square > 1; floor(sqrt(2)) = 1.

Input: (9,)

Expected Output: 3

Explanation: Perfect square; floor(sqrt(9)) = 3.

Input: (15,)

Expected Output: 3

Explanation: sqrt(15) = 3.872..., integer part is 3 (just below the next perfect square 16).

Input: (16,)

Expected Output: 4

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

Input: (2147483647,)

Expected Output: 46340

Explanation: Max 32-bit signed int; floor(sqrt(2147483647)) = 46340 (46341^2 overflows 32 bits).

Input: (2147395600,)

Expected Output: 46340

Explanation: 46340^2 exactly; tests the boundary where mid * mid must not overflow a 32-bit type.

Hints

The answer lies in the range [0, x]. For x >= 2, the square root is at most x // 2, so you can search [1, x // 2].
Binary search on the candidate answer: if mid * mid <= x, mid could be the answer (record it) and search higher; otherwise search lower.
In languages with fixed-width integers, mid * mid can overflow 32 bits — cast to a 64-bit (long / long long) before multiplying.
Follow-up: Newton's iteration r = (r + x // r) // 2 converges quadratically and is the more efficient practical method.

Quick Overview

This question evaluates numerical algorithm design and integer arithmetic competence, including robustness for edge cases and overflow handling, and is categorized in the Coding & Algorithms domain.