← Capital One Interview Insights

Capital One·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Capital One coding screen, one algorithm problem on alternating parity subarrays. The brute force solution isn't going to cut it here, so knowing the linear scan trick ahead of time is basically the whole battle.

Questions Asked (1)

Q1

Given an integer array, count the number of contiguous subarrays of length at least 2 where elements strictly alternate between odd and even values.

Algorithms & Data Structures
Author's notes

My first instinct was the nested loop approach and I even started typing it out before remembering that O(n^2) was going to be a problem on large inputs.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem and constraints, then propose an O(n) single-pass solution that tracks the length of the current alternating run. For each position, add the number of valid subarrays ending there, which is the current run length minus 1 if the run length is at least 2.

Pro tip: Mention that you can optimize to O(1) space by only keeping the current run length, and explicitly handle edge cases like arrays of length 0 or 1. Also, discuss how the solution would change if the array were circular or if the subarrays needed to be of exactly length k.

1. Understand the problem

Restate the problem in your own words and ask clarifying questions about input size, element ranges, and whether the array can be empty. Confirm that 'strictly alternate' means odd-even-odd or even-odd-even.

2. Brainstorm approaches

Start with a brute-force O(n^2) or O(n^3) solution to show understanding, then optimize. Recognize that the property is local: a subarray alternates iff every adjacent pair alternates.

3. Design an efficient algorithm

Use a single pass: maintain the length of the current alternating run. For each new element, if it alternates with the previous, increment the run length; otherwise reset to 1. Add (run length - 1) to the count if run length >= 2.

4. Analyze complexity and edge cases

State that the time complexity is O(n) and space is O(1). Walk through edge cases: empty array, single element, all same parity, and alternating array.

5. Test with examples

Trace the algorithm on a small example like [1,2,3,4] and [1,3,5] to verify correctness. Discuss potential off-by-one errors.

Key Points to Mention

  • Definition of alternating parity: consecutive elements have different parity (one odd, one even).
  • Brute-force approach: check all subarrays of length >= 2, O(n^2) or O(n^3) time.
  • Optimized approach: dynamic programming or sliding window tracking current alternating run length.
  • Time and space complexity: O(n) time, O(1) space.
  • Edge cases: empty array, single element, all elements same parity, fully alternating array.
  • Handling large inputs: the O(n) solution is optimal and scalable.

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