Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Meta Data Engineer coding round, one algorithmic problem that looked deceptively simple but had a neat counting trick hiding underneath it.

Questions Asked (1)

Given an integer array of length n, count the number of index pairs (i, j) where i < j, the product of the two elements is even, and the difference in indices is odd.

Algorithms & Data Structures

Author's notes

I started brute-forcing it in my head and then caught myself.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem and edge cases. Then, derive a mathematical condition for the index difference being odd: i and j must have different parities. Count even and odd numbers at even and odd indices, and compute the number of valid pairs using combinatorics.

Pro tip: Mention that a brute-force O(n^2) solution is trivial but inefficient; aim for O(n) by counting. Also, explicitly state the parity condition for the index difference to show clarity.

1. Clarify the problem

Restate the problem in your own words and ask clarifying questions about input constraints, expected output, and edge cases (e.g., empty array, negative numbers).

2. Analyze the conditions

Break down the conditions: product even means at least one element is even; index difference odd means i and j have different parities (one even, one odd).

3. Count elements by parity and index parity

Traverse the array once, counting how many even and odd numbers are at even indices and at odd indices. This gives four counts: evenEven, evenOdd, oddEven, oddOdd.

4. Compute valid pairs

Use the counts to compute the number of valid pairs: pairs where at least one element is even and indices have different parities. Sum the appropriate products of counts.

5. Verify with examples

Test the formula on small examples to ensure correctness, and discuss time and space complexity (O(n) time, O(1) space).

Key Points to Mention

Parity of indices: i and j must have different parities for index difference to be odd.
Product even condition: at least one of the two elements must be even.
Counting approach: count even/odd numbers at even/odd indices in one pass.
Combinatorial calculation: multiply counts of compatible groups to get total pairs.
Time and space complexity: O(n) time, O(1) space.
Edge cases: empty array, all odd numbers, all even numbers, negative numbers.

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