Sharing Amazon OA coding questions

Round 2

Questions: Given a string s_id, find the lexicographically minimal string of boxes using the following operations:

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

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.

Example: Given s_id = "26547".

• 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.

Function Description: Complete the function getMinimumString in the editor below. getMinimumString has the following parameter:

• string s_id: the ID of the boxes

Returns:

• string: the lexicographically minimal string.

Constraints:

• 1 ≤ |s_id| ≤ 2 * 10^5
• s_id consists of only digits from 0 to 9. Note that s_id is just a string consisting of digits, so leading zeros are allowed.

Input Format For Custom Testing: Sample Input:

04829

Sample Output:

02599

Explanation:

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.

---