← Boston Consulting Group Interview Insights

Boston Consulting Group·AI Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

BCG AI Engineer interview with a coding question on array parity patterns. Pretty focused on algorithmic thinking, nothing too wild but it required some careful edge case handling.

Questions Asked (1)

Q1

Given an integer array, count every contiguous subarray where adjacent elements strictly alternate between odd and even values. Subarrays of length 1 count too.

Algorithms & Data Structures
Author's notes

The length-1 edge case is the kind of thing you skip over mentally and then get burned by.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem and edge cases, then propose an O(n) single-pass solution that tracks the length of the current alternating run and adds it to the total count. Explain why this works and discuss trade-offs with a brute-force approach.

Pro tip: Emphasize that each new element extends all valid subarrays ending at the previous position if the alternation condition holds, so you can count them in constant time per element. This shows you understand the combinatorial insight behind the linear solution.

1. Clarify the problem

Confirm definitions: contiguous subarray, strict alternation between odd and even, and that length-1 subarrays always count. Ask about input size, possible negative numbers, and expected output type.

2. Discuss brute-force approach

Mention that checking all O(n^2) subarrays and verifying alternation would be O(n^3) or O(n^2) with optimization, but it's inefficient for large inputs.

3. Derive the linear-time insight

Observe that if the current element alternates with the previous one, it extends all valid subarrays ending at the previous position, plus itself. Maintain a running length of the current alternating run.

4. Present the algorithm

Initialize total = 1 and run_length = 1. For each subsequent element, if it alternates with the previous, increment run_length; otherwise reset to 1. Add run_length to total. Return total.

5. Analyze complexity and edge cases

State O(n) time and O(1) space. Test with empty array, single element, all same parity, and alternating array to verify correctness.

Key Points to Mention

  • Definition of odd/even alternation: (a[i] % 2) != (a[i-1] % 2).
  • Length-1 subarrays always count, so initialize total and run_length to 1.
  • When alternation holds, run_length increases by 1; otherwise reset to 1.
  • Each step adds run_length to total, accounting for all valid subarrays ending at current index.
  • Time complexity O(n) and space complexity O(1).
  • Edge cases: empty array (return 0), single element (return 1), all same parity (return n).

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