← LinkedIn Interview InsightsSoftware Engineer

LinkedIn·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

LinkedIn coding screen for a software engineer role, just one algorithm question the whole time. Pretty standard vibe, nothing unexpected.

Questions Asked (1)

Q1

Given a non-negative integer n, determine whether it is a perfect square without using any built-in square root function. Your solution should run in O(log n) time.

Algorithms & Data Structures
Author's notes

My first instinct was to just iterate from 1 upward and multiply each number by itself until I hit n or exceeded it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use binary search on the range [0, n] to find an integer x such that x^2 equals n, avoiding overflow by comparing mid with n/mid. If found, return true; otherwise, return false after the search space is exhausted.

Pro tip: Mention edge cases like n=0 and n=1, and explicitly discuss how you avoid integer overflow when squaring large numbers—this shows attention to detail and practical coding maturity.

1. Clarify constraints and edge cases

Confirm that n is non-negative and discuss special cases like 0 and 1, which are perfect squares. Also consider the maximum input size to plan for overflow handling.

2. Choose binary search over linear scan

Explain that a linear scan from 1 to n would be O(n), but binary search on the answer space [0, n] achieves O(log n) time. Justify why binary search is applicable: the predicate 'x^2 <= n' is monotonic.

3. Implement binary search with overflow-safe comparison

Set low=0, high=n. While low <= high, compute mid = low + (high - low)//2. Compare mid with n//mid (or use division) to avoid overflow when squaring mid. Adjust low/high accordingly.

4. Handle termination and return result

If mid*mid == n (checked safely), return true. If the loop ends without finding an exact square, return false. Ensure the loop condition and updates prevent infinite loops.

5. Analyze complexity and test

State that time complexity is O(log n) and space is O(1). Walk through a few test cases (e.g., n=16, n=14, n=0) to verify correctness and edge handling.

Key Points to Mention

  • Binary search on the integer range [0, n] to achieve O(log n) time.
  • Overflow avoidance by using division (n/mid) instead of multiplication (mid*mid).
  • Monotonic property: if mid^2 > n, the answer must be in the lower half; if mid^2 < n, in the upper half.
  • Edge cases: n=0 and n=1 are perfect squares; handle them explicitly or ensure the algorithm covers them.
  • Time complexity O(log n) and space complexity O(1).
  • Alternative approaches like Newton's method, but binary search is simpler and meets the requirement.

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