← Airbnb Interview InsightsSoftware Engineer

Airbnb·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say
Jun 2026

Summary

Airbnb software engineer interview with a tricky permutation problem that looks deceptively clean on the surface but has enough edge cases to really trip you up if you go in without a clear plan.

Questions Asked (1)

Q1

Given a multiset of digits and a lower bound integer, return the smallest number you can form by permuting those digits that is still greater than or equal to the lower bound. Return -1 if no valid permutation exists.

Algorithms & Data Structures
Author's notes

The greedy approach clicked for me pretty fast: walk left to right through the lower bound's digits, at each position try to slot in the smallest available digit that's at least as large as the corresponding bound digit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort the digits and use a greedy backtracking approach to build the smallest number that is >= the lower bound. At each position, try digits in ascending order, but if the prefix matches the lower bound, only consider digits >= the corresponding digit of the lower bound. If a valid number is found, return it; otherwise, backtrack and try the next digit.

Pro tip: Clarify edge cases upfront: leading zeros are allowed if the number has multiple digits? Also, discuss how to handle cases where the lower bound has more digits than the multiset, or when the multiset cannot form a number with the same number of digits as the lower bound.

1. Understand the problem and constraints

Restate the problem: given a multiset of digits and a lower bound, find the smallest permutation >= lower bound. Ask clarifying questions about leading zeros, input format, and constraints.

2. Sort digits and compare lengths

Sort the digits in ascending order. If the number of digits is less than the number of digits in the lower bound, return -1. If equal, proceed to construct the number.

3. Backtracking with pruning

Use backtracking to build the number digit by digit. At each position, if the prefix so far is equal to the lower bound's prefix, only try digits >= the lower bound's current digit; otherwise, try digits in ascending order. Mark digits as used.

4. Handle leading zeros and return result

If leading zeros are allowed, ensure they are considered. Once a complete number is built, return it as an integer or string. If no valid number is found, return -1.

5. Analyze complexity and optimize

Discuss time complexity: O(n! ) in worst case, but pruning reduces it. Mention potential optimizations like using a frequency map and early termination.

Key Points to Mention

  • Sorting the digits to enable greedy selection
  • Backtracking with pruning based on comparison with the lower bound
  • Handling leading zeros appropriately (clarify with interviewer)
  • Edge cases: lower bound has more digits than available, no valid permutation, duplicate digits
  • Time and space complexity analysis
  • Alternative approaches like next permutation or dynamic programming

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