在这篇文章中，我将分享在Amazon的在线评测（Online Assessment, OA）中遇到的两道编程题。这两道题目分别涉及数据包传输质量的优化和股票收益的分析。下面是对这两道题目的详细描述和解题思路。

In this blog post, I will share two coding questions I encountered during Amazon's Online Assessment (OA). These questions involve optimizing data packet transfer quality and analyzing stock profit and loss. Below are the detailed descriptions and solution approaches for these questions.

题目一：数据包传输质量优化 Question 1: Data Packet Transfer Quality Optimization

英文原文 Original Prompt:：

Amazon's AWS provides fast and efficient server solutions. The developers want to stress-test the quality of the servers' channels. They must ensure the following:

• Each of the packets must be sent via a single channel.
• Each of the channels must transfer at least one packet.

The quality of the transfer for a channel is defined by the median of the sizes of all the data packets sent through that channel.

Note: The median of an array is the middle element if the array is sorted in non-decreasing order. If the number of elements in the array is even, the median is the average of the two middle elements.

Find the maximum possible sum of the qualities of all channels. If the answer is a floating-point value, round it to the next higher integer.

Example:

packets = [1, 2, 3, 4, 5]
channels = 2

At least one packet has to go through each of the 2 channels. One maximal solution is to transfer packets [1, 2, 3, 4] through channel 1 and packet [5] through channel 2.

The quality of transfer for channel 1 is (2 + 3) / 2 = 2.5 and that of channel 2 is 5. Their sum is 2.5 + 5 = 7.5 which rounds up to 8.

Function Description

Complete the function findMaximumQuality in the editor below.

findMaximumQuality has the following parameter(s):

• int packets[n]: the packet sizes
• int channels: the number of channels

Returns

• long int: the maximum sum possible

Constraints

• 1 ≤ len(packets) ≤ 5 * 10^5
• 1 ≤ packets[i] ≤ 10^9
• 1 ≤ channels ≤ len(packets)

题目描述

Amazon的AWS提供快速高效的服务器解决方案。开发人员希望对服务器的通道进行压力测试，确保以下几点：

• 每个数据包必须通过单个通道传输。
• 每个通道必须传输至少一个数据包。

通道传输的质量由通过该通道传输的所有数据包大小的中位数定义。

注意：数组的中位数是数组按非递减顺序排序后的中间元素。如果数组中的元素个数为偶数，中位数是中间两个元素的平均值。

找到所有通道质量的最大可能总和。如果答案是浮点数，则将其四舍五入到下一个整数。

示例

数据包 = [1, 2, 3, 4, 5]
通道数 = 2

至少一个数据包必须通过每个通道。一个最大化的解决方案是将数据包[1, 2, 3, 4]通过通道1，数据包[5]通过通道2。

通道1的传输质量是(2 + 3)/2 = 2.5，通道2的传输质量是5。它们的总和是2.5 + 5 = 7.5，四舍五入为8。

题目二：股票收益分析 Question 2: Stock Profit and Loss Analysis

英文原文：

You are analyzing the market trends of Amazon stocks. An AWS financial service model returned an array of integers, PnL (Profit and Loss), for your portfolio representing that in the ith month, you will either gain or lose PnL[i] amount. All reported PnL values are positive, representing gains.

As part of the analysis, you will perform the following operation on the PnL array any number of times:

• Choose any month i (0 ≤ i < n) and multiply PnL[i] by -1

Find the maximum number of months you can afford to face a loss, i.e. have a negative PnL, such that the cumulative PnL for each of the n months remains strictly positive, i.e. remains greater than 0.

Note: The cumulative PnL for the ith month is defined as the sum of PnL from the starting month up to the ith month. For example, if the PnL for 4 months is [3, 2, -5, 6], its cumulative PnL is [3, 5, 0, 6].

Example:

Consider, n = 4, and PnL = [5, 3, 1, 2]

Some of the possible arrays after performing the given operation some number of times:

Modified PnL	Cumulative PnL	Number of Negatives	Is Valid	Comments
[5, -3, -1, 2]	[5, 2, 1, 3]	2	Yes	The operation was performed on the second and third months (in bold). All the cumulative PnL are positive
[5, -3, -1, -2]	[5, 2, 1, -1]	3	No	The last cumulative PnL is negative, hence this is not valid
[5, 3, 1, -2]	[5, 8, 9, 7]	1	Yes	All the cumulative PnL are positive
[-5, 3, 1, 2]	[-5, -2, -1, 1]	1	No	The cumulative PnL for the first three months are negative

There are many more ways to perform the operations but the maximum number of negative PnLs there can be, maintaining a positive cumulative PnL is 2. Report 2 as the answer.

Function Description

Complete the function getMaxNegativePnL in the editor below.

getMaxNegativePnL has the following parameter(s):

• int PnL[n]: an array of integers

Returns

• int: the maximum number of months

Constraints

• 1 ≤ n ≤ 10^5
• 1 ≤ PnL[i] ≤ 10^9

题目描述

你正在分析亚马逊股票的市场趋势。AWS金融服务模型返回了一个整数数组PnL（利润和亏损），表示在第i个月，你的投资组合将获得或损失PnL[i]金额。所有报告的PnL值都是正数，表示收益。

作为分析的一部分，你可以对PnL数组执行以下操作任意次：

• 选择任意一个月i（0 ≤ i < n），将PnL[i]乘以-1

找到你可以承受亏损的最大月数，即使PnL为负数，使得每个月的累计PnL仍然严格为正，即大于0。

示例

n = 4，PnL = [5, 3, 1, 2]

一些可能的数组在执行给定操作若干次后的情况：
修改后的PnL        累计PnL           负数的数量         是否有效      备注
[5, -3, -1, 2]      [5, 2, 1, 3]      2                 是           操作在第二个月和第三个月执行。所有的累计PnL都是正数
[5, -3, -1, -2]     [5, 2, 1, -1]     3                 否           最后一个累计PnL是负数，因此无效
[5, 3, 1, -2]       [5, 8, 9, 7]      1                 是           所有的累计PnL都是正数
[-5, 3, 1, 2]       [-5, -2, -1, 1]   1                 否           前三个月的累计PnL都是负数
执行这些操作的多种方式中，保持累计PnL为正数的情况下，可以有最多2个负数PnL。报告2作为答案。

解题思路

题目一：数据包传输质量优化

1. 初始化：
   • 将数据包按大小排序。
2. 分配数据包：
   • 将最大的k-1个数据包单独分配给k-1个通道，每个通道一个。
   • 剩余的数据包分配给最后一个通道。
3. 计算中位数：
   • 对于每个通道，计算其中位数。
4. 求总和：
   • 将所有通道的中位数相加，得到总和，并四舍五入到下一个整数。

Solution Approach

1. Initialization:
   • Sort the packets by size.
2. Distribute Packets:
   • Assign the largest k-1 packets individually to k-1 channels.
   • Assign the remaining packets to the last channel.
3. Calculate Median:
   • Compute the median for each channel.
4. Sum Up:
   • Sum the medians of all channels, rounding up to the next integer if necessary.

题目二：股票收益分析

1. 初始化：
   • 计算初始的累计PnL。
2. 操作选择：
   • 遍历PnL数组，选择将正数转换为负数的操作，优先选择较小的正数，以最大化负数的数量。
3. 验证累计PnL：
   • 每次操作后，重新计算累计PnL，确保所有月份的累计PnL保持正数。
4. 记录结果：
   • 记录可以承受负数的最大月份数。
     

Solution Approach

1. Initialization:
   • Calculate the initial cumulative PnL.
2. Choose Operations:
   • Traverse the PnL array, selecting operations that convert positive values to negative, prioritizing smaller positive values to maximize the number of negatives.
3. Validate Cumulative PnL:
   • After each operation, recalculate the cumulative PnL to ensure it remains positive for all months.
4. Record Results:
   • Record the maximum number of months with negative PnL while maintaining a positive cumulative PnL.

结论

通过这两道题目，我们学会了如何优化数据传输质量和分析股票收益。这些技能在实际开发中非常有用，不仅能提升我们的算法能力，还能帮助我们更好地进行系统设计和性能优化。

希望这个分享对大家有所帮助，如果有任何问题或建议，欢迎在评论区留言！

我们提供面试辅助，OA代写，代面试服务，助您进入梦想大厂，欢迎随时咨询我。

By solving these questions, we learn how to optimize data transfer quality and analyze stock profit and loss. These skills are useful in real-world development, enhancing our algorithmic abilities and helping us design and optimize systems more effectively.

If you need help with your online assessments or interviews, we offer professional OA and interview assistance services to help you land your dream job at top companies. Feel free to reach out for more information!