How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Airbnb.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Find smallest permutation under constraints

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given a non-negative integer `n`, consider its decimal digits as a multiset (digits can repeat). 1) Return the **smallest possible integer** that can be formed by rearranging the digits of `n`, **allowing leading zeros** (i.e., you are allowed to place `0` at the front; the result is still treated as an integer value). 2) Follow-up: Given an additional integer `lowerBound`, return the **smallest integer strictly greater than `lowerBound`** that can be formed by rearranging the digits of `n`. If no such number exists, return an indication such as `-1`. ### Example - `n = 178`: smallest permutation (allow leading zeros) is `178`. - Follow-up: `n = 178`, `lowerBound = 200` → answer is `718`. ### Constraints - You may assume `n` fits in 32-bit signed integer input, but intermediate permutations may exceed 32-bit; define how you handle overflow (e.g., use 64-bit or strings).

Quick Answer: This question evaluates digit-manipulation and combinatorial permutation skills, along with numeric ordering and representation concerns such as leading zeros and overflow handling in the Coding & Algorithms domain.

Part 1: Smallest Integer From Digit Rearrangement

Given a non-negative integer `n`, rearrange all of its decimal digits to form the smallest possible integer value. Leading zeros are allowed in the rearranged digit string, and those zeros are ignored when the value is interpreted as an integer. For example, rearranging `1002` as `0012` produces the integer `12`.

Constraints

`0 <= n <= 2,147,483,647`
`n` is given in base 10
Leading zeros are allowed in the rearranged digit string
Use normal Python integers for the result

Examples

Input: 178

Expected Output: 178

Explanation: The digits are already in ascending order, so the smallest rearrangement is 178.

Input: 1002

Expected Output: 12

Explanation: Sorting gives `0012`, which is interpreted as the integer 12.

Input: 9070

Expected Output: 79

Explanation: Sorting gives `0079`, which becomes 79 as an integer.

Input: 0

Expected Output: 0

Explanation: The only rearrangement of the single digit 0 is 0.

Hints

What happens if you sort the digits in ascending order?
Because leading zeros are allowed, you do not need to force the first digit to be non-zero.

Part 2: Smallest Rearranged Integer Strictly Greater Than lowerBound

Given a non-negative integer `n` and an integer `lowerBound`, rearrange all digits of `n` to form the smallest integer value that is strictly greater than `lowerBound`. Leading zeros are allowed in the rearranged digit string, so some zeros may disappear when the value is interpreted as an integer. Return `-1` if no rearrangement produces a value greater than `lowerBound`.

Constraints

`0 <= n <= 2,147,483,647`
`lowerBound` is an integer
The number of digits of `n` is at most 10
Leading zeros are allowed in the rearranged digit string
The result may exceed 32-bit signed range, but Python integers handle this safely

Examples

Input: (178, 200)

Expected Output: 718

Explanation: Among all permutations of 1, 7, and 8, the smallest value greater than 200 is 718.

Input: (1002, 20)

Expected Output: 21

Explanation: The permutation `0021` is allowed and becomes 21, which is the smallest value strictly greater than 20.

Input: (1002, 21)

Expected Output: 102

Explanation: 21 is not strictly greater than 21, and there is no other 2-digit answer. The next smallest valid result is 102 from `0102`.

Input: (321, 321)

Expected Output: -1

Explanation: 321 is already the largest permutation of these digits, so no rearrangement is strictly greater.

Input: (0, -1)

Expected Output: 0

Explanation: The only possible value is 0, and 0 is strictly greater than -1.

Hints

Only leading zeros can disappear. Every non-zero digit from `n` must still appear somewhere in the final integer.
For a fixed output length, try to match `lowerBound` from left to right. As soon as you place a larger digit, fill the rest with the smallest available digits.

Quick Overview

This question evaluates digit-manipulation and combinatorial permutation skills, along with numeric ordering and representation concerns such as leading zeros and overflow handling in the Coding & Algorithms domain.