Company: AMAZON

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 size s among the first i products. Mathematically, this is defined as:

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

Your goal is to arrange the products in a way that minimizes the total variation, i.e., the sum of variation[0] + variation[1] + ... + variation[n-1]. 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^9

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

Sample Output 0:
16

Explanation:
By reordering the products as productSize = [1, 1, 2, 4, 4, 5, 6]:

- variation[0] = max(1) - min(1) = 1 - 1 = 0.
- variation[1] = max(1, 1) - min(1, 1) = 1 - 1 = 0.
- variation[2] = max(1, 1, 2) - min(1, 1, 2) = 2 - 1 = 1.
- variation[3] = max(1, 1, 2, 4) - min(1, 1, 2, 4) = 4 - 1 = 3.
- variation[4] = max(1, 1, 2, 4, 4) - min(1, 1, 2, 4, 4) = 4 - 1 = 3.
- variation[5] = max(1, 1, 2, 4, 4, 5) - min(1, 1, 2, 4, 4, 5) = 5 - 1 = 4.
- variation[6] = max(1, 1, 2, 4, 4, 5, 6) - min(1, 1, 2, 4, 4, 5, 6) = 6 - 1 = 5.

The minimum total variation is variation[0] + variation[1] + variation[2] + variation[3] + variation[4] + variation[5] + variation[6] = 0 + 0 + 1 + 3 + 3 + 4 + 5 = 16. Show More

Amazon is launching a revolutionary security feature that incorporates an advanced antivirus program, adept at identifying and halting potential threats. This framework manages n active programs, each with a unique Program Identifier (PID). The antivirus program evaluates the overall security risk of the system using a specialized algorithm.

The algorithm analyzes contiguous subarrays of Progr am Identifiers (PIDs) represented by the array pid. For each subarray, it calculates the sum of the PIDs and divides this sum by a constant k. The remainder obtained from this division is compared to the number of programs in the subarray. A subarray is flagged if the remainder equals the number of programs within it and is considered as malicious. The overall security risk is determined by the total count of such flagged subarrays.

Formally, given an array pid of size n, representing the PIDs of the programs running on the computer, and an integer k, with which remainder has to be checked. The task is to calculate the system's security risk level. Remainder is defined as the remaining part after performing the division. For example, the remainder of 13 with 5 is 3. A subarray is a continuous portion of an array. For example, in the array [5, 7, 9, 11] possible subarrays include [5,7], [7, 9, 11], [11] etc. Note that a subarray maintains the original order of elements and consists of consecutive elements.

Example: n = 4, pid = [1, 3, 2, 4], k = 4. There are 2 different malicious contiguous subarrays:

1. Subarray from index [0, 0] with pid given by: [1], the remainder of the sum of pid (sum = 1) of the subarray [1] with k = 4 is 1 (the remainder of 1 with 4 is 1), which is equal to the number of elements in the subarray, i.e., 1. Hence, this subarray is flagged.
2. Subarray from index [2, 3] with pid given by: [2, 4], the remainder of the sum of pid (sum = 2 + 4 = 6) of the subarray with k = 4 is 2, which is equal to the number of elements in the subarray, i.e., 2. Hence, this subarray is flagged.

An example of a contiguous subarray which is not flagged:
- Subarray from index [0, 1] with pid given by: [3, 2] is not flagged because the remainder of the sum of PIDs = 3 + 2 = 5, whose remainder with k = 4, is 1, while there are 2 elements in the subarray. Hence, the subarray is not malicious.

Hence, the overall security risk of the system is 2. Thus, return 2 from the function.

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

findSecurityLevel has the following parameters:
int pid[n]: an array of integers denoting the PIDs of the programs
int k: an integer with which the remainder is checked

Returns: long: an integer denoting the overall security risk of the system

Constraints:
- 1 ≤ n ≤ 2 * 10^5
- 1 ≤ pid[i] ≤ 10^9
- 1 ≤ k ≤ 10^9 Show More

Amazon Games has recently launched a new game called Match the Column in which players are supposed to match the numbers from the left column to the right column like a traditional match the column game. Given an array of integers, match, the i-th index in the left column is matched with match[i] in the right column. There is a twist: Intersecting matches, illustrated below, are not allowed.

De termine the maximum number of matches possible without any intersections.

In the left illustration, match = [4, 3, 2, 3, 5].

More formally, two matches (i, match[i]) and (j, match[j]) intersect if i < j and match[i] > match[j] or i > j and match[i] ≤ match[j].

Example: Given n = 4, match = [2, 2, 1, 3]. There cannot be more than 2 valid matches, as shown above. Note that both illustrations are optimal. Return 2.

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

getMaxMatching has the following parameter: int match[n]: an array of integers

Returns: int: the maximum number of matchings possible

Constraints:
- 1 ≤ n ≤ 10^5
- 1 ≤ match[i] ≤ n

Input Format For Custom Testing:

Sample Case 0

Sample Input For Custom Testing:

STDIN
6
3
1
4
2
3
5

Function match[] size n = 6 match = [3, 1, 4, 2, 3, 5]

Sample Output:
4

Explanation: Given n = 6, match = [3, 1, 4, 2, 3, 5], the matchings are (1, 3), (2, 1), (3, 4), (4, 2), (5, 3), (6, 5). It is optimal to match (2, 1), (4, 2), (5, 3), (6, 5), none of which intersect. Show More

Todd has a grid sheet of paper measuring N by M units and plans to draw squares on it. Each cell in the grid contains an integer X, which represents the center of a square with dimensions (2X - 1) by (2X - 1). Given this grid, Todd wants to know how many squares enclose specific cells. You will be asked Q queries, each with two numbers A and B. Your task is to determine how many of Todd's squares enclose the cell (A, B).

Note: Todd's squares can intersect and form additional shapes, but you only need to consider the original squares he draws, not any new shapes formed by intersections. Even if one square entirely overlaps another, both should be considered separately. The coordinates (A, B) are 0-based. grid[i][j] will contain integer values such that Todd's squares are always contained inside the grid.

Input Format:
The first line contains three integers N, denoting the number of rows in the grid, M, the number of columns in the grid, and Q, the number of queries. The next N lines each contain M integers, representing the grid. The next Q lines each contain two integers: A and B, representing the cell coordinates for the queries.

Output Format:
For each query, print a single integer representing the number of squares that enclose the given cell (A, B).

Constraints:
1 <= N, M <= 10^3
0 <= grid[i][j] <= min(N/2, M/2)
1 <= Q <= 10^5
0 <= A <= N-1
0 <= B <= M-1

Sample Testcase 1:
Input:
5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 2 0 0
0 0 0 2 0
0 1 0 0 0
2 2

Output:
2

Explanation:
Todd's art will look like this: For the query (2, 2), the number of squares enclosing the point is 2 — the red square and the green square.

Sample Testcase 2:
Input:
3 3 2
0 1 0
0 2 1
0 0 0
0 1
1 1

Output:
2
1

Explanation:
Todd's art will look like this: The first query (0, 1) is enclosed by 2 squares, and the second query (1, 1) is enclosed by 1 square. Show More

You are given an 8x8 chess board. The board has your rook denoted by 'R' and the rest of the cells are either blank, denoted by 'B' or they have some piece upon them denoted by 'P'. You can move over the blank cells only. A rook can move along its entire row or column in 1 move, up to the point where blank spaces are available.

If current coordinates of a rook are (x, y) then rook can move in t he following ways in 1 move: Move from (x, y) to (x-1, y), (x-2, y), (x-3, y) and so on; Move from (x, y) to (x+1, y), (x+2, y), (x+3, y) and so on; Move from (x, y) to (x, y-1), (x, y-2), (x, y-3) and so on; Move from (x, y) to (x, y+1), (x, y+2), (x, y+3) and so on. The rook can't move outside the board. As soon as the rook encounters a 'P' cell in its path it stops and can't move further.

The rook needs to reach cell (8,8) in order to prove its worth. Find the minimum number of moves the rook would take to reach cell (8,8) or print -1 if it is impossible to do so. The board follows 1 based indexing. The board contains a single cell with value 'R'. Each string consists of only 3 types of characters: 'P', 'B', or 'R'.

Input Format: The first line contains a single integer T, the number of testcases. Lines from 1 to 8 of each test case take input of a string of size 8 denoting the arrangement on the chess board.

Output Format: Print the minimum number of moves required to reach cell (8,8) or print -1 if it is impossible to do so.

Constraints: 1 <= T <= 10^8, length of each string = 8.

Sample Testcase 1:
Input:
1
BBBBBBBB
BRPPPPPP
PBPPPPPP
PBPPPPPP
PBBBBPPP
PPBBBBBB
PPPPPPPB
PPPPPPPB

Output:
5

Explanation:
In the first move the rook can move from cell (2,2) to (5,2) as all cells in between are blank, i.e. cells (3,2), (4,2), (5,2) are blank. In the second move the rook can move from cell (5,2) to (5,4) as all cells in between are blank, i.e. cells (5,3), (5,4) are blank. In the third move the rook can move from cell (5,4) to (6,4). In the fourth move the rook can move from cell (6,4) to (6,8). In the fifth move the rook can move from cell (6,8) to (8,8). Path: (2,2) > (5,2) > (5,4) > (6,4) > (6,8) > (8,8). Thus, it took 5 moves for the rook to reach cell (8,8). There might be other possible paths too but none of them would take less than 5 moves.

Sample Testcase 2:
Input:
BBBBBBBB
BBBBBBBB
RBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBPP
BBBBBBPB

Output:
-1

Explanation:
Since cell (8,8) is blocked by pieces ('P') from all directions, it is impossible for the rook to reach cell (8,8) regardless of the path taken. Show More

Prince was playing games on his computer all day, so his father decided to give him the task of arranging the books kept on the bookshelf. Prince can arrange the books on the bookshelf according to the book type, where an English alphabet denotes each book type. He is required to arrange the books in such a way that the book type having the lowest number of copies is kept first, and the book type having the maximum number of copies is kept last. If two or more book types have the same number of books, arrange them in lexicographically ascending order.

You are given two numbers, L and R. Return the total number of books of type A E I O U between [L, R], which are present on the bookshelf.

Input Format: The first line contains an integer n denoting the number of books. The second line contains n space-separated uppercase English alphabets that denote the type of book. The third line contains two space-separated integers denoting L and R.

Output Format: Return the total number of books of type A E I O U between [L, R] on the bookshelf.

Constraints: 1 <= N <= 100. The book type is uppercase English alphabet only.

Sample Testcase 1
Input:
7
BBAABCC
1 2

Output:
2

Explanation: In this case, 2 books are of type A, 2 books are of type C, and 3 books are of type B. Hence, after arranging them according to the given condition, the shelf looks like this: AACCBBB (let's say string y). Here, the frequency of A and C are the same, so they are sorted in lexicographically ascending order. The distinct types of book that is kept on the shelf after arrangement is ACB (let's say string x). The value of L=1 and R=2. Therefore, the number of books of type A E I O U in the range [1,2] in string x is 1, i.e., the type A. The number of books of type A in string y is 2; hence, the answer is 2.

Sample Testcase 2
Input:
7
CABCABB
1 3

Output:
[Output not provided] Show More

You are given an NxN matrix 'mat' where each cell contains one of the two characters 'a' or 'z'. A man stands at the bottom-right corner of the matrix (mat[N-1][N-1]) and wants to reach the top-left corner of the matrix (mat[0][0]). The man can only move up or left at each step. Your task is to find the lexicographically smallest string that can be formed by following any valid path from mat[N-1][ N-1] to mat[0][0]. Additionally, determine the number of distinct paths that yield this lexicographically smallest string.

Input Format: First line of input takes integer 'N' denoting the dimensions of the matrix 'mat'. The next 'N' lines take 'N' space-separated characters either 'a' or 'z' representing the values in the matrix 'mat'.

Output Format: The first line of output shows the lexicographically smallest string that can be formed by any valid path from mat[N-1][N-1] to mat[0][0]. The last line of the output shows the number of distinct paths that yield this lexicographically smallest string.

Constraints: 2 <= N <= 40

Sample Testcase 1
Input:
3
z a z
a a a
z z z

Output:
zaaaz
2

Explanation: Starting from mat[2][2] = 'z', the next move can either be up or left. If we move up to mat[1][2] = 'a', then move left to mat[1][1] = 'a', then move either up or left to mat[1][0] or mat[0][1] = 'a', and finally move up to mat[0][0] = 'z', the path forms the string "zaaaz", the lexicographically smallest string. Therefore, the number of possible paths = 2.

Sample Testcase 2
Input:
4
z z a z
z z a a
z z a z
a a a a

Output:
aaaaazz
1

Explanation: Starting from mat[3][3] = 'a', the next move can either be up or left. Moving up to mat[2][3] = 'a', then up to mat[1][3] = 'a', then up to mat[0][3] = 'a', then left to mat[0][2] = 'a', then left to mat[0][1] = 'z', and finally left to mat[0][0] = 'z', the path forms the string "aaaaazz", which is the lexicographically smallest string. Therefore, the number of possible paths that form the string is 1. Show More

Your team at Amazon is working on a system that divides applications to a mixed cluster of computing devices. Each application is identified by an integer ID, requires a fixed non-zero amount of memory to execute, and is defined to be either a foreground or background application. IDs are guaranteed to be unique within their own application type, but not across types.

Each device should be assi gned two applications at once, one foreground application and one background application. Devices have limited amounts of memory and cannot execute applications that require more memory than the available memory. The goal of the system is to maximize the total utilization of the memory of a given device. A foreground/background application pair is considered to be optimal if there does not exist another pair that uses more memory than this pair, and also has a total less than or equal to the total memory of the device. For example, if the device has 10MB memory, a foreground/background pair using a sum total of 9MB memory would be optimal if there does not exist a pair that uses a sum total of 10MB, but would not be optimal if such a pair did exist.

Write an algorithm to find the sets of foreground and background application pairs that optimally utilize the given device for a given list of foreground applications and a given list of background applications.

Input
The input to the function/method consists of three arguments:
deviceCapacity, an integer representing the maximum capacity of the given device;
foregroundAppList, a list of pairs of integers where the first integer represents the unique ID of a foreground application and the second integer represents the amount of memory required by this application;
backgroundAppList, a list of pairs of integers where the first integer represents the unique ID of a background application and the second integer represents the amount of memory required by this application.

Output
Return a list of pairs of integers representing the pairs of IDs of foreground and background applications that optimally utilize the given device [foregroundAppID, backgroundAppID]. If no pair is possible, return a list with empty pair - not just an empty list.

Examples

Example 1:
Input:
deviceCapacity = 7
foregroundAppList = [[1,2], [2,4], [3,6]]
backgroundAppList = [[1,2]]

Output:
[[2,1]]

Explanation:
There are only three combinations, [1,1], [2,1], and [3,1], which use a total of 4, 6, and 8MB memory, respectively. Since 6 is the largest use that does not exceed 7, [2,1] is the only optimal pair.

Example 2:
Input:
deviceCapacity = 10
foregroundAppList = [[1, 3], [2, 5], [3, 7], [4, 10]]
backgroundAppList = [[1, 2], [2, 3], [3, 4], [4, 5]]

Output:
[[2, 4], [3, 2]]

Explanation:
There are two pairs of foreground and background applications possible that optimally utilize the given device.
Application 2 from foregroundAppList uses 5 memory units, and application 4 from backgroundAppList also uses 5 memory units. Combined, they add up to 10 units of memory.
Similarly, application 3 from foregroundAppList uses... Show More

Amazon's Alexa team is working on optimizing the customer experience for scenarios where customers ask generic questions.
One example of a generic question is "What are good vegetarian restaurants nearby?"

In this example, Alexa would then search for a list of vegetarian restaurants in the city and select the nearest X vegetarian
restaurants relative to the customer's location. Given an ar ray representing the locations of N vegetarian restaurants in
the city, implement an algorithm to find the nearest X vegetarian restaurants to the customer's location.

Input
The input to the function/method consists of two arguments:
- allLocations: a list of elements where each element consists of a pair of integers representing the x and y coordinates of
the vegetarian restaurant in the city
- numRestaurants: an integer representing the number of nearby vegetarian restaurants that would be returned to the customer (X)

Output
Return a list of elements where each element of the list represents the x and y integer coordinates of the nearest recommended
vegetarian restaurant relative to customer's location. If there is one tie, use the location with the closest X coordinate.
If no location is possible, return a list with an empty location - not just an empty list.

Constraints
numRestaurants ≤ size(allLocations)

Note
The customer begins at the location [0, 0].
The distance from the customer's current location to a recommended vegetarian restaurant location (x, y) is the square root of x² + y².
If there are ties then return any of the locations as long as you satisfy returning exactly X nearby vegetarian restaurants.
The returned output can be in any order.

Example
Input:
allLocations = [[1, 2], [3, 4], [1, -1]]
numRestaurants = 2

Output:
[[1, -1], [1, 2]]

Explanation:
The distance of the customer's current location from location [1, 2] is √5 ≈ 2.236
The distance from location [3, 4] is √25 = 5
The distance from location [1, -1] is √2 ≈ 1.414

The required number of vegetarian restaurants is 2, hence the output is [1, -1] and [1, 2]. Show More

A student is preparing for a scholarship test which is organized on the Amazon Academy platform and scheduled for next month.
There are n chapters to be studied where the ith chapter has pages[i] pages. In one day, the student decides to read up to p of the remaining pages, each from some k consecutive chapters. Thus, the number of pages remaining to be read is reduced by p from each of these cha pters. If a chapter has less than p pages remaining, the student reads the remaining pages, and the remaining page count is set to 0 for subsequent days.
Find the minimum number of days the student needs to read all the chapters completely, i.e., the remaining page count of all chapters is 0.
Note: The chapters read must be contiguous.

Example
The number of chapters is n = 3, the number of chapters read in a day is k = 2, the number of pages read from each chapter is p = 2, and the page counts of each chapter are pages = [3, 1, 4].

The chapters can be read as follows:
Chapters read must be contiguous.
- Choose chapters 1 and 2, remaining pages to be read = [1, 0, 4].
- Choose chapters 1 and 2, remaining pages to be read = [0, 0, 4].
- Choose chapters 2 and 3, remaining pages to be read = [0, 0, 2].
- Finally, choose chapters 2 and 3, remaining pages to be read = [0, 0, 0].
The chapters cannot be read in less than 4 days.

Function Description
Complete the function findMinimumDays in the editor below.

findMinimumDays has the following parameters:
int pages[n]: the number of pages in each chapter
int k: the number of chapters chosen each day
int p: the maximum number of pages read from

Returns
long_int: the minimum number of days to read all pages of all chapters

Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ pages[i] ≤ 10^9
- 1 ≤ k ≤ n
- 1 ≤ p ≤ 10^9

Input Format For Custom Testing

Sample Case 0
Sample Input For Custom Testing
STDIN
2
FUNCTION
3
4
1
2

pages[] size n = 2
pages = [3, 4]
k = 1
p = 2

Sample Output
4

Explanation
Read the first chapter for the first two days,
and the second chapter for the next two days.

Sample Case 1
Sample Input For Custom Testing
STDIN
FUNCTION
3
5

pages[] size n = 3
pages = [5, 1, 2]
1
2
3
3

k = 3
p = 3

Sample Output
2

Explanation
After 1st day, the number of pages remaining = [2, 0, 0].
After 2nd day, the number of pages remaining = [0, 0, 0]. Show More