Amazon SDE Intern OA problems 💡

I recently gave Amazon OA where there were two DSA problems — one medium-level (greedy + simulation based) and the other hard (pairing for maximum)

🔹 Question 1:

The developers at Amazon are working on optimising the capacity of their cloud system. In the system, there are n servers where the memory capacity of the i-th server is represented by the array memory[i].

A system always contains an even number of servers. If the system has 2x servers, then x of them will be primary and the other x will be backup servers.

For each primary server P, there exists a backup server B where the memory capacity of B ≥ memory capacity of P. The system’s memory capacity is the sum of the memory capacity of all the primary servers.

Given n servers and an array memory, find the maximum system memory capacity that can be formed using the n servers.

Example Given 5 servers as [serverA, serverB, serverC, serverD, serverE] having memory = [2, 4, 3, 1, 2].

In the second configuration, the system memory capacity is memory[serverA] + memory[serverD] = 3. While in the third configuration, it is memory[serverA] + memory[serverC] = 5. Hence, the maximum system memory capacity is 5.

Function Description Complete the function maximumCapacity in the editor below. maximumCapacity has the following parameter:

• int memory[n]: the memory capacity of the given servers Returns
• long int: the maximum system memory capacity

Constraints 2 ≤ n ≤ 2*10^5 1 ≤ size[i] ≤ 10^9

Sample Case 0:

Input: 4 1 2 1 2

Output: 3

Explanation: Here, we have 4 servers [serverA, serverB, serverC, serverD] having memory sizes as [1, 2, 1, 2].

We can choose serverA and serverB as primary servers, and serverC and serverD as their respective backup. The conditions hold true since memory[serverC] ≥ memory[serverA] and memory[serverD] ≥ memory[serverB]. Hence, the maximum system memory capacity is 3.

Sample Case 1:

Input: 3 1 2 1

Output: 1

Explanation: Here, we have 3 servers [serverA, serverB, serverC] having memory sizes as [1, 2, 1].

We can choose serverA as a primary server, and serverB as its respective backup server. The conditions hold true since memory[serverB] ≥ memory[serverA]. Hence, the maximum system memory capacity is 1.

🔹 Question 2:

The manager of the Amazon warehouse has decided to make changes to the inventory by changing the prices of the products. Currently, the inventory has n products, where the price of the i-th product is represented by the array element prices[i].

The manager is given two integers:

• k:- which is the maximum amount by which a product’s price can be adjusted (increased or decreased) in a single operation, and
• d:- which represents the target price difference.

The goal is to ensure that the difference between the highest and lowest prices in the inventory is strictly less than d.

In order to make changes to the inventory, the manager can do the following operation any number of times:

• The manager selects two indices x, y (1 ≤ x, y ≤ n), and an integer p (1 ≤ p ≤ k).
• The manager increases the price of the product x by p.
• The manager decreases the price of the product y by p.

Given n products, an array prices, and the two integers k and d, find the minimum number of operations that the manager has to perform such that the maximum difference between the prices of any two products from the array of products is strictly less than d.

Note: The array prices follows 1-based indexing meaning the first element is at index 1 rather than 0.

Example Given n = 4, prices = [1, 5, 9, 11], k = 4, and d = 2.

One of the possible sequence of operations that modifies the prices in the optimal way is as follows:

The manager needs to perform a total of 3 operations. It is not possible to achieve the required condition, where the difference between the highest and lowest prices is strictly less than d = 2, in fewer than 3 operations. Therefore, the result is 3.

Function Description Complete the function minOperations in the editor. minOperations has the following parameters:

• int prices[n]: an array of integers representing the prices of n products
• int k: the maximum amount that a price can be increased or decreased by in one operation
• int d: the target difference

Returns int: the minimum number of operations required to ensure the condition is satisfied, i.e., the difference between the maximum and minimum prices of the array of products is strictly less than d.

Constraints 1 ≤ n ≤ 10^3 1 ≤ prices[i] ≤ 10^3 1 ≤ k ≤ 10^3 1 ≤ d ≤ 10^3

Sample Case 0:

Input: 3 1 4 6 1 2

Output: 2

Explanation: Here, we have 3 products with prices [1, 4, 6]. The manager can adjust prices with a maximum of k = 1 per operation, and the required maximum price difference is d = 2.

Now the max difference is 4 - 3 = 1, which is strictly less than d = 2. Hence, the manager needs to perform 2 operations.