Greedy Questions at Expedia: What to Expect

Greedy algorithms are a practical and efficient approach to optimization problems, and Expedia’s interview process reflects their real-world utility in travel and logistics. With 10 out of 54 total coding questions tagged as Greedy, it’s a significant focus area. Mastering these questions demonstrates your ability to make locally optimal choices that lead to globally optimal solutions—a skill directly applicable to optimizing routes, scheduling, pricing, and resource allocation in a travel technology company.

What to Expect — Types of Problems

Expedia’s Greedy problems typically fall into a few predictable categories. You can expect questions on interval scheduling—like booking the maximum number of non-overlapping meetings or flights. Coin change variations may appear, often framed as minimizing or maximizing resource use. Array-based optimization is common, requiring you to rearrange or select elements to achieve a goal, such as maximizing profit or minimizing cost. Problems involving sorting and selection, where sorting the data enables a simple greedy pass, are also frequent. The key is recognizing that a greedy choice property and optimal substructure exist; if you can prove that taking the best immediate choice leads to the best overall outcome, a greedy approach is likely valid.

How to Prepare — Study Tips with One Code Example

Start by solidifying the core greedy patterns: activity selection, coin change (canonical), and task scheduling. Practice proving why the greedy choice works—this is often discussed in interviews. Then, move to Expedia-specific problems to understand their flavor. A fundamental pattern is the "minimum number of coins" problem, where you aim to make an amount with the fewest coins from an infinite supply of given denominations (assuming canonical systems like US coins). The greedy approach works here because larger denominations are multiples of smaller ones.

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        if amount == 0:
            break
        count += amount // coin
        amount %= coin
    return count if amount == 0 else -1

# Example: coins = [1, 5, 10, 25], amount = 63
# Returns 6 (25+25+10+1+1+1)

Note: This greedy solution only works for canonical coin systems. For arbitrary denominations, a dynamic programming approach is required—a common follow-up question.

Recommended Practice Order

1. Foundation: Solve classic greedy problems (Activity Selection, Fractional Knapsack, Minimum Coin Change for canonical systems) on platforms like LeetCode.
2. Pattern Recognition: Practice Expedia-tagged Greedy questions to identify recurring themes, such as interval merging or maximizing sum with constraints.
3. Proof & Edge Cases: For each problem, articulate why the greedy choice is optimal and test edge cases (empty input, single element, large values).
4. Integration: Mix greedy problems with other Expedia topics (like Arrays or Dynamic Programming) to simulate the actual interview question distribution.

Practice Greedy at Expedia