← Meta Interview Insights

Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Meta SWE coding round, one algorithm question on finding the majority element in an array. Pretty standard stuff but worth knowing the Boyer-Moore voting approach cold before you walk in.

Questions Asked (1)

Q1

Given an array of integers, find the element that appears more than half the time (the majority element). Assume the array is non-empty and a majority element always exists.

Algorithms & Data Structures
Author's notes

My first instinct was a hashmap to count frequencies, which works fine and I got it out cleanly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and constraints, then propose a solution using Boyer-Moore Voting Algorithm, which finds the majority element in O(n) time and O(1) space. Explain the algorithm's intuition and walk through a small example to demonstrate correctness.

Pro tip: Mention that the Boyer-Moore algorithm is optimal for this problem and that it can be extended to find elements appearing more than n/k times. Also, discuss potential edge cases like when the majority element is not guaranteed, and how to verify the candidate in a second pass.

1. Clarify the problem

Restate the problem to ensure understanding: find the element that appears more than n/2 times in a non-empty array where a majority element always exists. Ask if there are any constraints on time or space complexity.

2. Discuss possible approaches

Mention brute force (O(n^2)), sorting (O(n log n)), hash map (O(n) time, O(n) space), and then introduce Boyer-Moore Voting Algorithm as the optimal O(n) time, O(1) space solution.

3. Explain Boyer-Moore algorithm

Describe the algorithm: maintain a candidate and a count; iterate through the array, if count is 0 set candidate to current element and count to 1; else if current element equals candidate increment count, else decrement count. The candidate at the end is the majority element.

4. Walk through an example

Choose a small array (e.g., [2,2,1,1,1,2,2]) and step through the algorithm to show how the candidate and count evolve, demonstrating that the final candidate is the majority element.

5. Analyze complexity and edge cases

State that the algorithm runs in O(n) time and O(1) space. Discuss that if the majority element is not guaranteed, a second pass is needed to verify the candidate's count. Also mention that the algorithm works because the majority element's count cannot be canceled out completely.

Key Points to Mention

  • Boyer-Moore Voting Algorithm is optimal for this problem with O(n) time and O(1) space.
  • The algorithm works by canceling out pairs of different elements, leaving the majority element as the candidate.
  • If the majority element is not guaranteed, a second pass is required to verify the candidate's frequency.
  • Alternative approaches: sorting (O(n log n)) or hash map (O(n) space) are less optimal.
  • The algorithm can be generalized to find elements appearing more than n/k times.
  • Edge cases: array with all identical elements, array with negative numbers, and large input sizes.

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