Sort the Jumbled Numbers

Sort the Jumbled Numbers

What is this problem about?

In "Sort the Jumbled Numbers," you are given a mapping that defines a new order for digits 0-9. For example, if the mapping is [8, 9, 4, 0, 2, 1, 3, 5, 7, 6], it means 0 is mapped to 8, 1 is mapped to 9, 2 is mapped to 4, and so on.

You are also given an array of integers. You need to sort these integers based on their "mapped values." To find the mapped value of an integer, you replace each of its digits with the corresponding digit from the mapping. The original numerical values remain the same; only the sorting order is determined by the mapping. Importantly, the sort must be stable—if two numbers have the same mapped value, their relative order from the input must be preserved.

Why is this asked in interviews?

This interview question is a great test of custom sorting and digit manipulation. It is frequently asked at companies like Goldman Sachs and Google. It evaluates whether you can correctly transform data (integers to mapped values) without losing the original context and whether you understand the importance of stability in sorting. It also tests your ability to handle large numbers and edge cases like the number zero.

Algorithmic pattern used

The pattern is Transformation-based Sorting (similar to the Schwartzian Transform).

1. Pre-computation: For each number in the array, calculate its mapped value. This involves converting the number to a string or extracting its digits, applying the map, and converting it back to an integer.
2. Storage: Store the results as tuples or objects: (mapped_value, original_index, original_value). Including the index helps in implementing a stable sort if the language's default sort isn't stable.
3. Sorting: Sort the storage based on the mapped_value.
4. Result: Extract the original_value from the sorted list.

Example explanation

Mapping: [8, 9, 4, 0, 2, 1, 3, 5, 7, 6], Array: [991, 338]

• 991: 9 maps to 6, 1 maps to 9. Mapped value = 669.
• 338: 3 maps to 0, 8 maps to 7. Mapped value = 007 (which is 7).
• Since 7 < 669, 338 comes before 991. Result: [338, 991].

Common mistakes candidates make

A common error is not handling the digit 0 correctly—specifically, if a mapped value has leading zeros (like 338 mapping to 007), it should be treated as the integer 7. Another mistake is using an unstable sort, which violates the problem's requirements. Some candidates also struggle with the performance of string conversions; doing the mapping mathematically using division and modulo is usually more efficient.

Interview preparation tip

For the "Sort the Jumbled Numbers coding problem," focus on the mapping function. Make sure it can handle the number 0 (which is a common edge case). Discussing the trade-offs between string manipulation and mathematical digit extraction shows that you are a well-rounded engineer. Also, always check if your language's sort is stable by default (like in Python or Java for objects).