Amazon SDE-2 2025 OA

Round 1

Questions:

Question 1:

You have an array of data (index starting from 1) data = [3, 6, 1, 4, 2] Rearrange the data such that after the permutation, 1 * data[1] + 2 * data[2] + 3 * data[3] + ... n * data[n] is the largest.

Return the permutations as an array where each element represents the index after permutation (also starting from 1). If there are multiple equivalent answers, return the lexicographically smallest one.

Example: data = [3, 6, 1, 4, 2] -> answer [3, 5, 1, 4, 2] because 1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + 5 * 6 is the largest sum you can get.

Potential Solution: larger values stay later. Sort the array based on 1. value 2. if there's a tie, based on index.

Question 2:

You have an array of products, where each element contains how much product you have products = [2, 9, 4, 7, 5, 3] Pick a subarray of products. Starting from the beginning of the subarray, pick some number of products. One restriction: the number of products you pick have to be strictly increasing.

For example, you choose [7, 5, 3], you pick 4 products out of 7, 5 out of 5, there's nothing to pick from [3]. But you can pick [1, 2, 3], a total of 6 products.

The ask is to find the maximum number of products you can pick. The answer for the above example is 16. Because you pick [2, 9, 4, 7] subarray and [2, 3, 4, 7] products out of it.

1 <= len(products) <= 5000 the array length won't exceed 5000
1 <= products[i] <= 10^9, the stocks per product won't exceed 10^9.

Potential Solution: loop each element and treat it as the last element in the subarray where you grab all of it, have an inside loop to go backwards to pick as much as possible. O(n^2) runtime.