← Expedia Interview InsightsSoftware Engineer
I went straight for the prefix sum approach, which worked, but I fumbled explaining why it was correct.
Use a sliding window (two pointers) to count subarrays with at most k odd numbers, then subtract the count for at most k-1 odd numbers. This yields the number of subarrays with exactly k odd numbers in O(n) time. Alternatively, track positions of odd numbers and compute combinations.
Pro tip: Clarify that the array contains only integers (positive, negative, or zero) and that oddness is determined by parity, not value. Mention that the sliding window works because the number of odd numbers is monotonic as the window expands, allowing efficient counting.
Confirm that you need to count contiguous subarrays with exactly k odd numbers. Clarify edge cases: k=0, k greater than total odd numbers, empty array, etc.
Decide between sliding window (two pointers) or tracking odd indices. The sliding window with atMost(k) - atMost(k-1) is straightforward and O(n).
Write a function that counts subarrays with at most k odd numbers. Use two pointers, expand right, and when odd count exceeds k, move left until it's <= k. Add (right - left + 1) to the count.
Return atMost(k) - atMost(k-1). Handle k=0 separately if needed, but the formula works if atMost(-1) returns 0.
State time complexity O(n) and space O(1). Walk through a small example to verify correctness, and discuss potential pitfalls like integer overflow (use long if needed).
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.