← Capital One Interview Insights

Capital One·Software Engineer·Technical Phone Screen·Senior

Senior
May 2026

Summary

Capital One Applied Researcher interview that came down to a single algorithmic problem about counting subarrays with alternating parity. Not the most complex setup but the problem had enough edge cases to trip you up if you weren't careful.

Questions Asked (1)

Q1

Given an array of integers, count the total number of contiguous subarrays of length 1 or more where the elements strictly alternate between even and odd parity (a 'sawtooth' sequence).

Algorithms & Data Structures
Author's notes

Took me a minute to realize single-element subarrays always count, which is kind of a free baseline you can build on.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a linear scan to track the length of the current alternating parity run, adding that length to a running total at each step. This works because every new element extends all valid subarrays ending at the previous element by one, plus starts a new subarray of length 1.

Pro tip: Clarify that 'strictly alternate' means adjacent elements must have different parity, and confirm whether subarrays of length 1 count (they do). Also mention that this O(n) solution is optimal since you must examine each element at least once.

1. Clarify the problem

Confirm that subarrays must be contiguous, length >= 1, and that parity alternation means adjacent elements have different parity (even vs odd).

2. Identify the pattern

Recognize that if the current element alternates with the previous one, it extends all valid subarrays ending at the previous element by one, plus forms a new subarray of length 1.

3. Design the algorithm

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

4. Analyze complexity

The algorithm runs in O(n) time and O(1) extra space, which is optimal since every element must be examined.

5. Test with examples

Walk through a small example (e.g., [1,2,3]) to verify the logic and edge cases like single-element arrays or all-even arrays.

Key Points to Mention

  • Parity check: (a[i] % 2) != (a[i-1] % 2)
  • Dynamic programming or running sum approach
  • Time complexity O(n), space complexity O(1)
  • Handling edge cases: empty array, single element, all same parity
  • Explanation of why adding current_run counts all valid subarrays ending at current index
  • Potential for integer overflow if using 32-bit int for large n (use 64-bit)

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