LinkedIn·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

LinkedIn software engineer interview with a binary search problem. Pretty standard algorithmic round, nothing too wild, but the two-pass approach tripped me up a bit at first.

Questions Asked (1)

Given a sorted array of integers, find the first and last position of a target value. Return [-1, -1] if the target doesn't exist. Must run in O(log n).

Algorithms & Data Structures

Author's notes

My first instinct was linear scan, which, yeah, immediately wrong given the constraint.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use binary search twice: first to find the leftmost occurrence of the target, then to find the rightmost occurrence. Modify the standard binary search to continue searching even after finding the target, adjusting the search range based on whether you're looking for the first or last position. This ensures O(log n) time complexity.

Pro tip: Clarify with the interviewer whether you can use built-in functions like lower_bound/upper_bound, but be prepared to implement them manually. Also, discuss edge cases like empty array or target not present to show thoroughness.

1. Clarify requirements and edge cases

Confirm the array is sorted, may contain duplicates, and the target may not exist. Discuss handling of empty array and single-element array.

2. Design binary search for first occurrence

Modify binary search to find the leftmost index: when nums[mid] == target, record mid and move the right pointer to mid-1 to search left half.

3. Design binary search for last occurrence

Similarly, find the rightmost index: when nums[mid] == target, record mid and move the left pointer to mid+1 to search right half.

4. Implement and combine results

Write code for both searches, ensuring they run in O(log n). Return [-1, -1] if either search fails to find the target.

5. Test with examples and edge cases

Walk through test cases: target present multiple times, target absent, empty array, target at boundaries. Verify time complexity.

Key Points to Mention

Time complexity O(log n) due to two binary searches, each O(log n).
Space complexity O(1) as only constant extra space is used.
Handling duplicates by continuing search after finding a match.
Edge cases: empty array, target not found, target at start/end.
Comparison with linear scan O(n) to highlight efficiency.
Potential use of lower_bound and upper_bound in C++ or bisect in Python.

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