Round 1
Questions: Given an array of n integers, data, find the lexicographically smallest permutation p such that the information gained for the given data is maximum. The information gained for a permutation p is defined as the sum of i * data[p[i]].
Example: Suppose n=3 and data =[2,1,2]
| Permutation | Information Gain | |------------------|-----------------------| | [1, 2, 3] | ( 12 + 21 + 32 = 10 ) | | [2, 1, 3] | ( 11 + 22 + 32 = 11 ) | | [1, 3, 2] | ( 12 + 22 + 31 = 9 ) | | [3, 1, 2] | ( 12 + 21 + 31 = 9 ) | | [2, 3, 1] | ( 11 + 22 + 32 = 11 ) | | [3, 2, 1] | ( 12 + 21 + 32 = 10 ) |
The maximum information is gained for permutations [2, 1, 3] and [2, 3, 1]. The lexicographically smaller permutation of the two is [2, 1, 3]: Hence the answer is [2, 1, 3].
Function Description:
Complete the function findOptimalPermutation which takes the following arguments:
int data[n]: the given data points
Returns:
int[n]: the lexicographically smallest permutation for which information gain is maximum.
Constraints:
- 1 ≤ n ≤ 10^5
- 1 ≤ data[i] ≤ 10^9
Input Format For Custom Testing: The first line contains an integer, n, the number of elements in data. Each of the next n lines contains an integer, data[i].
Sample Input For Custom Testing:
4 2 1 2 3
Sample Output:
2 1 3 4
Explanation: The information gain is maximum for [2, 1, 3, 4] which is equal to 1 * 1 + 2 * 2 + 3 * 2 + 4 * 3 = 23.
Implement the below function:
public static List<Integer> findOptimalPermutation(List<Integer> data) { // Implementation goes here }
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.