Company: AMAZON

Amazon Prime Video is developing a new feature called "Segmentify." This feature applies to a video with n (even) visual frames, where each frame is represented by a binary character in the array `frames`. In this format, a "0" represents a black pixel, and a "1" represents a white pixel.

Due to factors like lighting and camera angles, some frames may need horizontal or vertical flips (changing "0"s to "1"s and vice versa) to create consistent visuals. The objective is to divide the video into subsegments so that all frames in a subsegment are visually identical (i.e., the frames in a subsegment are either all "0"s or all "1"s). Additionally, each subsegment should have an even length.

The goal is to accomplish this segmentation with two criteria in mind:
1. Minimize the number of flips required to form valid segments — let this be denoted by B.
2. Among all configurations requiring B flips, minimize the total number of subsegments.

Given the binary string `frames`, determine the minimum number of such subsegments that meet the criteria.

Note: A subsegment is a segment that can be derived from another segment by deleting some elements without changing the order of the remaining elements.

Example:
`frames = "1110011000"`
One set of optimal moves is as follows:
- Flip the first 0 to 1 → "1111011000"
- Flip the next 0 to 1 → "1111111000"
- Flip the final 0 to 1 → "1111111100"

All resulting subsegments (11111111 and 00) are of even length. So, the minimum number of subsegments is 2 with a total of 3 flips. Hence, the answer is 2.

Another example:
`frames = "110011"`
In this case, the string already consists of groups of "0"s and "1"s that have even lengths. Therefore, no flipping is necessary, and the string can be divided into 3 even-length subsegments without modification. Hence, the answer is 3.

Function Description:
Complete the function `getminSubsegments` in the editor below.

`getminSubsegments` has the following parameter:
- string `frames`: the frames of the video as a binary string.

Returns:
- int: the minimum number of subsegments.

Constraints:
- 2 ≤ n ≤ 10^5, where n is even.
- It is guaranteed that the string `frames` only consists of '0's and '1's.

Sample Input:
`100110`

Sample Output:
2

Explanation:
Flip the first 0 to 1, resulting in "110110". All segments can then be grouped into even-length parts. Show More

Data scientists at Amazon are working on a utility for detecting similar passwords in their security systems. The utility finds anagram patterns in pairs of passwords. A pair of passwords is considered similar if they are anagrams after removing any number of occurrences of at most one character from each password.

Given n pairs of passwords, for each pair, attempt to make them anagrams. Return a list of boolean values, one for each pair, where True means a pair is similar.

Example
Given n = 1, and the strings password1 = "safddadfs" and password2 = "famafmss". The strings are anagrams after removing all the occurrences of character 'd' from the first password and character 'm' from the second password. Return [True].

Note: It is not required that all instances of a character be removed. For example, given 'aab' and 'ba', one 'a' can be removed from 'aab' to leave 'ab'.

Function Description
Complete the function findSimilarPasswords in the editor below.

findSimilarPasswords has the following parameter(s):
string password[n][2]: the pairs of passwords.

Returns
bool[n]: "true" if the pair is special, and "false" otherwise

Constraints
· 1 ≤ n ≤ 10
· 1 ≤ |password[i][0]|, |password[i][1]| ≤ 10,000
· The strings in password1 and password2 consist of lowercase English letters only.

Sample Case 0
Input
n = 2
password1 = "abcee", password2 = "acdeedb"
password1 = "sljffsaje", password2 = "sljsje"

Output
[True, False]

Explanation
For pair 1, remove 'd' from the second string and leave the first string untouched.
For pair 2, password1 contains 'f' and 'a' which are not in password2. They cannot be anagrams after removing only 1 character from password1.

Sample Case 1
Input
n = 1
password1 = "abcdee", password2 = "abcde"

Output
[True]

Explanation
Remove one occurrence of 'e' from password1. Show More

To be efficient, Amazon must optimally distribute parcels among their delivery agents. Initially, there are n agents, and the number of parcels assigned to the i-th agent is initialParcels[i]. There are additionalParcels parcels that also need to be shipped. The additional parcels should be assigned such that the maximum number of parcels assigned to any one agent is minimized.

Given an integer array, initialParcels, and an integer, additionalParcels, find the minimum possible value of the maximum number of parcels any agent must deliver.

Example
Suppose n = 5, initialParcels = [7, 5, 1, 9, 1], and additionalParcels = 25.
An optimal assignment is shown:

Initial Parcels | Additional Parcels | Total Parcels
7 | 3 | 10
5 | 5 | 10
1 | 9 | 10
9 | 1 | 10
1 | 7 | 8

There are other possible optimal assignments, but the minimum value of the maximum number of parcels any agent will deliver is 10.

Function Description
Complete the function minimizeMaxParcelLoad in the editor below.

minimizeMaxParcelLoad takes the following arguments:
int initialParcels[n]: the initial number of parcels assigned to the agents
long int additionalParcels: the additional parcels to be assigned

Returns
long int: the minimum possible value of the maximum number of parcels an agent must deliver

Constraints
· 1 ≤ n ≤ 10^5
· 1 ≤ additionalParcels ≤ 10^15
· 1 ≤ initialParcels[i] ≤ 10^9

Sample Input
initialParcels = [1, 2, 3]
additionalParcels = 3

Sample Output
3

Explanation
It is optimal to assign 2 additional parcels to the first agent and 1 additional parcel to the second agent. Finally, each agent will have to deliver 3 parcels. Show More

The Amazon warehouse receives a multitude of packages every day, each assigned a unique identifier from 1 to n. The warehouse manager must sort the packages, not by their identifiers, but rather through a specific process defined by a permutation packageSequence that ensures optimal processing.

Initially, the number of sorted packages, sortedCount, is zero. In each operation, the manager sifts through the packages from left to right. If the current package's identifier aligns with the next one to be sorted (i.e., packageSequence[i] = sortedCount + 1), the manager sorts it and increments sortedCount by one. If the current package is not next in the sorting sequence, the manager overlooks it.

Determine the number of operations required by the manager to sort all the packages. One operation indicates a complete check from the first package to the last.

Note: A permutation is a sequence consisting of integers from 1 to n, of length n, containing each integer exactly once. For example, [1, 3, 2] is a permutation, while [1, 2, 1] is not.

Example 1
n = 5
packageSequence = [5, 3, 4, 1, 2]
Initially sortedCount = 0. In the first operation, the manager does the following:
At the end of the third operation, sortedCount is 5, and all packages are sorted.
Thus, 3 operations are required to handle all the packages. Hence, the answer is 3.

Example 2
n = 5
packageSequence = [3, 1, 4, 2, 5]
In the first operation, the manager:
1. Overlooks packageSequence[0] = 3.
2. Sorts packageSequence[1] = 1 as packageSequence[1] = sortedCount + 1 = 1 (now sortedCount becomes 1).
3. Overlooks packageSequence[2] = 4.
4. Sorts packageSequence[3] = 2 as packageSequence[3] = sortedCount + 1 = 2 (now sortedCount becomes 2).
5. Overlooks packageSequence[4] = 5.
At the end of the first operation, sortedCount is 2.

In the second operation, the manager:
1. Sorts packageSequence[0] = 3 as packageSequence[0] = sortedCount + 1 = 3 (now sortedCount becomes 3).
2. Overlooks packageSequence[1] = 1.
3. Sorts packageSequence[2] = 4 as packageSequence[2] = sortedCount + 1 = 4 (now sortedCount becomes 4).
4. Overlooks packageSequence[3] = 2.
5. Sorts packageSequence[4] = 5 as packageSequence[4] = sortedCount + 1 = 5 (now sortedCount becomes 5).
At the end of the second operation, sortedCount is 5, and all packages are sorted.
Thus, 2 operations are required to handle all the packages. Hence, the answer is 2.

Function Description
Complete the function getNumberOperations in the editor below.

getNumberOperations has the following parameters:
int packageSequence[n]: an array of integers symbolizing the sequence of packages.

Returns
int: the number of operations the warehouse manager has to perform to sort all packages.

Constraints
· 1 ≤ n ≤ 10^6
· 1 ≤ packageSequence[i] ≤ n
· packageSequence is a permutation of length n. Show More

As an operations engineer at Amazon, you are responsible for organizing the distribution of n different items in the warehouse. The size of each product is provided in an array productSize, where productSize[i] represents the size of the i-th product.

You construct a new array called variation, where each element variation[i] is the difference between the largest and smallest product sizes amon g the first i products. Mathematically, this is defined as:

variation[i] = max(productSize[1], productSize[2], ..., productSize[i]) - min(productSize[1], productSize[2], ..., productSize[i])

Your goal is to arrange the products in a way that minimizes the total variation, i.e., the sum of variation[1] + variation[2] + ... + variation[n]. Determine the minimum possible value of this sum after you have reordered the products.

Example:
n = 3
productSize = [3, 1, 2]

By reordering the products as productSize = [2, 3, 1]:

- variation[0] = max(2) - min(2) = 2 - 2 = 0
- variation[1] = max(2, 3) - min(2, 3) = 3 - 2 = 1
- variation[2] = max(2, 3, 1) - min(2, 3, 1) = 3 - 1 = 2

The sum is variation[0] + variation[1] + variation[2] = 0 + 1 + 2 = 3. This is the minimum possible total variation after rearranging.

Function Description:
Complete the function minimizeVariation in the editor below.

minimizeVariation has the following parameter(s):
int productSize[n]: The size of each product.

Returns:
int: the minimum possible total variation after rearranging the array productSize.

Constraints:
1 ≤ n ≤ 2000
1 ≤ productSize[i] ≤ 10^6

Input Format for Custom Testing:
The first line contains an integer, n, the number of elements in productSize.
Each of the next n lines contains an integer describing productSize[i].

Sample Case 0:
Sample Input:
7
productSize = [4, 5, 4, 6, 2, 1, 1]

Sample Output:
4 Show More

Amazon Books is a retail store that sells the newly launched novel "The Story of Amazon". The novel is divided into n volumes numbered from 1 to n and unfortunately, all the volumes are currently out of stock.

The Amazon team announced that starting today, they will bring exactly one volume of "The Story of Amazon" in stock for each of the next n days. On the nth day, all volumes will be in sto ck. Being an impatient bookworm, each day you will purchase the maximum number of volumes you can such that:

- You have not purchased the volume before.
- You already own all prequels (prior volumes).

Note: For the ith volume of the novel, all the volumes j such that j < i are its prequels.

Determine the volumes you would purchase each day. You should return an array of n arrays where the ith array contains:

- The volume numbers sorted in increasing order if you purchased some volumes on the ith day.
- The single element -1 if you did not purchase any book.

Example:
volumes = [2, 1, 4, 3]

Initially, all volumes are out of stock:

- On the first day, Volume No. 2 becomes available. Since you do not own its prequel (Volume 1) yet, you will not purchase it. The answer for the first day is [-1].
- On the second day, Volume No. 1 becomes available. Now, you can purchase both volumes 1 and 2 together. The answer for the second day is [1, 2].
- On the third day, Volume No. 4 becomes available. Since you do not have one of its prequels (Volume 3) yet, you will not buy Volume 4. The answer for the third day is [-1].
- On the fourth day, Volume No. 3 becomes available. Now, you can purchase both volumes 3 and 4. The answer for the fourth day is [3, 4].

The final answer is:
[[-1], [1, 2], [-1], [3, 4]]

Function Description:
Complete the function orderBooks in the editor below.

orderBooks has the following parameter:
int volumes[n]: an array of integers where the ith integer denotes the volume that is in stock on the ith day

Returns:
int[][]: a 2D array of integers where the ith array denotes the volumes purchased on the ith day. Show More

In an Amazon analytics team, the Analysts collectively have a preference for the number zero and a disapproval towards negative numbers. Their objective is to determine the maximum number of zeroes achievable after performing a series of operations (possibly zero) on an array, all while avoiding negative values.

Formally, given an array sequenceData of size n of positive integers, the Analysts can perform the following operation any number of times (possibly zero):

- Choose a prefix of size s (1 ≤ s ≤ n) that doesn't contain any zero (there is no index i such that sequenceData[i] = 0 and 1 ≤ i ≤ s).
- Decrease all values of this prefix by one, i.e., set sequenceData[i] = sequenceData[i] - 1 for all 1 ≤ i ≤ s.

Find the maximum number of zeroes that the array sequenceData can contain after performing any (possibly zero) number of operations on the array.

Note that a prefix of size s in an array sequenceData is the first s elements in this array, for example, the prefix of size 3 of array [3, 1, 5, 5, 2] is [3, 1, 5].

Example:
n = 5
sequenceData = [4, 3, 5, 5, 3]

If we perform the following operations:

- No further operations can be done on the array, and the number of zeroes in sequenceData is 3, which is the maximum possible.

Function Description:
Complete the function calculateMaxZeroes in the editor below.

calculateMaxZeroes has the following parameters:
int sequenceData[]: the elements of the array

Returns:
int: the maximum number of zeroes that the array sequenceData can contain after performing any (possibly zero) number of operations on the array.

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

Input Format for Custom Testing:
The first line contains an integer, n, denoting the number of elements in sequenceData.
Each of the next n lines contains an integer describing sequenceData[i].

Sample Case 0:
Sample Input:
2
sequenceData[] size n = 5
sequenceData = [2, 5, 9, 3, 5]

Sample Output:
1

Explanation:
If we perform the following operations:
- [2, 5, 9, 3, 5] → [1, 4, 8, 3, 5]
- No further operations can be done on the array, and the number of zeroes in sequenceData is 1, which is the maximum possible.

Prefix Size:
4 → New Array: [1, 4, 8, 3, 5] → [0, 3, 7, 2, 5] Show More

AWS provides scalable systems. A set of n servers are used for horizontally scaling an application. The goal is to have the computational power of the servers in non-decreasing order. To do so, you can increase the computational power of each server in any contiguous segment by x. Choose the values of x such that after the computational powers are in non-decreasing order, the sum of the x values i s minimum.

Example:
There are n = 5 servers and their computational power = [3, 4, 1, 6, 2].
Add 3 units to the subarray (2, 4) and 4 units to the subarray (4, 4). The final arrangement of the servers is: [3, 4, 4, 9, 9]. The answer is 3 + 4 = 7.

Function Description:
Complete the function findMinimumSum in the editor below.

findMinimumSum has the following parameter(s):
int power[n]: the computational powers of n different servers

Returns:
int: the minimum possible sum of integers required to make the array non-decreasing

Constraints:
1 ≤ n ≤ 10^5
1 ≤ power[i] ≤ 10^9

Input Format For Custom Testing:
The first line contains an integer, n, denoting the number of elements in power.
Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer describing power.

Sample Case 0:
Sample Input:
3
power[] size n = 3
power = [3, 2, 1]

Sample Output:
1 Show More

Amazon has multiple delivery centers for the distribution of its goods. In one such center, parcels are arranged in a sequence where the ith parcel has a weight of weight[i]. A shipment is constituted of a contiguous segment of parcels in this arrangement.

For example, with weights [3, 6, 3], possible shipments include [3], [6], [3], [3, 6], [6, 3], and [3, 6, 3], but not [3, 3] (since it’s not contiguous).

These shipments are to be loaded for delivery and must be **balanced**.

A shipment is considered balanced **if the weight of the last parcel in the shipment is *not* the maximum weight** in that shipment.
- Example: [3, 9, 4, 7] is balanced because the last parcel is 7 and the max is 9.
- [4, 7, 2, 7] is **not** balanced since the last parcel (7) is also the maximum.

**Task:**
Given an array `weight` of size `n`, representing parcel weights, determine the **maximum number of balanced shipments** that can be formed such that:
- Each parcel belongs to exactly one shipment
- Each shipment is a contiguous subarray
- Each shipment is balanced

If no valid balanced shipment can be formed, return 0.

**Example:**
`weight = [1, 2, 3, 2, 6, 3]`
There are n = 6 parcels. The optimal way is to divide them into two shipments:
[1, 2, 3, 2] and [6, 3], both of which are balanced.
Hence, the output is `2`.

**Function Description:**
Complete the function `getMaximumBalancedShipments` in the editor below.

**Function Signature:**
`int getMaximumBalancedShipments(int[] weight)` Show More

A user is using the Amazon fitness tracker and is engaged in a jumping exercise routine. The user is positioned on the ground, and there are n blocks, each placed at different heights. The height of the ith block is represented by height[i] feet.

The goal is to maximize the calorie burn during this exercise. The calories burned when jumping from the ith block to the jth block is calculated as ( height[i] - height[j])².

The user intends to jump on each block exactly once but can choose the order in which they jump. Since the user wants to optimize calorie burn for this session, the task is to determine the **maximum amount of calories** that can be burned during the exercise.

Notes:
- The user can jump from any block to any block.
- The ground's height is 0.
- Once the user jumps from the ground to a block, they **cannot** go back to the ground.

Example:
n = 3
height = [5, 2, 5]

The user can jump in this sequence: Ground → 3rd block → 2nd block → 1st block
Calories burned:
(0 - 5)² + (5 - 2)² + (2 - 5)² = 25 + 9 + 9 = 43

It can be shown that no other order results in more than 43 units of calorie burn. Hence, the answer is 43.

Function Description:
Complete the function `optimizeCalorieBurn` in the editor below.

Function Signature:
`int optimizeCalorieBurn(int[] height)` Show More