← Boston Consulting Group Interview Insights

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

Intermediate
Apr 2026

Summary

BCG AI Engineer interview with a coding round that leaned more algorithmic than I expected. One question on array parity patterns that took me a minute to fully wrap my head around.

Questions Asked (1)

Q1

Given an integer array, count all contiguous subarrays where every pair of adjacent elements alternates between odd and even. Subarrays of length 1 count too.

Algorithms & Data Structures
Author's notes

My first instinct was to reach for a brute force O(n^2) scan and I started talking through it before realizing there's a cleaner linear pass.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and edge cases, then propose an O(n) single-pass solution that tracks the length of the current alternating run. Explain how each new element extends or resets the run, and how to accumulate the count of valid subarrays.

Pro tip: Emphasize that the count of subarrays ending at each position equals the current run length, which avoids enumerating all subarrays. This demonstrates strong algorithmic insight and efficiency awareness.

1. Clarify the problem

Confirm that subarrays of length 1 always count, and that 'alternates' means adjacent elements have different parity (odd/even).

2. Define the alternating condition

Two adjacent elements alternate if (a[i] % 2) != (a[i-1] % 2). Use this to check validity.

3. Track current run length

Initialize run = 1 for the first element. For each subsequent element, if it alternates with the previous, increment run; otherwise reset run to 1.

4. Accumulate total count

Add run to a total counter at each step, because each valid subarray ending at the current index contributes run new subarrays.

5. Analyze complexity and edge cases

State O(n) time and O(1) space. Handle empty array (return 0) and single element (return 1).

Key Points to Mention

  • Parity check using modulo 2 or bitwise AND 1
  • Single-pass O(n) time and O(1) space solution
  • Dynamic tracking of current alternating run length
  • Accumulation of subarray count via run length
  • Edge cases: empty array, single element, all same parity
  • Avoiding brute-force O(n^2) enumeration

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