PayPal·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

PayPal coding screen, one question, pretty standard binary search territory. Nothing wild but the O(log n) constraint makes it clear they want you to actually think about complexity and not just brute force it.

Questions Asked (1)

Given a sorted array of distinct integers and a target value, return the index of the target if found. If not found, return the index where it would be inserted to keep the array sorted. Your solution must run in O(log n) time.

Algorithms & Data Structures

Author's notes

Classic binary search but with a small twist at the end.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use binary search to find the target or the insertion point. Maintain low and high pointers, and at each step compare the middle element with the target. If found, return the index; otherwise, after the loop, low will be the insertion index.

Pro tip: Clarify that the array has distinct integers and is sorted, so binary search is optimal. Mention that the same algorithm can be implemented using lower_bound in C++ or bisect_left in Python, but be prepared to write it from scratch.

1. Clarify and confirm

Restate the problem to ensure understanding: sorted distinct integers, find target or insertion index, O(log n) required. Ask if there are any constraints on array size or duplicates (though distinct is given).

2. Choose binary search

Explain that binary search is the natural choice for O(log n) on a sorted array. Define low = 0 and high = n (or n-1) and decide on the loop condition.

3. Implement search

While low < high (or low <= high), compute mid, compare nums[mid] with target. If equal, return mid. If nums[mid] < target, set low = mid + 1; else set high = mid.

4. Return insertion index

If the loop ends without finding the target, return low (or high+1 depending on variant) as the insertion point to maintain sorted order.

5. Test and verify

Walk through edge cases: target smaller than all, larger than all, empty array, single element. Confirm O(log n) time and O(1) space.

Key Points to Mention

Binary search reduces search space by half each iteration, achieving O(log n) time.
Use low = 0 and high = n (exclusive) to simplify insertion index return.
Loop condition low < high avoids infinite loops and ensures termination.
When target not found, low equals the insertion index.
Handle edge cases: empty array, target before first element, target after last element.
Space complexity is O(1) as only a few variables are used.

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