原题汇总，会选其中的3道题。
A summary of the original questions, and I will choose 3 of them.
1.Minimum Swaps
You are given an unordered array consisting of consecutive integers [1, 2, 3, ..., n] without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order.
For example, given the array [7, 1, 3, 2, 4, 5, 6] we perform the following steps:
- Swap positions 7 and 2 (resulting in [2, 1, 3, 7, 4, 5, 6])
- Swap positions 2 and 1 (resulting in [1, 2, 3, 7, 4, 5, 6])
- Swap positions 7 and 4 (resulting in [1, 2, 3, 4, 7, 5, 6])
- Swap positions 7 and 5 (resulting in [1, 2, 3, 4, 5, 7, 6])
- Swap positions 7 and 6 (resulting in [1, 2, 3, 4, 5, 6, 7])
It took 5 swaps to sort the array.
Function Description
Complete the function minimumSwaps in the editor below. It must return an integer representing the minimum number of swaps to sort the array.
minimumSwaps has the following parameter(s):
- arr: an unordered array of integers
Input Format
The first line contains an integer, n, the size of arr. The second line contains n space-separated integers arr[i].
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ arr[i] ≤ n
Output Format
Return the minimum number of swaps to sort the given array.
2. Autoscale Policy
A scaling computing system checks its average utilization every second while it monitors. It implements an autoscale policy to increase or reduce instances depending on the current load as described below. Once an action of increasing or reducing the number of instances is performed, the system will stop monitoring for 10 seconds. During that time, the number of instances does not change.
- If the average utilization <25%, then an action is instantiated to reduce the number of instances by half if the number of instances is greater than 1. Take the ceiling of the number if it is not an integer. If the number of instances is 1, take no action.
- If the average utilization is between 25% and 60%, no action is taken.
- If the average utilization >60%, then an action is instantiated to double the number of instances if the doubled value does not exceed 2 x 10^8. If the number of instances exceeds this limit upon doubling, take no action.
Given an array of integers that represent the average utilization at each second, determine the number of instances at the end of the time frame.
Example 2
Instances = 1
averageUtil = [25, 23, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 76, 80]
At second 1, the average utilization averageUtil[0] = 25% takes no action. Since the average utilization will stop checking for 10 seconds, take the following number of seconds as the next averageUtil[i] = averageUtil[10]. At second 2, averageUtil[10] = 76% so the number of instances is doubled from 1 to 2. At second 3, averageUtil[11] = 80% so the number of instances is doubled from 2 to 4. There are no more readings to consider and 4 is the final answer.
Function Description
Complete the function finalInstances in the editor below.
finalInstances has the following parameters:
- int instances: the original number of instances running
- int averageUtil[n]: the average utilization at each second of the time frame
Returns:
- int: the final number of instances running
Constraints
- 1 ≤ instances ≤ 10^5
- 1 ≤ n ≤ 10^5
- 1 ≤ averageUtil[i] ≤ 100
Input Format For Custom Testing
The first line contains an integer, the starting number of instances. The second line contains an integer, n, the size of averageUtil. The next n lines contain an integer averageUtil[i] each.
3. Document Chunking
A financial services company is uploading documents to a compliance system for analysis. They use a chunking mechanism as below.
- Each document is divided into equal size packets.
- Documents are then divided and uploaded in "chunks" of packets. A chunk is defined as a contiguous set of packets, where n is any integer ≥ 0.
- After the document is divided into chunks, they systematically upload chunks until all the contents of a document are uploaded.
There is one document that is partially uploaded, described in uploadedChunks. Determine the minimum number of chunks that are yet to be uploaded.
Example
totalPackets = 5
numberOfChunks = 2
uploadedChunks = [(1,2), (4,5)]
The document has 5 packets and 1 chunk of 2*1 = 2 packets (1,2) is already uploaded.
The remaining 3 packets are uploaded in 2 chunks. The length of chunk 2 is 1*2 packets (3,4) and the length of chunk 3 is 1*1 packet (5).
Function Description
Complete the minimumChunksRequired function in the editor below.
minimumChunksRequired has the following parameters:
- long int totalPackets: the number of packets in the document
- long int uploadedChunks[n][2]: each uploadedChunks[i] describes the start and end packet numbers of the uploaded chunks.
Returns
- int: an integer that denotes the minimum number of chunks that need to be uploaded.
Constraints
- 1 ≤ totalPackets ≤ 10^9
- 0 ≤ uploadedChunks ≤ 10^5
- The uploaded chunks do not overlap
- 1 ≤ starting packet ≤ ending packet's totalPackets
The image also shows sample input and output for custom testing, as well as a portion of Python code that seems to be the solution to the problem described.
4 Maximum Distinct
Consider two arrays �a and �b where each consists of �n integers. In one operation:
This operation can be performed at most �k times.
Find the maximum number of distinct elements that can be achieved in array �a after at most �k operations.
5.Special Sequence
The following sequence is formed using words and numbers:
- The first number is 11
- In the first number, there was one 1 so the second number is 1111
- In the second number, there were two 1s, so the third number is 2121
- In the previous number, there was one 2 and there was one 1, so the fourth number is 12111211
- The next number is 111221111221, one 1, one 2, two 1's.
This sequence can continue infinitely. Given an integer, q[i], determine the sum of the digits of the value in the sequence at that position. For example, position 4 contains the value 12111211. The sum of those digits is 1+2+1+1=51+2+1+1=5.
6.Bucket Fill
Digital graphics tools often make available a "bucket fill" tool that will only paint adjacent cells. In one fill, a modified bucket tool recolors adjacent cells (connected horizontally or vertically but not diagonally) that have the same color. Given a picture represented as a 2-dimensional array of letters representing colors, find the minimum number of fills to completely repaint the picture.
Example: picture = ["aabba", "aabba", "aaacb"]
Each string represents a row of the picture and each letter represents a cell's color. The diagram below shows the 5 fills needed to repaint the picture. It takes two fills each for a and b, and one for c. The array picture is shown below.
Initial Canvas:
Function Description: Complete the function strokesRequired in the editor below.
The rest of the image includes a sample input for custom testing where the input is a 3x5 picture and the sample output is '5', followed by an explanation that aligns with the example above, mentioning that letter 'a' takes 2 fills, 'b' takes 2 fills, and 'c' takes 1 fill for a total of 5 fills.
For a full understanding of the problem, it is necessary to read the complete text, including the function signature and any additional details that may be included in the prompt outside of the image frame.
contact me to slove OA （Paid）
