Sqrt(x)

Sqrt(x)

What is this problem about?

The Sqrt(x) coding problem is a fundamental algorithm question that asks you to compute and return the square root of a non-negative integer $x$. Since the return type is an integer, the decimal digits are truncated, and you only return the integer part of the result. For example, the square root of 8 is 2.828..., so you should return 2.

Why is this asked in interviews?

This is one of the most frequently asked questions across the entire tech industry (Apple, Microsoft, Uber, etc.). It tests whether you can apply Binary Search to a numerical range instead of just an array. It also assesses your awareness of integer overflow and your ability to optimize from a linear $O(N)$ search to a logarithmic $O(\log N)$ search.

Algorithmic pattern used

The core pattern is Binary Search. Since the square root of $x$ must be between 0 and $x$, we can search this range. For any number $mid$, if $mid \cdot mid \le x$, it could be the answer, so we move our lower bound up. If $mid \cdot mid > x$, the answer must be smaller, so we move our upper bound down. This Binary Search interview pattern allows us to find the answer very quickly even for large values of $x$.

Example explanation (use your own example)

Let's find the square root of $x = 10$.

1. Range: [0, 10]. Mid = 5. $5 \cdot 5 = 25 > 10$. Range becomes [0, 4].
2. Range: [0, 4]. Mid = 2. $2 \cdot 2 = 4 \le 10$. This is a candidate. Range becomes [3, 4].
3. Range: [3, 4]. Mid = 3. $3 \cdot 3 = 9 \le 10$. This is a better candidate. Range becomes [4, 4].
4. Range: [4, 4]. Mid = 4. $4 \cdot 4 = 16 > 10$. Range becomes [4, 3]. The search ends, and the last valid candidate was 3. Truncated sqrt(10) is 3.

Common mistakes candidates make

• Linear Search: Using a for loop from 1 to $x$, which is $O(x)$ and too slow for large inputs.
• Integer Overflow: Computing $mid \cdot mid$ which can exceed the maximum value of a 32-bit integer. It's safer to use $mid \le x / mid$.
• Precision issues: Using floating-point math when an integer-only solution is preferred.
• Boundary conditions: Not handling $x=0$ or $x=1$ correctly.

Interview preparation tip

Binary search is not just for finding elements in a list; it's a powerful tool for searching any sorted space, including numerical ranges. Always check for overflow when multiplying middle values in these types of problems.