Airbnb·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Airbnb software engineer coding round, one problem the whole session. The question was harder to implement cleanly than it looks on paper and I spent a lot of time getting the backtracking logic right.

Questions Asked (1)

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 StructuresTechnical Trade-offs

Author's notes

The greedy approach feels obvious once you see it but I fumbled the backtracking part for a while.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Treat the problem as finding the smallest permutation of the multiset that is >= the lower bound. Sort the digits and use backtracking with pruning, or generate permutations in lexicographic order and pick the first valid one. Alternatively, use a greedy algorithm that builds the number digit by digit, choosing the smallest possible digit at each position while ensuring a valid completion exists.

Pro tip: Clarify constraints first (e.g., digit count, lower bound size) to choose between brute-force and optimized approaches. Mention that if the lower bound has more digits than the multiset, return -1 immediately; if fewer, return the smallest permutation (sorted ascending).

1. Understand the problem and constraints

Restate the problem: given a multiset of digits and a lower bound, find the smallest permutation >= lower bound, else -1. Ask about input size, digit range, and whether leading zeros are allowed.

2. Handle trivial cases

If the number of digits in the multiset is less than the number of digits in the lower bound, return -1. If greater, return the digits sorted in ascending order (smallest number). If equal, proceed to the main algorithm.

3. Choose an algorithm

For equal length, use backtracking with pruning or a greedy approach with a feasibility check. Sort the digits and try to match the lower bound prefix as closely as possible, then find the smallest valid suffix.

4. Implement and test

Write code to generate the next permutation or use DFS. Test with edge cases: lower bound with repeated digits, no valid permutation, leading zeros, and large inputs.

5. Analyze complexity and trade-offs

Discuss time and space complexity. Backtracking is O(n!) worst-case but can be optimized. Greedy with binary search is O(n log n). Mention trade-offs between simplicity and efficiency.

Key Points to Mention

Sorting the digits to facilitate finding the next permutation.
Handling leading zeros: if the smallest permutation starts with zero, it might be invalid unless the number is zero itself.
Using backtracking with pruning to avoid exploring all permutations.
Greedy approach: at each position, pick the smallest digit >= lower bound's digit that allows a valid suffix.
Edge cases: lower bound has more digits, no valid permutation, duplicate digits.
Time complexity: O(n!) for brute force, O(n log n) for optimized greedy with binary search.

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