微软的笔试题限时110分钟，需要写2道算法题，输入输出需要自行控制，使用codility平台。让我们一起来看看真题吧 。
The Microsoft online assessment is limited to 110 minutes, requiring the completion of two algorithm questions. Input and output handling must be managed manually, and the exam is conducted on the Codility platform. Let’s take a look at the actual exam questions.
A domino is a rectangular tile divided into two square parts. There are between 1 and 6 dots on each of the parts.
There is an array A of length 2*N, representing N dominoes. Dominoes are arranged in a line in the order in which they appear in array A. The number of dots on the left and the right parts of the K-th domino are A[2*K] and A[2*K+1], respectively. For example, an array A = [2, 4, 1, 3, 4, 6, 2, 4, 1, 6] represents a sequence of five domino tiles: (2, 4), (1, 3), (4, 6), (2, 4), and (1, 6).
In a correct domino sequence, each pair of neighboring tiles should have the same number of dots on their adjacent parts. For example, tiles (2, 4) and (4, 6) form a correct domino sequence and tiles (2, 4) and (1, 3) do not.
What is the minimum number of domino tiles that must be removed from the sequence so that the remaining tiles form a correct domino sequence? It is not allowed to reorder or rotate the dominoes.
Write a function:
def solution(A):
that, given an array A representing a sequence of N domino tiles, returns the minimum number of tiles that must be removed so that the remaining tiles form a correct domino sequence.
Examples:
- Given A = [2, 4, 1, 3, 4, 6, 2, 4, 1, 6], the function should return 3.
- Given A = [5, 1, 2, 6, 6, 1, 3, 1, 4, 3, 4, 3, 4, 6, 1, 2, 4, 1, 6, 2], the function should return 7. The domino tiles that should remain are: (2, 6), (6, 1), and (1, 2).
- Given A = [1, 5, 3, 3, 1, 3], the function should return 2. No pair of dominoes can be connected without rotating or reordering them.
- Given A = [3, 4], the function should return 0.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..50,000];
- The length of array A is equal to 2*N;
- Each element of array A is an integer within the range [1..6].
You are given an array A of N integers.
Three elements of A are called non-adjacent if their consecutive indexes all differ by more than 1. What is the maximum sum of three non-adjacent elements from A?
For example, given A = [8, -4, -7, -5, -5, -4, 8, 8]:
- Elements in positions 0, 3, and 6 are non-adjacent, and their sum is 8+(−5)+8=118 + (-5) + 8 = 118+(−5)+8=11.
- Elements in positions 0, 6, and 7 sum up to 8+8+8=248 + 8 + 8 = 248+8+8=24, but they are not non-adjacent.
- Elements in positions 0, 5, and 7 are non-adjacent and sum up to 8+(−4)+8=128 + (-4) + 8 = 128+(−4)+8=12.
The third choice is optimal because there is no way to choose any other three non-adjacent elements with a larger sum.
Write a function:
def solution(A):
that, given an array A of N integers, returns the maximum sum of three non-adjacent elements from A.
Examples:
- Given A = [8, -4, -7, -5, -5, -4, 8, 8], the function should return 12. As explained above, you can choose elements in positions 0, 5, and 7.
- Given A = [-2, -8, 1, 5, -8, 4, 7, 6], the function should return 15. The optimal choice of positions is 3, 5, and 7.
- Given A = [-3, 0, -6, -7, -9, -5, -2, -6], the function should return -9. The optimal choice of positions is 1, 3, and 6.
- Given A = [-10, -10, -10, -10, -10], the function should return -30.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [5..100,000];
- Each element of array A is an integer within the range [-100,000,000..100,000,000].
我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。
We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.
