Problem Statement |
| | Many economists like to represent objects with numbers and compare them using various measures. For example, when shopping for houses, they may represent attributes like cost, number of bedrooms, and distance from work as numbers. They can then prioritize these attributes and easily determine the best match. Consider the following 4 houses:
- A: $100,000, 2 bedrooms, 30 minutes from work
- B: $200,000, 3 bedrooms, 10 minutes from work
- C: $300,000, 3 bedrooms, 10 minutes from work
- D: $100,000, 3 bedrooms, 20 minutes from work
One way to prioritize the attributes is as follows:
1) The most important attribute is the number of bedrooms. We don't need a big house, so among all the houses, prefer the ones that have less bedrooms.
2) The second most important attribute is the distance to work. Among houses that are tied after step 1, prefer the ones that are closer to work.
3) The least important attribute is cost. Among houses that are still tied after step 2, prefer the ones that cost less.
If we sort the 4 houses above using this prioritization, we get (from most to least preferred): A, B, C, D. House A is preferred over all other houses because it has 2 bedrooms, while B, C and D have 3 bedrooms each. Houses B and C are preferred over house D because they they are closer to work than D. And, finally, house B is preferred over house C because B is cheaper.
Your friend Helen is shopping for houses, but she forgot to bring her prioritized list of attributes. Luckily, she does have a list of houses that were sorted according to that prioritization. She has asked you to help her recover the prioritized list of attributes.
You are given a String[] clues containing the list of houses sorted from most to least preferred. Each element of clues represents one house and contains the values of the attributes for that house. The i-th character (0-indexed) is the value of the i-th attribute, and is a hexadecimal digit ('0'-'9','A'-'F'). Lower values are preferred to higher values for all attributes. You must determine the order in which the attributes were prioritized to produce this list. Assume that after the given list was sorted, there were no ties (meaning no two houses were equally as good according to the prioritization).
Return a String containing the indices (0-indexed) of the prioritized attributes from most to least important. If there is no possible prioritized attribute list, return "IMPOSSIBLE" instead, and if there is more than one possible answer, return "TOO MANY" (all quotes for clarity).
|
| |
Definition |
| | | Class: | LostSortingAlgorithm | | Method: | recoverSortingAlgorithm | | Parameters: | String[] | | Returns: | String | | Method signature: | String recoverSortingAlgorithm(String[] clues) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | clues will contain between 1 and 50 elements, inclusive. |
| - | Each element of clues will contain between 1 and 8 characters, inclusive. |
| - | Each element of clues will contain only digits ('0'-'9') and uppercase letters ('A'-'F'). |
| - | All elements of clues will be of the same length. |
| - | All elements of clues will be distinct. |
| |
Examples |
| 0) | |
| | {"12D", "23A", "33A", "13B"} |
| Returns: "120" | | The example from the statement. Four elements of the input represent four houses, where the first character of each element represents the cost ('1' corresponds to $100,000, '2' - to $200,000, and 3 - to $300,000), the second character represents the number of bedrooms, and the third character of each element represents the distance to work ('A' corresponds to 10 minutes, 'B' - to 20 minutes and 'D' - to 30 minutes).
The prioritized list of attributes in this case must be "120" (number of bedrooms, distance from work, cost - this is the example we used above). |
|
|
| 1) | |
| | |
| 2) | |
| | |
| 3) | |
| | |
| 4) | |
| | {"0","1","2","3","4","7","6"} |
| Returns: "IMPOSSIBLE" | |
|
| 5) | |
| | {"0123","1234","2345","0145","1245","2346"} |
| Returns: "IMPOSSIBLE" | |
|
| 6) | |
| | {"0123","0145","1234","1245","2345","2346"} |
| Returns: "TOO MANY" | |
|
| 7) | |
| | {"CC0","2F0","4A1","FB1","542","362","462","172"} |
| Returns: "210" | |
|