← LinkedIn Interview Insights

LinkedIn·Mobile Engineer·Technical Phone Screen·Intermediate

Intermediate
Mar 2026

Summary

LinkedIn mobile engineer screen, one coding question, pretty straightforward but the constraint about no built-in sqrt tripped me up for a moment before I remembered binary search was the move.

Questions Asked (1)

Q1

Given a positive integer, determine whether it is a perfect square without using any built-in square root functions. Solve it in O(log n) time.

Algorithms & Data Structures
Author's notes

The no-sqrt restriction is what makes it interesting.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use binary search on the range [1, n] to find an integer x such that x^2 equals n. At each step, compare mid^2 with n and adjust the search range accordingly. This yields O(log n) time and O(1) space.

Pro tip: Mention that you can optimize by setting the upper bound to n/2 (for n > 1) to reduce iterations, and handle edge cases like n=1 separately. Also, discuss how to avoid integer overflow when computing mid*mid by using division instead of multiplication.

1. Clarify constraints and edge cases

Confirm that the input is a positive integer and discuss edge cases such as n=1, n=2, and very large numbers that might cause overflow. This shows thoroughness and prevents bugs.

2. Choose binary search over linear search

Explain that a linear scan from 1 to n would be O(n), which is too slow. Binary search reduces the search space by half each iteration, achieving O(log n) time.

3. Define the search range and mid calculation

Set low=1 and high=n (or n/2 for n>1). Compute mid = low + (high - low)/2 to avoid overflow. Compare mid*mid with n.

4. Adjust search range based on comparison

If mid*mid == n, return true. If mid*mid < n, set low = mid + 1. If mid*mid > n, set high = mid - 1. Continue until low > high.

5. Return result and analyze complexity

If the loop ends without finding a perfect square, return false. State that time complexity is O(log n) and space complexity is O(1).

Key Points to Mention

  • Binary search algorithm and its O(log n) time complexity.
  • Handling integer overflow when computing mid*mid by using division or long data type.
  • Edge cases: n=1 is a perfect square, n=2 is not, and n=0 is not positive.
  • Optimization: upper bound can be n/2 for n>1 to reduce iterations.
  • Alternative approach: Newton's method for square root, but binary search is simpler and meets O(log n).
  • Mobile engineering relevance: efficient algorithms for resource-constrained devices.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.