Amazon OA Interview Question: Quality Minimum Replacement Cost

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

The manager wants to create an optimal inventory, where the array of products quality follows this property:

• All occurrences of each quality value must be contiguous.

In order to convert the inventory into an optimal inventory, the manager can do the following operation any number of times:

• Choose two quality values x and y.
• Replace every product with quality x to have quality y instead.
• This operation costs num_replacements units of money, where num_replacements is the number of products whose quality was changed.

Given n products and an array quality, find the minimum amount of money the manager has to spend to convert the inventory into an optimal inventory.

Note: The quality of a product can be negative, indicating that the product is of poor quality.

Example:

Given n = 7, quality = [7, 7, 5, 7, 3, 5, 3].

One of the optimal ways to convert is explained below:

• Replace all products of quality 5 with 7, and then replace all products of quality 3 with 7.

Hence, the total amount spent is 4.

Function Description

Complete the function getMinAmount in the editor below.

getMinAmount has the following parameter(s):

• int quality[n]: the quality of products

Returns

• int: the minimum amount of money the manager has to spend to convert the inventory into an optimal inventory.

This Amazon OA problem asks for the minimum cost to transform an array so that all equal values become contiguous. The optimal strategy is to keep the largest useful blocks of repeated values and replace the rest, which makes frequency counting and interval grouping the key ideas. A typical solution uses hash maps to track occurrences, first/last positions, and then scans the array to compute how many elements can be preserved in each grouped segment. The answer is the total number of replacements needed to merge scattered equal values into contiguous runs.