Instacart·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Instacart SWE interview with a coding question that looks deceptively simple but has a parity edge case that'll trip you up if you're not paying attention. The O(n) constraint is the real test here.

Questions Asked (1)

Given an integer array that may include negative numbers, count all contiguous subarrays where the elements strictly alternate between odd and even parity. Subarrays of length 1 always qualify. Can you do it in O(n)?

Algorithms & Data Structures

Author's notes

The negative number thing is where I fumbled first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a single pass through the array, maintaining the length of the current alternating parity run ending at the previous index. For each element, if its parity differs from the previous element, extend the run; otherwise, reset the run to 1. Add the run length to a running total, as each new element contributes that many valid subarrays ending at its position.

Pro tip: Clarify that 'strictly alternate' means adjacent elements must have different parity, and explicitly state that length-1 subarrays always count. Then walk through a small example to demonstrate the O(n) logic and catch off-by-one errors.

1. Clarify the problem

Confirm that parity means odd/even, that alternation is strict (no two adjacent same parity), and that single-element subarrays are always valid. Ask if the array can be empty or contain zeros (zero is even).

2. Define the state

Maintain a variable `run` representing the length of the longest alternating parity subarray ending at the current index. Initialize `run = 1` for the first element and `total = 1`.

3. Iterate and update

For each subsequent element, compare its parity with the previous element. If different, increment `run`; otherwise, reset `run` to 1. Add `run` to `total`.

4. Return the total

After the loop, `total` holds the count of all valid contiguous subarrays. Return it.

5. Analyze complexity

Explain that the algorithm uses O(1) extra space and runs in O(n) time because it processes each element exactly once.

Key Points to Mention

Parity check: use `num % 2` to determine odd/even, handling negative numbers correctly (e.g., -3 % 2 == -1 in some languages, so compare absolute parity or use `num & 1`).
Dynamic programming / sliding window perspective: the run length acts as a DP state that captures all valid subarrays ending at the current index.
Counting contribution: each element contributes `run` new subarrays (one ending at each position in the current alternating run).
Edge cases: empty array (return 0), single element (return 1), all same parity (return n), and alternating array (return n*(n+1)/2).
Time and space complexity: O(n) time, O(1) space, which is optimal since any algorithm must at least read the input.
Potential pitfalls: off-by-one errors when resetting the run, and incorrect handling of negative numbers in parity checks.

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