← Expedia Interview InsightsSoftware Engineer

Expedia·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Coding round at Expedia for a software engineer role. Pretty standard dynamic programming problem, nothing that would throw you off if you've done any leetcode prep.

Questions Asked (1)

Q1

You are a robber trying to maximize the amount stolen from a row of houses, where you cannot rob two adjacent houses without triggering an alarm. Given an array of non-negative integers representing money in each house, return the maximum amount you can rob.

Algorithms & Data Structures
Author's notes

Classic DP problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as a dynamic programming problem where at each house you decide to rob it (and add the max from two houses back) or skip it (keeping the max from one house back). Define dp[i] as the maximum amount robbable from the first i houses, then derive the recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Optimize space to O(1) by tracking only the last two values.

Pro tip: Start by clarifying edge cases (empty array, single house) and then walk through a small example like [2,7,9,3,1] to validate your recurrence before coding. This shows structured thinking and catches off-by-one errors early.

1. Clarify and Restate

Confirm the problem constraints: non-negative integers, no two adjacent houses, return maximum sum. Ask about edge cases like empty input or single house.

2. Define Subproblem and Recurrence

Let dp[i] be the max money from first i houses. At house i, either skip it (dp[i-1]) or rob it (dp[i-2] + nums[i]). So dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

3. Handle Base Cases and Iterate

Initialize dp[0] = 0, dp[1] = nums[0]. Iterate from i=2 to n, applying the recurrence. Return dp[n].

4. Optimize Space

Since dp[i] depends only on dp[i-1] and dp[i-2], use two variables (prev2, prev1) to achieve O(1) space. Update them each iteration.

5. Test and Analyze Complexity

Walk through a sample array to verify. State time complexity O(n) and space O(1). Mention that this is optimal.

Key Points to Mention

  • Dynamic programming approach with optimal substructure
  • Recurrence relation: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  • Base cases: empty array returns 0, single house returns its value
  • Space optimization from O(n) to O(1) using two variables
  • Time complexity O(n) and space complexity O(1)
  • Edge cases: all zeros, large values, negative numbers (though problem says non-negative)

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