← Expedia Interview InsightsSoftware Engineer

Expedia·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Expedia coding round, one problem the whole session. It was a backtracking question dressed up with a quirky digit constraint and I spent more time second-guessing the range than actually coding.

Questions Asked (1)

Q1

Given a string of digits and '?' wildcards (e.g. '08??840') and a target digit sum, replace each '?' with any digit from 0 to 8 and return all resulting strings whose digits sum to the target.

Algorithms & Data Structures
Author's notes

The 0-8 range tripped me up.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use backtracking to replace each '?' with digits 0-8, pruning branches where the current sum plus the minimum possible sum of remaining '?' exceeds the target or plus the maximum possible sum is less than the target. Collect all valid strings when all '?' are replaced and the sum equals the target.

Pro tip: Clarify the constraints upfront (e.g., string length, number of '?', target range) and discuss time/space complexity; also mention that pruning with min/max remaining sums drastically reduces the search space.

1. Clarify requirements and constraints

Ask about input size, digit range (0-8), target sum range, and whether output order matters. Confirm that '?' can be replaced by any digit from 0 to 8.

2. Precompute fixed sum and wildcard count

Calculate the sum of fixed digits and count the number of '?' to determine the remaining sum needed and the min/max possible contributions from wildcards.

3. Design recursive backtracking with pruning

Recursively replace each '?' with digits 0-8, tracking current sum and index. Prune if current sum + minRemaining > target or current sum + maxRemaining < target.

4. Collect and return valid strings

When all '?' are replaced, check if the total sum equals the target; if so, add the string to the result list. Return the list of all valid strings.

5. Analyze complexity and optimize

Discuss time complexity (worst-case O(9^k) where k is number of '?') and space complexity (O(k) recursion depth). Mention that pruning reduces practical runtime.

Key Points to Mention

  • Backtracking with pruning based on min/max possible sums of remaining wildcards
  • Time complexity: O(9^k) worst-case, but pruning makes it much faster in practice
  • Space complexity: O(k) for recursion stack, plus O(m) for output storage
  • Edge cases: no '?' (just check sum), target sum impossible (return empty), leading zeros allowed
  • Use of helper function to compute min/max remaining sums efficiently
  • Potential optimization: iterate digits in a smart order or use memoization if needed

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