Expedia·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Expedia software engineer interview with a coding problem that looks straightforward until you think about the constraints. The brute force path is obvious but they explicitly want you past it, which tells you something about the bar they're setting.

Questions Asked (1)

Given an array of maximum allowed heights for n pillars, assign each pillar an integer height between 1 and its capacity such that the heights form a single-peak (mountain) shape. Return the maximum possible sum of all heights.

Algorithms & Data Structures

Author's notes

My first instinct was to just try every possible peak index and greedily fill outward, capping each pillar by its neighbor's height and its capacity.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and edge cases, then propose a two-pass dynamic programming approach: compute the maximum non-decreasing heights from left to right and non-increasing heights from right to left, then find the peak that maximizes the sum. Discuss time and space complexity, and consider if any optimizations are possible.

Pro tip: Mention that the optimal peak can be found in O(n) time by precomputing prefix and suffix maxima, and emphasize that you would test with edge cases like all equal capacities or strictly increasing capacities.

1. Understand the problem

Restate the problem in your own words: assign heights within capacities to form a single-peaked array maximizing the sum. Clarify that the peak can be at any index and heights must be integers.

2. Identify constraints and edge cases

Discuss constraints like n up to 10^5, capacities up to 10^9, and edge cases such as n=1, all capacities equal, or capacities that force a flat peak.

3. Design the algorithm

Propose a two-pass DP: left[i] = min(capacity[i], left[i-1]+1) for i>0, and right[i] = min(capacity[i], right[i+1]+1) for i<n-1. Then for each i, the height at peak i is min(left[i], right[i]), and the total sum is sum of left up to i-1 + peak + sum of right from i+1.

4. Analyze complexity and optimize

State that the algorithm runs in O(n) time and O(n) space. Mention that space can be reduced to O(1) extra by computing prefix sums on the fly, but O(n) is acceptable.

5. Test with examples

Walk through a small example, e.g., capacities = [3,2,1], to show how the algorithm yields the maximum sum. Also test edge cases like [1,1,1] and [1,2,3].

Key Points to Mention

Dynamic programming with two passes (left-to-right and right-to-left) to compute maximum possible heights respecting the mountain shape.
The peak height at index i is min(left[i], right[i]), and the total sum is computed by combining the left and right parts.
Time complexity O(n) and space complexity O(n), with potential for O(1) extra space if needed.
Edge cases: n=1, all capacities equal, strictly increasing/decreasing capacities, and large capacities requiring 64-bit integers.
Proof of correctness: the left pass ensures non-decreasing heights up to i, the right pass ensures non-increasing heights from i, and taking the minimum at the peak maintains both constraints.
Alternative approaches like greedy or binary search are less efficient or more complex; the DP approach is optimal.

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