← LinkedIn Interview InsightsSoftware Engineer

LinkedIn·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

LinkedIn software engineer interview, got a binary search problem that looks straightforward until you realize you need two separate searches. Pretty standard for this type of role but the O(log n) constraint is what makes it non-trivial.

Questions Asked (1)

Q1

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) time.

Algorithms & Data Structures
Author's notes

My first instinct was to find any occurrence and then scan left and right, which is obviously O(n) and not what they want.

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 boundaries based on whether you need the first or last position. This ensures O(log n) time complexity.

Pro tip: Mention that you can implement a single helper function that takes a boolean flag to find either the first or last occurrence, reducing code duplication and potential errors. Also, clarify how you handle edge cases like an empty array or when the target is not present.

1. Clarify requirements and edge cases

Confirm that the array is sorted in ascending order, may contain duplicates, and that the target may or may not exist. Discuss edge cases: empty array, target smaller than first element, target larger than last element.

2. Design binary search for first occurrence

Perform binary search; when target is found, record the index and continue searching in the left half to find an earlier occurrence. Return the recorded index if found, else -1.

3. Design binary search for last occurrence

Similarly, perform binary search; when target is found, record the index and continue searching in the right half to find a later occurrence. Return the recorded index if found, else -1.

4. Combine results and handle not found

If either search returns -1, return [-1, -1]. Otherwise, return [first, last]. Ensure the solution runs in O(log n) time and O(1) space.

5. Test with examples and edge cases

Walk through examples: target present multiple times, target present once, target absent, empty array. Verify correctness and time complexity.

Key Points to Mention

  • Time complexity: O(log n) due to two binary searches, each O(log n).
  • Space complexity: O(1) iterative implementation.
  • Handling duplicates: binary search must continue after finding a match to locate boundaries.
  • Edge cases: empty array, target not present, target at boundaries.
  • Code clarity: use a helper function with a flag to avoid duplication.
  • Comparison with linear scan: emphasize why binary search is necessary for O(log n).

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