← Expedia Interview InsightsSoftware Engineer

Expedia·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Expedia coding screen, one algorithmic problem about rearranging an array so no two adjacent elements are the same. Pretty standard for this type of role but the constraint makes it trickier than it looks at first glance.

Questions Asked (1)

Q1

Given an integer array, rearrange it so that no two adjacent elements are equal. A valid arrangement is guaranteed to exist. Return any valid result.

Algorithms & Data Structures
Author's notes

My first instinct was to just sort and interleave, which works but I fumbled explaining why it works.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a max-heap to greedily place the most frequent remaining element that differs from the last placed element. This ensures the most frequent elements are placed early and avoids adjacent duplicates. The guaranteed existence of a valid arrangement means the greedy choice will always succeed.

Pro tip: After presenting the heap solution, mention that a simpler O(n) approach exists using the majority element (if any) and interleaving, but the heap method is more general and easier to reason about under pressure.

1. Clarify and Confirm

Restate the problem: rearrange array so no two adjacent elements are equal, and a valid arrangement is guaranteed. Confirm input size and constraints (e.g., can elements be negative? duplicates?).

2. Choose Data Structure

Use a max-heap (priority queue) keyed by frequency to always access the most frequent remaining element. Alternatively, consider sorting and interleaving, but heap is more straightforward.

3. Greedy Placement Algorithm

While heap has elements: pop the most frequent element. If it equals the last placed element, pop the next most frequent, place it, then push back the first if its count > 0. Otherwise, place the popped element and push back if count > 0.

4. Handle Edge Cases

If heap becomes empty but last element still has count > 0, it means no valid arrangement (but problem guarantees one). Also handle single-element array and all elements same (only possible if length 1).

5. Analyze Complexity

Time: O(n log k) where k is number of distinct elements, typically O(n log n). Space: O(n) for the heap and result array.

Key Points to Mention

  • Greedy strategy: always place the most frequent element that is not equal to the previous element.
  • Use of a max-heap (priority queue) to efficiently retrieve the most frequent element.
  • Handling the case where the most frequent element equals the last placed element by temporarily using the second most frequent.
  • Time and space complexity analysis: O(n log n) time, O(n) space.
  • Proof of correctness: the greedy choice is safe because a valid arrangement is guaranteed, and placing the most frequent element early prevents it from being stranded.
  • Alternative approaches: sorting and interleaving, or using the majority element if it exists (Boyer-Moore), but heap is more general.

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