Panda Guru LogoPanda
Guru

Amazon SDE 2 Online assessment question - Jan 2025

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:

Returns:

Constraints:

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.