← Expedia Interview InsightsSoftware Engineer

Expedia·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Expedia software engineer interview with a sliding window / prefix sum problem. Pretty standard coding round, nothing too wild, but the two-approach angle made it more interesting than I expected.

Questions Asked (1)

Q1

Given an integer array and an integer k, count the number of contiguous subarrays that contain exactly k odd numbers.

Algorithms & Data Structures
Author's notes

I went straight for the prefix sum approach, which worked, but I fumbled explaining why it was correct.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

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.

1. Understand the problem

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.

2. Choose an efficient approach

Decide between sliding window (two pointers) or tracking odd indices. The sliding window with atMost(k) - atMost(k-1) is straightforward and O(n).

3. Implement the sliding window helper

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.

4. Compute the result

Return atMost(k) - atMost(k-1). Handle k=0 separately if needed, but the formula works if atMost(-1) returns 0.

5. Analyze complexity and test

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).

Key Points to Mention

  • Sliding window technique for counting subarrays with a constraint
  • Monotonic property: number of odd numbers increases as window expands
  • Using atMost(k) - atMost(k-1) to get exactly k
  • Time complexity O(n) and space O(1)
  • Edge cases: k=0, k > total odds, empty array
  • Alternative approach: track indices of odd numbers and compute combinations

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