Code Question 1

Problem Description
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 ith 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.

Examples
Consider the following conceptual examples for selecting primary and backup servers:

Primary Servers Backup Servers Conditions Valid

Options Options Option

serverA, serverB serverC, serverD memory[serverA] ≤ No

memory[serverC]
memory[serverB] ≤
memory[serverD]

serverA, serverD serverB, serverE memory[serverA] ≤ Yes

memory[serverB]
memory[serverD] ≤
memory[serverE]

serverA, serverC serverE, serverB memory[serverA] ≤ Yes

memory[serverE]
memory[serverC] ≤
memory[serverB]

●​
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.

Example 1: (Sample Case 0)

Input: n = 4, memory = [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.

Example 2: (Sample Case 1)

Input: n = 3, memory = [1, 2, 1]
Output: 1
Explanation: Here, we have 3 servers [serverA, serverB, serverC] having memory sizes as
[1, 2, 1] respectively. 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.

Note: The problem statement specifies that a system always contains an even number of
servers. Example 2 (Sample Case 1) uses n=3, which is an odd number. This might be a
discrepancy in the problem description or an edge case to consider.

Constraints
●​ 2 ≤ n ≤ 2 * 10^5
●​ 1 ≤ memory[i] ≤ 10^9

Sol:​
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

long maximumCapacity(int memory_count, int* memory) {

std::sort(memory, memory + memory_count);

●​
 long long total_capacity = 0;
if (memory_count % 2 == 0) {
for (int i = 0; i < memory_count; i += 2) {
total_capacity += memory[i];
}
} else {
for (int i = 1; i < memory_count; i += 2) {
total_capacity += memory[i];
}
}
return total_capacity;
}

​
​

Modified Knapsack Problem

Problem Description
Given n items where:

●​ The weight of the ith item is 2i using 0-based indexing.

●​ The cost of the ith item is cost[i].

Find the minimum amount needed to purchase items whose combined weight is at least
minWeight. Multiple units of an item can be purchased.

Example

n = 5​
cost = [2, 5, 7, 11, 25]​
minWeight = 26

An optimal purchase strategy is:

●​ Buy 2 units at cost[0] and 3 units at cost[3] per item

●​ Total cost = 2 * 2 + 3 * 11 = 4 + 33 = 37
●​ Total weight = (2 * 20) + (3 * 23) = 2 + 24 = 26, which meets the
minimum weight requirement.

●​
The answer is 37, representing the minimum cost to achieve the weight requirement.

Function Description

Complete the function getMinimunCost in the editor with the following parameters:

int cost[]: the cost of each item​

int minWeight: the minimum combined weight of the items

Returns

long_int: the minimum amount needed to purchase the items

Examples
Example 1:
Input:
5
4
3
2
1
10
2
Output:
1
Explanation: It is optimal to buy 1 unit of item 3 which has a weight of 23 = 8 units (greater

than minWeight = 2) and has a cost of 1.

Example 2:
Input:
4
10
9
8
10
14
Output:
20

●​
Explanation: It is optimal to buy 2 units of item 0 (0-based), which weighs 8 units. Total
combined weight = 2 * 8 = 16, which is greater than minWeight. Total cost = 2 * 10

= 20.

Constraints
●​ 1 <= n <= 30
●​ 1 <= cost[i] <= 109
●​ 1 <= minWeight <= 109

Sol:​
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>

int getMinPath(std::vector<int> coins, int tree_nodes,

std::vector<int> tree_from, std::vector<int> tree_to) {
if (tree_nodes <= 1) {
return 0;
}

std::vector<std::unordered_set<int>> adj(tree_nodes);
for (size_t i = 0; i < tree_from.size(); ++i) {
adj[tree_from[i]].insert(tree_to[i]);
adj[tree_to[i]].insert(tree_from[i]);
}

int remaining_nodes = tree_nodes;

std::queue<int> q;

for (int i = 0; i < tree_nodes; ++i) {

if (adj[i].size() == 1 && coins[i] == 0) {
q.push(i);
}
}

while (!q.empty()) {
int u = q.front();
q.pop();
remaining_nodes--;

if (adj[u].empty()) continue;

int v = *adj[u].begin();

●​
 adj[u].clear();
adj[v].erase(u);

if (adj[v].size() == 1 && coins[v] == 0) {

q.push(v);
}
}

if (remaining_nodes <= 2) {
return 0;
}

for (int level = 0; level < 2; ++level) {

if (remaining_nodes <= 2) {
break;
}
std::queue<int> leaves;
for (int i = 0; i < tree_nodes; ++i) {
if (adj[i].size() == 1) {
leaves.push(i);
}
}

if (leaves.empty()) {
break;
}

remaining_nodes -= leaves.size();

while(!leaves.empty()){
int u = leaves.front();
leaves.pop();

if (adj[u].empty()) continue;

int v = *adj[u].begin();
adj[u].clear();
adj[v].erase(u);
}
}

if (remaining_nodes <= 1) {
return 0;
}

return 2 * (remaining_nodes - 1);

}

●​
Collect The Coins
Problem Description
Alex is playing a game in Hackerland and needs to collect coins from various locations. The
city is represented as a tree with n vertices labeled from 0 to n - 1. There is an array called
coins of size n, where coins[i] is either 0 or 1, where 1 means the vertex contains a coin.

Alex must travel the tree's edges to collect all the coins. The distance between two vertices
is the number of edges between them. From any given vertex x, Alex can collect all coins
located within a distance of 2 edges from x.

The goal is to find the shortest path that allows Alex to collect all the coins. Alex can choose
any vertex, but must start and end at that vertex. The path can traverse the same edge
multiple times, and all edges are bidirectional.

Return the number of edges in the shortest path along which Alex can collect all the coins.

The function is expected to return an INTEGER.

The function accepts the following parameters:

int getMinPath(vector coins, int tree_nodes, vector tree_from,

vector tree_to)

●​ coins: an array of tree_nodes integers representing coins at each vertex.

●​ tree_nodes: the number of nodes in the graph.
●​ tree_from: one node of each bidirectional edge.
●​ tree_to: the other node of each bidirectional edge.

Returns:

●​
int: the number of edges in the shortest path.

Examples
Example 1:
Input:
tree_nodes = 12
coins = [1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1]
tree_from = [0, 0, 1, 2, 3, 4, 5, 6, 8, 9, 10]
tree_to = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Output: 10
Explanation: One optimum path is to start at vertex 3 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 6 -> 4 ->
3 -> 9 -> 11. Collect coins from vertices 2 (coins at 0, 2 and 3), 6 (coins at 6 and 8), and 9
(coin at vertex 11).

Example 2:
Input:
tree_nodes = 10
coins = [1, 0, 1, 1, 1, 0, 0, 0, 1, 1]
tree_from = [0, 0, 0, 0, 1, 6, 7, 8]
tree_to = [1, 2, 3, 4, 5, 7, 8, 9]
Output: 4

Constraints
●​ 2 <= tree_nodes <= 10^5
●​ coins[i] = 0 or coins[i] = 1, where 0 <= i < tree_nodes
●​ 0 <= tree_from[i] < tree_nodes where 0 <= i < tree_nodes - 1
●​ 0 <= tree_to[i] < tree_nodes where 0 <= i < tree_nodes - 1

Sol:
​
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>

int getMinPath(std::vector<int> coins, int tree_nodes,

std::vector<int> tree_from, std::vector<int> tree_to) {
if (tree_nodes <= 1) {
return 0;
}

●​
 std::vector<std::unordered_set<int>> adj(tree_nodes);
for (size_t i = 0; i < tree_from.size(); ++i) {
adj[tree_from[i]].insert(tree_to[i]);
adj[tree_to[i]].insert(tree_from[i]);
}

int remaining_nodes = tree_nodes;

std::queue<int> q;

for (int i = 0; i < tree_nodes; ++i) {

if (adj[i].size() == 1 && coins[i] == 0) {
q.push(i);
}
}

while (!q.empty()) {
int u = q.front();
q.pop();
remaining_nodes--;

if (adj[u].empty()) continue;

int v = *adj[u].begin();
adj[u].clear();
adj[v].erase(u);

if (adj[v].size() == 1 && coins[v] == 0) {

q.push(v);
}
}

if (remaining_nodes <= 2) {
return 0;
}

for (int level = 0; level < 2; ++level) {

if (remaining_nodes <= 2) {
break;
}
std::queue<int> leaves;
for (int i = 0; i < tree_nodes; ++i) {
if (adj[i].size() == 1) {
leaves.push(i);
}
}

if (leaves.empty()) {

●​
 break;
}

remaining_nodes -= leaves.size();

while(!leaves.empty()){
int u = leaves.front();
leaves.pop();

if (adj[u].empty()) continue;

int v = *adj[u].begin();
adj[u].clear();
adj[v].erase(u);
}
}

if (remaining_nodes <= 1) {
return 0;
}

return 2 * (remaining_nodes - 1);

}

Lexicographically Smallest Sequence

Problem Description
Data scientists at Amazon are working on a utility to generate data points for their models
based on existing data points.

A simple prototype takes in two integers, n, and sequence_sum, and generates a

sequence of size n whose sum of elements equals sequence_sum, and the absolute

values of the elements form a permutation of size n. The utility reports the lexicographically

smallest such sequence.

Given two integers, n, and sequence_sum, return the lexicographically smallest sequence

of integers such that:

1.​ The sum of its elements equals sequence_sum.

●​
 2.​ The absolute values of its elements form a permutation of size n.

Note: A sequence of n integers is a permutation if it contains all integers from 1 to n exactly

once. For example, [1, 4, 2, 5, 3] is a permutation but [2, 3, 4, 5] is not.

Given two permutations x and y, x is lexicographically smaller than y if there exists an index

i where x[i] < y[i] and for this smallest index j < i, x[j] == y[j]. This means

that when comparing two elements by scanning from the start, the first position at which they
differ determines their order. If the element in x is less than the corresponding element in y

at this position, x is considered smaller.

Examples
Example 1:
Suppose n = 5, sequence_sum = 9

Some sequences of size n = 5 with sequence_sum = 9 are:

Sequence Sum
[-1, 2, 3, 4, 5] 9
[-2, 1, 3, 4, 5] 9
[-3, 1, 2, 4, 5] 9
[3, 4, 5, -2, -1] 9
[3, 2, 1, 4, 5] 9
Explanation: Now we can clearly see [-3, 1, 2, 4, 5] is lexicographically smaller than

[-3, 2, 1, 4, 5] because 1 < 2 at the first index where they differ. The

lexicographically smallest sequence with the given sum is [-3, 1, 2, 4, 5].

Function Description
Complete the function getSmallestSequence in the editor below.

getSmallestSequence has the following parameters:

●​ int n: the number of elements in the sequence

●​ long int sequence_sum: the sum of elements in the sequence

●​
Returns

●​ int[]: the lexicographically smallest sequence of n integers following the above

criteria. If it is not possible, return an array of size n filled with zeros.

Constraints
●​ 1 <= n <= 10^5
●​ -10^10 <= sequence_sum <= 10^10

Sol:​
#include <vector>
#include <numeric>

std::vector<int> getSmallestSequence(int n, long long

sequence_sum) {
long long max_total_sum = (long long)n * (n + 1) / 2;

if (sequence_sum < -max_total_sum || sequence_sum >

max_total_sum || (max_total_sum - sequence_sum) % 2 != 0) {
return std::vector<int>(n, 0);
}

std::vector<int> result;
result.reserve(n);
std::vector<bool> used(n + 1, false);
long long current_target_sum = sequence_sum;
long long sum_of_unused_abs = max_total_sum;

for (int i = 0; i < n; ++i) {

bool found_choice_for_i = false;

for (int k = n; k >= 1; --k) {

if (used[k]) {
continue;
}

int v = -k;
long long sum_of_abs_for_rem = sum_of_unused_abs - k;
long long min_rem_sum = -sum_of_abs_for_rem;
long long max_rem_sum = sum_of_abs_for_rem;
long long rem_target_sum = current_target_sum - v;

if (rem_target_sum >= min_rem_sum && rem_target_sum <=

max_rem_sum) {
if ((max_rem_sum - rem_target_sum) % 2 == 0) {

●​
 result.push_back(v);
current_target_sum -= v;
used[k] = true;
sum_of_unused_abs -= k;
found_choice_for_i = true;
break;
}
}
}

if (found_choice_for_i) {
continue;
}

for (int k = 1; k <= n; ++k) {

if (used[k]) {
continue;
}

int v = k;
long long sum_of_abs_for_rem = sum_of_unused_abs - k;
long long min_rem_sum = -sum_of_abs_for_rem;
long long max_rem_sum = sum_of_abs_for_rem;
long long rem_target_sum = current_target_sum - v;

if (rem_target_sum >= min_rem_sum && rem_target_sum <=

max_rem_sum) {
if ((max_rem_sum - rem_target_sum) % 2 == 0) {
result.push_back(v);
current_target_sum -= v;
used[k] = true;
sum_of_unused_abs -= k;
break;
}
}
}
}

return result;
}

Query Process Activity

Problem Description

●​
You are a developer at Amazon evaluating the performance of processing units. There are n

processes, where each process i runs from starts[i] to ends[i] (both inclusive).

You are given q queries, each defined by three arrays:

●​ query_process[j] → the exact number of processes to check.

●​ query_start[j] → the start time of the query interval.
●​ query_end[j] → the end time of the query interval.

For each query j, determine how many seconds within query_start[j],

query_end[j] (inclusive) have exactly query_process[j] processes running.

Return an array of size q with the result for each query.

Examples
Example 1:
Input:
starts = [0, 1, 2]
ends = [2, 10, 9]
query_process = [0, 2]
query_start = [1, 4]
query_end = [10, 9]
The following table illustrates the process status over time based on the example input (note:
the `starts` and `ends` arrays might lead to a slightly different interpretation of process
activity than the table's "Process Status" events):

Time Process Status In Execution

0 process 0 starts [0]

1 process 1 starts [0, 1]

2 process 2 starts, process 0 ends [1, 2]

●​
 3 - [1, 2]

4 - [1, 2]

5 - [1, 2]

6 process 1 ends [2]

7 - [2]

8 - [2]

9 process 2 ends []

10 - []

11 - []

Explanation: (Note: The following explanation uses `query_process` values of 1 and 2 for the
first and second queries respectively, which might differ from the `query_process = [0, 2]` in
the input. This explanation is provided as-is from the problem statement.)

For the first query, the answer is the number of seconds between the 1st and 10th second
(both inclusive), where exactly 1 process is executing, i.e., (6, 7, 8, 9, 10). The answer to this
query is 5.

For the second query, the answer is the number of seconds between the 4th and 9th second
(both inclusive), where exactly 2 processes are executing, i.e., (4, 5). The answer to this
query is 2.

Hence, the answer array reported is [5, 2].

●​
Output: [5,2]

Function Description
Complete the function getqueryAnswers in the editor below. The function must return an

array where ith integer denotes the answer to the ith query.

getqueryAnswers has the following parameters:

●​ int starts[n]: the starting times of the processes

●​ int ends[n]: the ending times of the processes
●​ int query_process[q]: the num_process component of each query
●​ int query_start[q]: the start time component of each query
●​ int query_end[q]: the end time component of each query

Returns:

●​ int[]: the answer to each query

Constraints
●​ 1 <= n <= 105
●​ 0 <= starts[i] <= ends[i] <= 109
●​ 0 <= q <= 105
●​ 0 <= query_start[j] <= query_end[j] <= 109
●​ 0 <= query_process[j] <= n

Input Format for Custom Testing

The first line contains an integer n, the size of starts and ends. The next n lines contain

elements of starts. The next n lines contain elements of ends. The next line contains an

integer q, the size of query_process, query_start, and query_end. The next q lines

contain elements of query_process. The next q lines contain elements of query_start.

The next q lines contain elements of query_end.

Sample Input

●​
3
0
1
2
3
2
10
9
2
0
2
1
4
10
9
Sample Output

5
2
Explanation:

(Note: This explanation section appears to have inconsistencies with the provided example
input and previous explanation.)

●​ Find the number of seconds between the 1st and 10th second (both inclusive) where
no process was being executed, i.e., (13, 14, 15, 16, 17, 18, 19, 20).
●​ Find the number of seconds between the 4th and 9th second (both inclusive) where
exactly 2 processes are executing, i.e., (4, 5).

Sol:​
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <limits>
#include <iterator>

long long getTotalLength(int t, int k,

const std::map<int,
std::vector<std::pair<int, int>>>& intervals_by_count,
const std::map<int, std::vector<long
long>>& prefix_lengths) {
if (t < 0) {
return 0;

●​
 }
auto it_k = intervals_by_count.find(k);
if (it_k == intervals_by_count.end()) {
return 0;
}

const auto& intervals = it_k->second;

const auto& prefixes = prefix_lengths.at(k);

if (intervals.empty()) {
return 0;
}

auto it = std::upper_bound(intervals.begin(), intervals.end(),

std::make_pair(t, std::numeric_limits<int>::max()));

int idx = std::distance(intervals.begin(), it);

if (idx == 0) {
return 0;
}

long long total_len = 0;

if (idx > 1) {
total_len = prefixes[idx - 2];
}

const auto& last_interval = intervals[idx - 1];

int s = last_interval.first;
int e = last_interval.second;

total_len += (long long)std::min(e, t) - s + 1;

return total_len;
}

std::vector<int> getQueryAnswers(std::vector<int> starts,

std::vector<int> ends,
std::vector<int> query_process,
std::vector<int> query_start, std::vector<int> query_end) {

std::map<int, int> events;

int max_coord = 0;
if (!ends.empty() || !query_end.empty()){
for (int e : ends) max_coord = std::max(max_coord, e);
for (int qe : query_end) max_coord = std::max(max_coord,
qe);
}

●​
 for (size_t i = 0; i < starts.size(); ++i) {
events[starts[i]]++;
if (ends[i] < std::numeric_limits<int>::max()) {
events[ends[i] + 1]--;
}
}

if (max_coord < std::numeric_limits<int>::max() - 1) {

events[max_coord + 2] += 0;
} else if (!events.empty()){
int last_key = events.rbegin()->first;
if (last_key < std::numeric_limits<int>::max()){
events[last_key + 1] += 0;
}
}

std::map<int, std::vector<std::pair<int, int>>>

intervals_by_count;
int current_count = 0;
int last_time = 0;

for (const auto& [time, change] : events) {

if (time > last_time) {

intervals_by_count[current_count].push_back({last_time, time -
1});
}
current_count += change;
last_time = time;
}

if (events.empty() && !query_process.empty()){

intervals_by_count[0].push_back({0, max_coord + 1});
}

std::map<int, std::vector<long long>> prefix_lengths;

for (auto const& [k, intervals] : intervals_by_count) {
if(intervals.empty()) continue;
long long current_sum = 0;
prefix_lengths[k].reserve(intervals.size());
for (const auto& p : intervals) {
current_sum += (long long)p.second - p.first + 1;
prefix_lengths[k].push_back(current_sum);
}
}

●​
 std::vector<int> answers;
answers.reserve(query_process.size());
for (size_t i = 0; i < query_process.size(); ++i) {
int p = query_process[i];
int s = query_start[i];
int e = query_end[i];

long long len_at_end = getTotalLength(e, p,

intervals_by_count, prefix_lengths);
long long len_before_start = getTotalLength(s - 1, p,
intervals_by_count, prefix_lengths);

answers.push_back(static_cast<int>(len_at_end -
len_before_start));
}

return answers;
}

Code Question 2
Problem Description
At Amazon's internal developer summit, two engineers, Alex and Charlie are competing in a
fun coding duel challenge. They are given a string S composed of lowercase English letters.

The game rules are as follows:

●​ Alex and Charlie take turns removing one character at a time, with Alex going first.
●​ The game continues until only one character is left in the string.

The engineers adopt the following removal strategy:

●​ Alex's strategy: Remove a character that results in the smallest possible string
(lexicographically).
●​ Charlie's strategy: Remove a character that results in the largest possible string
(lexicographically).

●​
Your task is to simulate this process and determine the final character left in the string after
all removals with Alex making the first move.

Note: To compare two strings, the lexicographical order is defined as follows:

●​ Start by comparing character by character from left to right of the string.

●​ The string with the first different character that appears earlier in the alphabet is
smaller. For example, "abc" < "abd" because 'c' comes before 'd'.

Examples
Example 1:
Consider the string S = 'cat'

1. Turn 1: Alex (minimize) tries removing each character and evaluates the resulting strings:

●​ Remove 'c' -> 'at'

●​ Remove 'a' -> 'ct'
●​ Remove 't' -> 'ca'
●​ Among these: 'at' is the smallest -> Alex removes 'c'.

2. Turn 2 - Charlie (maximize), tries removing each character:

●​ Remove 'a' -> 't'

●​ Remove 't' -> 'a'
●​ Among these: 't' is larger -> Charlie removes 'a'

The final character left in the string is 't'. Hence, the answer is 't'.

Sample Case 0:
Input: S = "abcde"
Output: c
Explanation:

Here, S="abcde"

●​ Alex would remove character 'e' (at index 4) making S="abcd"

●​
 ●​ Charlie would remove character 'a' (at index 0) making S="bcd"
●​ Alex would remove character 'd' (at index 2) making S="bc"
●​ Charlie would remove character 'b' (at index 0) making S="c"

Hence, 'c' is the final character left.

Sample Case 1:
Input: S = "hacker"
Output: e
Explanation:

Here, S="hacker"

●​ Alex would remove character 'h' (at i=0) making S="acker"

●​ Charlie would remove character 'a' (at i=0) making S="cker"
●​ Alex would remove character 'k' (at i=1) making S="cer"
●​ Charlie would remove character 'c' (at i=0) making S="er"
●​ Alex would remove character 'e' (at i=0) making S="r"

Hence, 'e' is the final character left.

Function Description
Complete the function finalCharacter in the editor below.

finalCharacter has the following parameter:

●​ S: A string composed of lowercase English letters.

char finalCharacter(string s) {
// Complete the 'finalCharacter' function below.
// The function is expected to return a CHARACTER.
// The function accepts STRING s as parameter.
}

Constraints
●​ 1 <= |S| <= 10^6
●​ String S consists only of English lowercase letters (a-z).

●​
 Sol:​
#include <bits/stdc++.h>

using namespace std;

// Function to get final remaining character

char finalCharacter(string s) {

deque<char> dq(s.begin(), s.end());

bool alexTurn = true;

while (dq.size() > 1) {

int n = dq.size();

// Compare possible removals

string removeFront = string(dq.begin() + 1, dq.end());

string removeBack = string(dq.begin(), dq.end() - 1);

if (alexTurn) {

// Alex wants lexicographically smallest

if (removeFront < removeBack)

dq.pop_front();

else

●​
 dq.pop_back();

} else {

// Charlie wants lexicographically largest

if (removeFront > removeBack)

dq.pop_front();

else

dq.pop_back();

alexTurn = !alexTurn;

return dq.front();

Find Minimum Sum

Problem Description
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 is minimum.

Complete the function findMinimumSum in the editor below.

●​
The function findMinimumSum has the following parameter(s):

●​ int power[]: the computational powers of n different servers

Returns:

●​ long: the minimum possible sum of integers required to make the array non-decreasing

long findMinimumSum(int power_count, int* power) {

Examples

Example 1:
There are n = 5 servers and their computational power = [3, 4, 1, 6, 2].

Explanation: 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.

Example 2:
Input:

n = 3

power = [3, 2, 1]

Output: 2

Explanation: Add 1 unit to subarray (1,2) and 1 unit to subarray (2,2). The final arrangement of servers is [3, 3, 3].

Example 3:
Input:

n = 4

power = [3, 5, 2, 3]

Output: 3

Explanation: Add 3 units to subarray (2,3). The final arrangement of servers is [3, 5, 5, 6].

●​
Constraints
●​ 1 <= n <= 10^5
●​ 1 <= power[i] <= 10^9

Sol:​

#include <algorithm>

long findMinimumSum(int power_count, int* power) {

if (power_count <= 1) {

return 0;

long long total_min_sum = 0;

long long prev_b = 0;

for (int i = 1; i < power_count; ++i) {

long long diff = (long long)power[i - 1] - power[i];

long long required_b = prev_b + diff;

long long current_b = std::max(0LL, required_b);

long long b_increase = current_b - prev_b;

●​
 if (b_increase > 0) {

total_min_sum += b_increase;

prev_b = current_b;

return (long)total_min_sum;

Number of Retailers Covering a Point

Problem Description
In a newly planned city, where a city is located at each integral coordinate in a 2-dimensional
plane, there are n Amazon retailers. The i-th retailer residing in the city at the coordinate

(x_i, y_i) can deliver to all the cities covered by the rectangle having the 4 corner points

(0, 0), (x_i, 0), (x_i, y_i), (0, y_i). We say that a point (a, b) is covered by

a rectangle if it lies inside the rectangle or on its boundaries. Note that no 2 retailers reside in
the same city.

Given q requests of the form (a, b), determine the number of retailers who can deliver to

the city at the coordinate (a, b).

Complete the function findNumRetailers in the editor below. The function is expected to

return an INTEGER_ARRAY.

●​
vector findNumRetailers(vector> retailers, vector> requests)
The function has the following parameters:

●​ int retailers[n][2]: the retailers' coordinates (x_i, y_i).

●​ int requests[q][2]: the coordinates of cities to deliver to (a, b).

Returns:

int array[q]: the i-th element is the answer to the i-th query.

Examples
Example 1:
Input: retailers = [[1, 2], [2, 3], [1, 5]], requests = [[1, 1],
[1, 4]]
Output: [3, 1]
Explanation: In this example, we have 3 retailers in the cities (1, 2), (2, 3), and (1, 5).

●​ For the first request, all 3 retailers can deliver to the city at the coordinate (1, 1).
●​ For the second request, only the third retailer can deliver to the city at the coordinate
(1, 4).

Hence, the answer for this example will be [3, 1].

Example 2:
Input: retailers = [[1, 4], [2, 4], [1, 5]], requests = [[2, 6],
[1, 4]]
Output: [0, 3]
Explanation:

●​ For the first request, none of the retailers can deliver to the city at the coordinates (2,
6).
●​ For the second request, all 3 retailers can deliver to the city at the coordinates (1, 4).

Constraints
●​ 1 <= n, q <= 7.5 * 10^4
●​ 1 <= retailers[i][0] <= 10^9

●​
 ●​ 1 <= retailers[i][1] <= 10^9
●​ 0 <= requests[i][0] <= 10^9
●​ 0 <= requests[i][1] <= 10^9
●​ No two retailers share the same coordinates.

Sol:​
#include <vector>
#include <algorithm>

struct Request {
int x, y, id;
};

class FenwickTree {
private:
std::vector<int> bit;
int size;

public:
FenwickTree(int sz) : size(sz), bit(sz + 1, 0) {}

void update(int idx, int val) {

for (; idx <= size; idx += idx & -idx) {
bit[idx] += val;
}
}

int query(int idx) {

int sum = 0;
for (; idx > 0; idx -= idx & -idx) {
sum += bit[idx];
}
return sum;
}
};

std::vector<int> findNumRetailers(const
std::vector<std::vector<int>>& retailers, const
std::vector<std::vector<int>>& requests) {
int n = retailers.size();
int q = requests.size();

if (q == 0) {
return {};
}

●​
 std::vector<int> y_coords;
y_coords.reserve(n + q);
for (const auto& r : retailers) {
y_coords.push_back(r[1]);
}
for (const auto& req : requests) {
y_coords.push_back(req[1]);
}

std::sort(y_coords.begin(), y_coords.end());
y_coords.erase(std::unique(y_coords.begin(), y_coords.end()),
y_coords.end());

auto get_compressed_y = [&](int y) {

return std::lower_bound(y_coords.begin(), y_coords.end(),
y) - y_coords.begin() + 1;
};

FenwickTree ft(y_coords.size());

std::vector<std::vector<int>> sorted_retailers = retailers;

std::sort(sorted_retailers.begin(), sorted_retailers.end(),
[](const std::vector<int>& a, const std::vector<int>& b) {
return a[0] > b[0];
});

std::vector<Request> reqs(q);
for (int i = 0; i < q; ++i) {
reqs[i] = {requests[i][0], requests[i][1], i};
}
std::sort(reqs.begin(), reqs.end(), [](const Request& a, const
Request& b) {
return a.x > b.x;
});

std::vector<int> ans(q);
int retailer_idx = 0;

for (const auto& req : reqs) {

while (retailer_idx < n &&
sorted_retailers[retailer_idx][0] >= req.x) {
int comp_y =
get_compressed_y(sorted_retailers[retailer_idx][1]);
ft.update(comp_y, 1);
retailer_idx++;
}

int comp_by = get_compressed_y(req.y);

●​
 int total_added = retailer_idx;
int count_less_than_b = ft.query(comp_by - 1);
ans[req.id] = total_added - count_less_than_b;
}

return ans;}

Minimize Cleaning Cost

Problem Description
Data Scientists at Amazon are working on cleaning a machine learning dataset. The dataset
is represented as a string dataset consisting of an even number of lowercase English letters.
The goal is to clean the dataset efficiently by performing specific operations.

Here's how the operations work:

●​ In each operation, two characters from the dataset are selected and removed.
●​ Each operation has an associated cost:
●​ matchCost: the cost of removing two identical characters.
●​ mismatchCost: the cost of removing two different characters.

The task is to determine the optimal strategy that minimizes the total cost to completely
clean up the dataset. In other words, find the minimum cost required to remove all
characters and make the dataset empty.

Complete the function minimizeCleaningCost in the editor below.

minimizeCleaningCost has the following parameters:

●​ string dataset: a string that denotes a machine learning dataset

●​ int matchCost: the cost of operation when the removed characters are equal
●​ int mismatchCost: the cost of operation when the removed characters are
unequal

Returns:

●​
 ●​ int: the minimum cost to clean up the dataset or make the string empty

Examples
Example 1:
Input: dataset = "ouio", matchCost = 2, mismatchCost = 4
Output: 6
Explanation:

Initial String: dataset = "ouio"

Operation 1:

●​ Action: Remove the first and last characters of the dataset, resulting in the string
dataset = 'ui'.
●​ Cost: mismatchCost = 2 (since both removed characters, 'o' and 'o', are the same).

Operation 2:

●​ Action: Delete the remaining characters of 'ui', making dataset an empty string.
●​ Cost: mismatchCost = 4 (since the removed characters, 'u' and 'i', are different).

Total Cost: matchCost + mismatchCost = 2 + 4 = 6.

Example 2:
Input: dataset = "aaabca", matchCost = 3, mismatchCost = 2
Output: 7
Explanation: In the first operation, the first and second characters are deleted from the
dataset, resulting in dataset = "abca". The cost of this operation is matchCost = 3

because both removed characters are equal to 'a'. In the next operation, the first and third
characters are deleted, making dataset = "ba". The cost of this operation is

mismatchCost = 2 because the removed characters are not equal. In the final operation,

the remaining two characters are deleted, making the dataset an empty string. The cost of
this operation is mismatchCost = 2 because the removed characters are not equal.

Hence, the total cost is 3 + 2 + 2 = 7.

●​
Example 3:
Input: dataset = "xxch", matchCost = 5, mismatchCost = 5
Output: 10
Explanation: In the first operation, the first two characters are deleted, resulting in dataset

= "ch". The cost of this operation is matchCost = 5, because both removed characters

are equal to 'x'. In the next operation, the remaining two characters are deleted, making
dataset an empty string. The cost of this operation is mismatchCost = 5, because the

removed characters are not equal. Hence, the total cost is 5 + 5 = 10.

Constraints
●​ 2 <= |dataset| <= 105
●​ |dataset| is even
●​ 1 <= matchCost, mismatchCost <= 104

Sol:​
#include <bits/stdc++.h>
using namespace std;

long long minimizeCleaningCost(const string &dataset, int matchCost, int mismatchCost) {

int n = dataset.size();
int totalPairs = n / 2;

vector<int> freq(26, 0);

for (char ch : dataset) freq[ch - 'a']++;

long long max_matchPairs = 0;

int maxf = 0;
for (int f : freq) {
max_matchPairs += f / 2;
maxf = max(maxf, f);
}

// maximum possible mismatch pairs

long long max_mismatchPairs = min<long long>(totalPairs, (long long)n - maxf);
long long min_matchPairs = totalPairs - max_mismatchPairs; // >= 0

long long chosenMatchPairs;

if (matchCost < mismatchCost) {
chosenMatchPairs = max_matchPairs;
} else if (matchCost > mismatchCost) {
chosenMatchPairs = min_matchPairs;
} else {

●​
 // costs equal -> any feasible number of match pairs yields same cost
chosenMatchPairs = max_matchPairs;
}

long long result = chosenMatchPairs * 1LL * matchCost

+ (totalPairs - chosenMatchPairs) * 1LL * mismatchCost;
return result;
}

Minimum Operations to Process

Packages
Problem Description
An Amazon distribution specialist needs to process n packages from different distribution

centers. The center of the ith package is represented by an array centers[i]. The

specialist is allowed to perform one operation at a time. Each operation is described below:

1.​ If the queue has two or more packages, the specialist can choose two packages x
and y from the queue if they are from different distribution centers (i.e., centers[x]
!= centers[y]) and process both of them.
2.​ If the queue has one or more packages, the specialist can choose one package x
from the queue and process it.

Note: After processing a package it gets removed from the queue, and the rest of the
packages which are currently not processed come together keeping the order the same as
before.

Given n packages and an array centers, find the minimum number of operations that the

specialist has to perform to process all of the packages.

Function Description
Complete the function findMinimumOperations in the editor below.

findMinimumOperations has the following parameter(s):

●​
 ●​ int centers[n]: the distribution center of each package.

Returns
●​ int: the minimum number of operations that the specialist has to perform to process
all of the packages.

#include <bits/stdc++.h>

/*
* Complete the 'findMinimumOperations' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER_ARRAY centers as parameter.
*/

int findMinimumOperations(vector<int> centers) {

int main() {

Examples
Example 1:
Input: n = 4, centers = [1,3,1,2]
Output: 2
Explanation: Given n=4 and centers=[1, 3, 1, 2].

The operations can be:

1.​ Choose packages from centers 1 and 3 (different centers). Remaining packages:
[1, 2]. (1 operation)
2.​ Choose packages from centers 1 and 2 (different centers). Remaining packages: [].
(1 operation)

The specialist needs to perform 2 operations to process all of the packages.

Example 2:
Input: n = 4, centers = [9,5,9,9]

●​
Output: 3
Explanation: Given n=4 and centers=[9, 5, 9, 9].

The operations can be:

1.​ Choose packages from centers 9 and 5 (different centers). Remaining packages:
[9, 9]. (1 operation)
2.​ Now, the remaining packages are from centers [9, 9]. Since both are from the
same center, we cannot choose two packages in one operation. We must process
them one by one. Choose one package from center 9. Remaining packages: [9]. (1
operation)
3.​ Choose the last package from center 9. Remaining packages: []. (1 operation)

The specialist needs to perform 3 operations to process all of the packages.

Constraints
●​ 1 <= n <= 105
●​ 1 <= centers[i] <= 109

Sol:​
#include <bits/stdc++.h>

using namespace std;

int findMinimumOperations(vector<int> centers) {

if (centers.empty()) {
return 0;
}

int n = centers.size();
unordered_map<int, int> freq_map;
int max_freq = 0;

for (int center : centers) {

freq_map[center]++;
if (freq_map[center] > max_freq) {
max_freq = freq_map[center];
}
}

●​
 if (max_freq > n - max_freq) {
return max_freq;
} else {
return (n + 1) / 2;
}
}

int main() {
return 0;
}

Maximum Data Flow

Problem Description
As an engineer in Amazon's Data Infrastructure Team, you are tasked with optimizing how
information flows through its network of processing nodes. You are given `n` processing
nodes, and the bandwidth capability of each node is given in an integer array `bandwidth`.

There are `streamCount` data channels that needs to be connected to two processing
nodes, one as the main connection and the other as the secondary. Each data channel must
utilize a unique pair of nodes for its connections.

The `dataFlow` for each data channel is defined as the sum of the bandwidth of its main and
secondary nodes.

Given an integer array `bandwidth` and an integer `streamCount`, find the maximum total
`dataFlow` that can be achieved by optimally selecting unique pair of connections for each
data channel.

Note: A pair of nodes (x,y) is said to be unique if no other channel has selected the same
pair. However, the pairs (y, x) and (x, y) are treated as different connections. It is also
possible to select the same node for main and secondary connections, which means that
(x,x) is a valid pair for the connection.

Complete the function `determineMaxDataFlow` in the editor below.

●​
long determineMaxDataFlow(vector<int> bandwidth, long streamCount)
The function has the following parameters:

●​ `int bandwidth[n]`: array of bandwidth capability provided by each processing node.

●​ `int streamCount`: the number of data channels that needs to be connected.

Returns: `long`: the maximum total dataFlow from the unique connections of node pairs.

Examples
Example 1:
Input: bandwidth = [6, 4, 7], streamCount = 4
Output: 52
Explanation: The data channels can select their connections among the following 9 possible
node pairs: [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]. (Assuming 1-based
indexing of bandwidth array). However each data channel must select a unique pair of
nodes. To achieve the maximum total dataFlow, the data channels can optimally choose the
pairs [3, 3], [3, 1], [1, 3], [1, 1] to obtain the maximum sum of dataFlow = (7 + 7) + (7 + 6) +
(6 + 7) + (6 + 6) = 52.

Example 2:
Input:
n = 5
bandwidth = [5, 4, 8, 4, 7]
streamCount = 6
Output: 86
Explanation: The six pairs of processing nodes with the highest sum of dataFlow are: [3, 3],
[3, 5], [5, 3], [5, 5], [3, 1], [1, 3]. (Assuming 1-based indexing) Thus total dataFlow will be
calculated as: 16 (for [3, 3]) + 15 (for [3, 5]) + 15 (for [5, 3]) + 14 (for [5, 5]) + 13 (for [3, 1]) +
13 (for [1, 3]) = 86. Therefore, the total dataFlow = 86. Hence return 86 as answer.

Example 3:
Input:
n = 4
bandwidth = [14, 120, 8, 14]
streamCount = 4
Output: 626
Explanation: The four pairs of processing nodes with the highest sum of dataFlow are: [2, 2],
[2, 1], [2, 4], [1, 2] (Assuming 1-based indexing). The total dataFlow is calculated as: 240 (for

●​
[2, 2]) + 134 (for [2, 1]) + 134 (for [2, 4]) + 118 (for [1, 2]) = 626. Thus, the total dataFlow =
626. Hence return 626 as answer.

Constraints
●​ `1 <= n <= 2 * 10^5`
●​ `1 <= bandwidth[i] <= 2 * 10^3`
●​ `1 <= streamCount <= min(10^3, n^2)`

Sol:​
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long determineMaxDataFlow(vector<int> bandwidth, long streamCount) {

int n = bandwidth.size();
sort(bandwidth.begin(), bandwidth.end(), greater<int>());

using T = tuple<int, int, int>; // {sum, i, j}

priority_queue<T> pq; // max-heap by sum

// To avoid revisiting same pair

set<pair<int, int>> vis;

// Start with largest pair (0,0)

pq.push({bandwidth[0] + bandwidth[0], 0, 0});
vis.insert({0, 0});

long long ans = 0;

while (streamCount-- && !pq.empty()) {
auto [sum, i, j] = pq.top();
pq.pop();
ans += sum;

// push next pairs

if (i + 1 < n && !vis.count({i + 1, j})) {
pq.push({bandwidth[i + 1] + bandwidth[j], i + 1, j});
vis.insert({i + 1, j});
}
if (j + 1 < n && !vis.count({i, j + 1})) {
pq.push({bandwidth[i] + bandwidth[j + 1], i, j + 1});
vis.insert({i, j + 1});
}
}

●​
 return ans;
}

int main() {
vector<int> bandwidth = {14, 120, 8, 14};
long streamCount = 4;
cout << determineMaxDataFlow(bandwidth, streamCount) << "\n"; // Output: 626
}

Total Packing Efficiency

Problem Description
In the Amazon distribution center, there is a collection of n products, each with a distinct

volume. The challenge is to evaluate the "packing efficiency" of the collection, aiming for
proper utilization of space.

More specifically, there is an array volumes, where volumes[i] represents the volume of

the ith product.

The "packing efficiency" of a subarray B = [volumes[l], volumes[l+1], ...,

volumes[r]] is defined by the number of indices i that satisfy these conditions:

●​ l <= i <= r (meaning i is an index within the subarray B, from its start l to its
end r)
●​ For every index j such that i < j <= r, volumes[i] > volumes[j]

The total packing efficiency of the entire collection is calculated by summing the packing
efficiency across all subarrays of a given size k.

Given an array volumes of size n and an integer k, compute the total packing efficiency of

the collection.

Examples

●​
Example 1:
Input:
n = 6
volumes = [3, 6, 2, 9, 4, 1]
k = 3
Output: 8
Explanation:

For volumes = [3, 6, 2, 9, 4, 1] and k = 3, we consider all subarrays of length

3:

For B = [3, 6, 2] (global indices 0 to 2):

●​ For i = 0 (value volumes[0]=3): 3 > volumes[1]=6 is false. Does not satisfy.

●​ For i = 1 (value volumes[1]=6): 6 > volumes[2]=2 is true. Satisfies.
●​ For i = 2 (value volumes[2]=2): No j such that 2 < j <= 2. Satisfies.

So, the efficiency of the subarray [3, 6, 2] is 2.

For B = [6, 2, 9] (global indices 1 to 3):

●​ For i = 1 (value volumes[1]=6): 6 > volumes[2]=2 is true, but 6 >

volumes[3]=9 is false. Does not satisfy.
●​ For i = 2 (value volumes[2]=2): 2 > volumes[3]=9 is false. Does not satisfy.
●​ For i = 3 (value volumes[3]=9): No j such that 3 < j <= 3. Satisfies.

So, the efficiency of the subarray [6, 2, 9] is 1.

For B = [2, 9, 4] (global indices 2 to 4):

●​ For i = 2 (value volumes[2]=2): 2 > volumes[3]=9 is false. Does not satisfy.

●​ For i = 3 (value volumes[3]=9): 9 > volumes[4]=4 is true. Satisfies.
●​ For i = 4 (value volumes[4]=4): No j such that 4 < j <= 4. Satisfies.

So, the efficiency of the subarray [2, 9, 4] is 2.

For B = [9, 4, 1] (global indices 3 to 5):

●​
 ●​ For i = 3 (value volumes[3]=9): 9 > volumes[4]=4 is true, and 9 >
volumes[5]=1 is true. Satisfies.
●​ For i = 4 (value volumes[4]=4): 4 > volumes[5]=1 is true. Satisfies.
●​ For i = 5 (value volumes[5]=1): No j such that 5 < j <= 5. Satisfies.

So, the efficiency of the subarray [9, 4, 1] is 3.

The total packing efficiency of the collection is 2 + 1 + 2 + 3 = 8.

Sol:​
#include <bits/stdc++.h>
using namespace std;

long long totalPackingEfficiency(vector<int>& volumes, int k) {

int n = volumes.size();
vector<int> ngr(n, n);
stack<int> st;

// Find next greater element index

for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && volumes[st.top()] < volumes[i])
st.pop();
if (!st.empty()) ngr[i] = st.top();
st.push(i);
}

long long ans = 0;

for (int i = 0; i < n; ++i) {
int rightLimit = ngr[i] - 1; // last index before a greater element
int leftLimit = i - k + 1; // minimum left possible
int maxLeft = min(i, rightLimit - k + 1);
int minLeft = max(0, leftLimit);
if (maxLeft >= minLeft)
ans += (maxLeft - minLeft + 1);
}
return ans;
}

int main() {
vector<int> volumes = {3, 6, 2, 9, 4, 1};
int k = 3;
cout << totalPackingEfficiency(volumes, k) << endl; // Output: 8
}

●​
Minimum Operations to Dispatch Items
Problem Description
The logistics coordinator at an Amazon fulfillment center needs to dispatch `n` items from
different warehouses, the warehouse of the `i`th item is represented by an array
`warehouses[i]`. The coordinator is allowed to perform one operation at a time. Each
operation is described below:

1.​ If the inventory has two or more items, the coordinator can select two items `x` and
`y` from the inventory if they are stored in different warehouses. i.e. `warehouses[x]
!= warehouses[y]` and dispatch both of them.
2.​ If the inventory has one or more items, the coordinator can select one item `x` from
the inventory and dispatch it.

Note: After dispatching an item it gets removed from the inventory, and the rest of the items
which are currently not dispatched come together keeping the order the same as before.

Given `n` items and an array `warehouses`, find the minimum number of operations that the
coordinator has to perform to dispatch all of the items.

Complete the function `calculateMinShipments` in the editor below.

The function is expected to return an INTEGER.

The function accepts `List warehouses` as parameter.

public static int calculateMinShipments(List<Integer> warehouses)

{
// Write your code here
}

Examples
Example 1:
●​
Input: warehouses = [2, 9, 7, 8, 8]
Output: 3
Explanation: The problem statement illustrates the operations to dispatch all items in 3
steps.

Example 2:
Input: warehouses = [1, 3, 1, 2]
Output: 2
Explanation: The problem statement illustrates the operations to dispatch all items in 2
steps.

Example 3:
Input: warehouses = [9, 5, 9, 9]
Output: 3
Explanation: The problem statement illustrates the operations to dispatch all items in 3
steps.

Constraints
●​ `1 <= n <= 10^5`
●​ `1 <= warehouses[i] <= 10^9`

Sol:​
#include <bits/stdc++.h>
using namespace std;

int calculateMinShipments(vector<int>& warehouses) {

unordered_map<int, int> freq;
int n = warehouses.size();
int maxFreq = 0;

for (int w : warehouses) {

maxFreq = max(maxFreq, ++freq[w]);
}

// Minimum operations = max(max frequency, ceil(n / 2))

return max(maxFreq, (n + 1) / 2);
}

int main() {
vector<int> w1 = {2, 9, 7, 8, 8};
vector<int> w2 = {1, 3, 1, 2};

●​
 vector<int> w3 = {9, 5, 9, 9};

cout << calculateMinShipments(w1) << "\n"; // 3

cout << calculateMinShipments(w2) << "\n"; // 2
cout << calculateMinShipments(w3) << "\n"; // 3
}

Code Question 1
Problem Description
Your team at Amazon is building a quiz-style application to help students prepare for
certification exams. Each quiz module tests one or more subjects and limits the number of
answers students can provide. You have been asked to examine the impact of this limit on
the ability of students to pass certain subjects within quiz modules. To do this, please review
and solve for the following: imagine a student has already answered answered[i]

questions in each of the n subjects, and still has time to answer a total of q more questions

overall. For each ith subject, the number of questions answered has to be at least

needed[i] in order to pass. Determine the maximum number of subjects the student can

pass if the q additional answered questions are optimally distributed among the subjects.

For example, consider that there are n = 2 subjects and needed = [4, 5] answered

questions, respectively, to pass. Imagine the student has answered answered = [2, 4]

questions in the two subjects so far, and can answer another q = 1 question across all

subjects combined. In that case, the best outcome is to answer an additional question in the
second subject in order to pass it, as 2 more answers are required to pass the first subject.
The maximum number of subjects that can be passed is 1.

Complete the function findMaximumNum in the editor below. The function must return an

integer that represents the maximum number of subjects that can be passed.

The function findMaximumNum has the following parameters:

●​ answered[0]...answered[n-1]: an array of integers

●​ needed[0]...needed[n-1]: an array of integers

●​
 ●​ q: an integer

int findMaximumNum(vector answered, vector needed, int q) {

// Function implementation
}

Examples
Example 1:
Input:
n = 3
answered = [24, 27, 0]
needed = [51, 52, 100]
q = 100
Output: 2
Explanation: The questions still needed for each subject are [max(0, 51-24), max(0,

52-27), max(0, 100-0)] = [27, 25, 100]. To pass the first two subjects, 27 +

25 = 52 additional questions are required. Since q = 100, we have enough questions to

pass these two subjects. To pass the third subject alone would require 100 questions.

Optimally, we can pass 2 subjects.

Example 2:
Input:
n = 3
answered = [24, 27, 0]
needed = [51, 52, 97]
q = 200
Output: 3
Explanation: The questions still needed for each subject are [max(0, 51-24), max(0,

52-27), max(0, 97-0)] = [27, 25, 97]. To pass all three subjects, a total of 27 +

25 + 97 = 149 additional questions are required. Since q = 200 and 149 <= 200,

there are enough questions to pass all three subjects. The remaining 200 - 149 = 51

questions can be distributed at random.

Constraints
●​ 1 <= n <= 105
●​ 0 <= answered[i] <= 109
●​ 0 <= needed[i] <= 109

●​
 ●​ 0 <= q <= 109
●​ 0 <= answered[i] <= needed[i]

Sol:​
#include <bits/stdc++.h>
using namespace std;

int findMaximumNum(vector<int> answered, vector<int> needed, int q) {

int n = answered.size();
vector<long long> remaining(n);

for (int i = 0; i < n; i++)

remaining[i] = max(0LL, (long long)needed[i] - answered[i]);

sort(remaining.begin(), remaining.end());

int passed = 0;
for (int i = 0; i < n; i++) {
if (q >= remaining[i]) {
q -= remaining[i];
passed++;
} else break;
}

return passed;
}

int main() {
vector<int> answered1 = {24, 27, 0};
vector<int> needed1 = {51, 52, 100};
int q1 = 100;
cout << findMaximumNum(answered1, needed1, q1) << "\n"; // Output: 2

vector<int> answered2 = {24, 27, 0};

vector<int> needed2 = {51, 52, 97};
int q2 = 200;
cout << findMaximumNum(answered2, needed2, q2) << "\n"; // Output: 3
}

Distinct Stock Profit Pairs

Problem Description

●​
A financial analyst for Amazon Web Services (AWS) is responsible for a portfolio of
profitable stocks represented by an array. Each item in the array represents the yearly profit
of a corresponding stock. The Amazonian gathers all distinct pairs of stocks that yielded the
target profit. Distinct pairs are pairs that differ in at least one element. Given the array of
profits, find the number of distinct pairs of stocks where the sum of each pair's profits is
exactly equal to the target profit.

Complete the function getDistinctPairs in the editor below.

getDistinctPairs has the following parameter(s):

●​ int stocksProfit[n]: an array of integers representing the stocks profits

●​ target: an integer representing the yearly target profit

Returns:

●​ int: the total number of pairs determined

The function signature is:

int getDistinctPairs(vector<int> stocksProfit, long target)

Examples
Example 1:
Input: stocksProfit = [5, 7, 9, 12, 11, 6, 6, 3], target = 12
Output: 3
Explanation: There are 4 pairs of stocks that have the sum of their profits equal to the target
12. Note that because there are two instances of 6 in stocksProfit there are two pairs

matching (6, 6). stocksProfit indices 2 and 7, and indices 3 and 8, but only one can be

included. There are 3 distinct pairs of stocks: (6, 6), (3, 9), and the return value is 3.

Example 2:
Input: stocksProfit = [1, 3, 46, 1, 3, 9], target = 47
Output: 1
Explanation: There are 4 pairs where stocksProfit[i] + stocksProfit[j] = 47:

●​
 1.​ (stocksProfit[0] = 1, stocksProfit[2] = 46)
2.​ (stocksProfit[2] = 46, stocksProfit[0] = 1)
3.​ (stocksProfit[3] = 1, stocksProfit[2] = 46)
4.​ (stocksProfit[2] = 46, stocksProfit[3] = 1)

Since all four pairs contain the same values, there is only 1 distinct pair of stocks: (1, 46).

Example 3:
Input: stocksProfit = [6, 3, 9, 3, 6], target = 12
Output: 2
Explanation: There are 5 pairs where stocksProfit[i] + stocksProfit[j] = 12:

1.​ (stocksProfit[0] = 6, stocksProfit[1] = 6)

2.​ (stocksProfit[0] = 6, stocksProfit[4] = 6)
3.​ (stocksProfit[1] = 3, stocksProfit[2] = 9)
4.​ (stocksProfit[2] = 9, stocksProfit[1] = 3)
5.​ (stocksProfit[3] = 3, stocksProfit[2] = 9)
6.​ (stocksProfit[4] = 6, stocksProfit[0] = 6)

The first 2 pairs are the same, as are the last 4. There are only 2 distinct pairs of stocks: (3,
9) and (6, 6).

Constraints
●​ 1 <= n <= 5 * 10^5
●​ 0 <= stocksProfit[i] <= 10^9
●​ 0 <= target <= 5 * 10^9

Sol:​
#include <bits/stdc++.h>
using namespace std;

int getDistinctPairs(vector<int>& stocksProfit, long target) {

unordered_map<long long, int> freq;
for (int p : stocksProfit) freq[p]++;

int count = 0;

●​
 for (auto& [x, f] : freq) {
long long y = target - x;
if (freq.find(y) != freq.end()) {
if (x == y) {
if (f >= 2) count++; // pair (x, x)
} else if (x < y) {
count++; // pair (x, y)
}
}
}
return count;
}

int main() {
vector<int> profits1 = {5, 7, 9, 12, 11, 6, 6, 3};
cout << getDistinctPairs(profits1, 12) << "\n"; // Output: 3

vector<int> profits2 = {1, 3, 46, 1, 3, 9};

cout << getDistinctPairs(profits2, 47) << "\n"; // Output: 1

vector<int> profits3 = {6, 3, 9, 3, 6};

cout << getDistinctPairs(profits3, 12) << "\n"; // Output: 2}

Medians
Problem Description
A new Amazon intern encountered a challenging task.

Currently, the intern has n integers, where the value of the ith element is represented by the

array element values[i].

The intern is curious to play with arrays and subsequences and thus asks you to join him.

Given n integer, array values, and an integer k, the intern needs to find the maximum and

minimum median overall subsequences of length k.

Function Description
Complete the function medians in the editor below.

medians has the following parameter(s):

●​
 ●​ int values[n]: the value of integers.
●​ int k: the given integer.

Returns
int[]: the maximum and minimum overall subsequences of length k in the form

[maximum median, minimum median].

vector medians(vector values, int k) {

Examples
Example 1:
Input: n = 3, values = [1, 2, 3], k = 2
Output: [2, 1]
Explanation:

Subsequences of length k median

[1, 2] 1

[1, 3] 1

[2, 3] 2

Here, the maximum median present is 2 and the minimum median in the subsequence
present is 1.

Example 2:
Input: n = 2, values = [56, 21], k = 1
Output: [56, 21]
Explanation:

●​
 Subsequences of length k median

[56] 56

[21] 21

The maximum median present is 56 and the minimum median in the subsequence present is
21.

Example 3:
Input: n = 5, values = [16, 21, 9, 2, 78], k = 5
Output: [16, 16]
Explanation:

Subsequences of length k median

[16, 21, 9, 2, 78] 16

There is only one subsequence of length 5, hence the maximum median and minimum
median are 16.

Constraints
●​ 1 ≤ n ≤ 106
●​ 0 ≤ values[i] ≤ 109
●​ 1 ≤ k ≤ n

Sol:
#include <bits/stdc++.h>
using namespace std;

vector<int> medians(vector<int>& values, int k) {

int n = values.size();
sort(values.begin(), values.end());

int medianIndex = (k - 1) / 2;

●​
 int minMedian = values[medianIndex];
int maxMedian = values[n - k + medianIndex];

return {maxMedian, minMedian};

}

int main() {
vector<int> v1 = {1, 2, 3};
auto res1 = medians(v1, 2);
cout << res1[0] << " " << res1[1] << "\n"; // 2 1

vector<int> v2 = {56, 21};

auto res2 = medians(v2, 1);
cout << res2[0] << " " << res2[1] << "\n"; // 56 21

vector<int> v3 = {16, 21, 9, 2, 78};

auto res3 = medians(v3, 5);
cout << res3[0] << " " << res3[1] << "\n"; // 16 16
}

Code Question 2
Problem Description
Software developed these days is subject to frequent cyber attacks.

To prevent the attacks from succeeding, the security team at Amazon ensures the security of
its systems by running tests against n files, where the ith file has size fileSize[i] and

there are n viruses.

The ith virus attacks the ith file and is only effective against a file with size affinity[i].

To minimize the damage caused, the team performs certain operations.

In one operation, the team can choose 2 files, i and j, and swap their sizes, i.e.,

fileSize[i] and fileSize[j].

●​
Given the sizes of files and the virus' affinities, find the minimum number of operations
performed such that fileSize[i] != affinity[i] for each file from 0 to n-1. If it is

not possible to do so after any number of operations, return -1.

Complete the function calculateMinimumSwaps in the editor below.

calculateMinimumSwaps has the following parameters:

●​ int fileSize[n]: the file sizes

●​ int affinity[n]: the affinities

Returns:

●​ int: the minimum number of operations, or -1 if it is impossible

Examples
Example 1:
Input: n = 5, fileSize = [2, 2, 1, 1, 2], affinity = [2, 1, 1, 1,
2]
Output: 2
Explanation: Initially, we have fileSize = [2, 2, 1, 1, 2] and affinity = [2,

1, 1, 1, 2].

●​ fileSize[0] == affinity[0] (both 2)

●​ fileSize[2] == affinity[2] (both 1)
●​ fileSize[4] == affinity[4] (both 2)

One possible solution to achieve fileSize[i] != affinity[i] for all i:

●​ Operation 1: Swap fileSize[0] with fileSize[2].​

fileSize becomes [1, 2, 2, 1, 2].​
Now, fileSize[2] == affinity[2] (both 2) and fileSize[4] ==
affinity[4] (both 2) are still matching.

●​
 ●​ Operation 2: Swap fileSize[3] with fileSize[4].​
fileSize becomes [1, 2, 2, 2, 1].​
In this modified file size array, none of the file sizes match the corresponding affinity.

The minimum number of operations required is 2.

Example 2:
Input: n = 5, fileSize = [1, 2, 3, 2, 3], affinity = [1, 2, 3, 2,
3]
Output: 3
Explanation: Given, n = 5, fileSize = [1, 2, 3, 2, 3], affinity = [1, 2,

3, 2, 3]. Initially, fileSize[i] is equal to affinity[i] for all i = 0, 1, 2, 3,

4.

One solution to make all fileSize[i] != affinity[i] involves 3 swaps:

●​ Swap fileSize[0] with fileSize[2]. fileSize becomes [3, 2, 1, 2,

3].
●​ Swap fileSize[0] with fileSize[1]. fileSize becomes [2, 3, 1, 2,
3].
●​ Swap fileSize[3] with fileSize[4]. fileSize becomes [2, 3, 1, 3,
2].

Example 3:
Input: n = 5, fileSize = [2, 2, 2, 1, 1], affinity = [1, 1, 1, 1,
2]
Output: -1
Explanation: Given, n = 5, fileSize = [2, 2, 2, 1, 1], affinity = [1, 1,

1, 1, 2]. It is impossible to swap the elements of fileSize in such a way that

fileSize[i] != affinity[i] for all files.

Constraints
●​ 1 <= n <= 105
●​ 1 <= fileSize[i], affinity[i] <= 109

Sol:

●​
#include <bits/stdc++.h>
using namespace std;

int calculateMinimumSwaps(vector<int>& fileSize, vector<int>& affinity) {

int n = fileSize.size();
vector<int> conflictIndices;
unordered_map<int,int> freq;

for(int i = 0; i < n; i++){

if(fileSize[i] == affinity[i]){
conflictIndices.push_back(i);
freq[fileSize[i]]++;
}
}

int same = conflictIndices.size();

if(same == 0) return 0; // already good

int maxFreq = 0;
for(auto& [val, f] : freq)
maxFreq = max(maxFreq, f);

if(maxFreq > (n + 1) / 2) return -1; // impossible

return (same + 1) / 2; // minimum swaps

}

int main() {
vector<int> file1 = {2,2,1,1,2};
vector<int> aff1 = {2,1,1,1,2};
cout << calculateMinimumSwaps(file1, aff1) << "\n"; // 2

vector<int> file2 = {1,2,3,2,3};

vector<int> aff2 = {1,2,3,2,3};
cout << calculateMinimumSwaps(file2, aff2) << "\n"; // 3

vector<int> file3 = {2,2,2,1,1};

vector<int> aff3 = {1,1,1,1,2};
cout << calculateMinimumSwaps(file3, aff3) << "\n"; // -1
}

●​