How should I practice Optimize Box IDs?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Optimize Box IDs associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

FastPrep

Problem · Stack

Optimize Box IDs

● HardAmazonOA

See Amazon hiring insights

The team at an Amazon warehouse is given a task to optimize the packing of a set of boxes with different IDs.

Each box is labeled with an ID, and these boxes are currently arranged in a single row from left to right, where the ID of the i-th box is represented by the string boxIds consisting of digits from 0 to 9 inclusive.

To make the packing more efficient, the team can perform the following operation any (possibly zero) number of times:

Choose an index i and remove the digit boxIds[i].
Then insert the box with ID min(boxIds[i] + 1, 9) on any position (at the beginning, at the end, or in between any two adjacent boxes) in the row.

Given a string boxIds, find the lexicographically minimal string of boxes using these operations.

Note: A string X is lexicographically smaller than a string Y of the same length if and only if: In the first position where X and Y differ, the string X has a smaller digit than the corresponding digit in Y.

Examples

01 · Example 1

boxIds = "26547"
return = "24677"

Delete 5 and insert 6 in the 4th position of the string → Delete 6 from the 2nd position and insert 7 in the 4th position of the string. Hence, the string returned is "24677". It can be proved that this is the lexicographically minimal string possible.

Constraints

1 <= |boxIds| <= 2 * 10^5

boxIds consists of only digits from 0 to 9. Note that boxIds is just a string consisting of digits, so leading zeros are allowed.