CS-OA cs-vo Faang

Efficiently Sorting Weights in an Array – Amazon Coding Challenge Walkthrough-数组内重量排序优化 – 亚马逊编程挑战解析-亚马逊OA- Amazon OA

Imagine you are shopping on Amazon.com for some good weight lifting equipment. The equipment you want has blocks of many different weights that you can combine to lift.

The listing on Amazon gives you an array, blocks, that consists of n different weighted blocks, in kilograms. There are no two blocks with the same weight. The element blocks[i] denotes the weight of the ith block from the top of the stack. You consider weight lifting equipment to be good if the block at the top is the lightest, and the block at the bottom is the heaviest.

More formally, the equipment with array blocks will be called good weight lifting equipment if it satisfies the following conditions (assuming the index of the array starts from 1):

  • blocks[1] < blocks[i] for all (2 ≤ i ≤ n)
  • blocks[i] < blocks[n] for all (1 ≤ i ≤ n-1)

In one move, you can swap the order of adjacent blocks. Find out the minimum number of moves required to form good weight lifting equipment.


Let the blocks be in the order: blocks = [3, 2, 1]

In the first move, we swap the first and the second blocks. After swapping, the order becomes:

blocks = [2, 3, 1]

In the second move, we swap the second and the third blocks. After swapping, the order becomes:

blocks = [2, 1, 3]

In the third move, we swap the first and the second blocks. After swapping, the order becomes:

blocks = [1, 2, 3]

Now, the array satisfies the condition after 3 moves.

Function Description

Function Description Complete the function getMinNumMoves in the editor below.

getMinNumMoves has the following parameter: int blocks[n]: the distinct weights

Returns int: the minimum number of operations required


  • 2≤1052≤n≤105
  • 1≤blocks≤1091≤blocks[i]≤109 for all 1≤1≤in
  • blocks consists of distinct integers.


In this coding challenge, the objective is to reorder an array of distinct integer weights to satisfy specific sorting conditions. We are given an array, blocks, where each element represents the weight of a block. The goal is to reorder the blocks so that the lightest block is at the beginning of the array (top of the stack) and the heaviest block is at the end (bottom of the stack).

To achieve this, we must follow the rules laid out in the problem statement:

  1. blocks[1] should be less than all other weights in the array.
  2. Each blocks[i] (where 1 < i < n) should be less than blocks[n].
  3. We can only swap adjacent elements to reorder the array.

Our task is to write a function, getMinNumMoves, that calculates the minimum number of adjacent swaps required to sort the array according to the rules.

The challenge comes with specific constraints:

  • The number of blocks n is between 2 and 100,000.
  • The weight of each block is between 1 and 1 billion and is a distinct integer.

Before jumping into coding, an analysis of the problem suggests that this can be seen as a variant of the bubble sort problem, where we are interested in counting the swaps rather than actually sorting the array. However, given the potential size of the array, a naïve bubble sort approach would be inefficient and likely exceed the time limits for large inputs. We must therefore seek a more efficient method.

One approach is to first identify the positions of the lightest and the heaviest blocks. Since we can only perform adjacent swaps, the minimum number of moves required would be the sum of the moves to bring the lightest block to the beginning and the heaviest to the end. This can be achieved in a single pass from both ends of the array.

In summary, we will develop a solution that first identifies the target positions of the lightest and heaviest blocks, then calculates the minimum number of swaps needed to achieve the 'good weight lifting equipment' configuration.

在这个编程挑战中,目标是重新排序一个包含不同整数重量的数组,以满足特定的排序条件。我们被给定一个数组 blocks,其中每个元素代表一个块的重量。目标是重新排列这些块,使最轻的块在数组的开头(堆栈的顶部),最重的块在末尾(堆栈的底部)。


  1. blocks[1] 应该小于数组中的所有其他重量。
  2. 每个 blocks[i](其中 1 < i < n)应该小于 blocks[n]
  3. 我们只能交换相邻元素来重新排序数组。

我们的任务是编写一个函数 getMinNumMoves,该函数计算按照规则对数组排序所需的最少相邻交换次数。


  • 块的数量 n 在2到100,000之间。
  • 每个块的重量在1到10亿之间,且为不同的整数。





If you're afraid that you can't solve the OA on your own, please scan the code to contact me or telegram

It's a paid service will cost you 359usd.Make sure you can get the perfect score.

Leave a Reply

Your email address will not be published. Required fields are marked *