← Meta Interview InsightsSoftware Engineer

Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Meta SWE coding round, one question the whole time. The problem sounds straightforward until you realize they want O(log n) and suddenly you're rethinking everything you thought you knew about binary search.

Questions Asked (1)

Q1

Given an integer array where no two adjacent elements are equal, find any peak element. A peak is an index where the value is greater than both its neighbors, with the array boundaries treated as negative infinity. Solve it in O(log n).

Algorithms & Data Structures
Author's notes

I started with the linear scan and they let me finish before asking if I could do better.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a binary search approach by examining the middle element and comparing it to its neighbors to determine which half of the array is guaranteed to contain a peak. Since no two adjacent elements are equal, you can always eliminate half the search space by moving toward the side with the larger neighbor. This guarantees O(log n) time complexity while leveraging the mathematical guarantee that a peak must exist in the chosen half.

Pro tip: Explicitly state the key invariant that makes binary search valid here: if nums[mid] < nums[mid+1], the right half must contain a peak because the sequence must eventually turn downward before the boundary (treated as -infinity). Articulating this invariant shows deep understanding beyond just memorizing the algorithm.

1. Clarify the Problem

Confirm that 'any' peak is acceptable (not necessarily the global maximum) and that boundaries are treated as negative infinity. Ask about edge cases like a single-element array, which is trivially a peak.

2. Explain Why Binary Search Works

Articulate the core invariant: if the middle element is smaller than its right neighbor, a peak must exist in the right half because the values must eventually decrease before hitting the -infinity boundary. This logical guarantee is what makes binary search applicable to a non-sorted array.

3. Implement the Binary Search

Set lo=0 and hi=n-1, then in each iteration check if nums[mid] > nums[mid+1]; if so, search left (hi=mid), otherwise search right (lo=mid+1). Continue until lo==hi, which is the peak index.

4. Handle Edge Cases

Verify your solution handles single-element arrays, peaks at the first or last index, and strictly monotonic arrays (where the peak is at one of the ends). Trace through at least one example to validate correctness.

5. Analyze Complexity and Discuss Extensions

Confirm O(log n) time and O(1) space complexity. Optionally mention the follow-up variant (LC 1901) for finding a peak in a 2D matrix, which demonstrates awareness of how the concept scales.

Key Points to Mention

  • The binary search invariant: a peak is guaranteed to exist in the half where the neighbor is larger, due to the -infinity boundary condition
  • Why this works on an unsorted array — you're not searching for a specific value but exploiting the structural guarantee of a peak's existence
  • The termination condition: lo == hi pinpoints the peak, and the loop invariant ensures it is always a valid peak index
  • No two adjacent elements are equal is a critical constraint — without it, plateaus could break the binary search logic
  • O(log n) time complexity and O(1) space complexity, contrasting with the naive O(n) linear scan
  • Edge cases: single-element array, peak at index 0 or n-1, and monotonically increasing or decreasing arrays

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