2021.02.27微软笔试题目

Task 1

Write a function solution that, given a string S consisting of N characters,returns the alphabetically smallest string that can be obtained by removing exactly one letter from S.

Examples:

1. Given S = “acb”, by removing the letter, you can obtain “ac”, “ab” or”cb”.Your function should return “ab” (after removing ‘c’) since it is alphabetically smaller than “ac” and “bc”.

2. Given S= “hot”, your function should return “ho”,which is alphabetically smaller than “ht” and “ot”.

3. Given S=”codility”,your function should return “cdility”, which can be obtained by removing the second letter.

4. Given S=”aaaa”, your function should return “aaa”. Any occurrence of ‘a’ can be removed.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [2..100,000];

• string S consists only of lowercase letters (a-z).

Task 2

You are given an array A of integers. Find the maximum number of non-intersecting segments of length 2 (two adjacent elements), such that segments have an equal sum.

For example, given $A=[10,1,3,1,2,2,1,0, 4]$, there are three non-intersecting segments, each whose sum is equal to 4: $(1,3),(2, 2),(0,4)$.Another three non-intersecting segments are: $(3,1),(2,2),(0,4)$.

Write a function:
int solution(vector<int>& A);

that,given an array A of N integers,returns the maximum number of segments with equal sums.

Examples:

1. Given $A = [10,1,3,1,2,2,1,0, 4]$, the function should return 3, as explained above.
2. Given $A=[5,3,1,3,2, 3]$, the function should return 1. Each sum of two adjacent elements is different from the others.
3. Given $A= [9,9,9,9,9]$, the function should return 3. There are three segments:$(1, 5),(2, 4),(3, 3)$ whose sums are equal to 6.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range $[2..100,000]$;

• each element of array A is an integer within the range $[0..1,000,000,000]$.

Task 3

A non-empty array A consisting of N non-negative integers is given. lts binarian is defined as:

$binarian(A)=pow2(A[0])+pow2(A[1])+…+pow2(A[N-1])$

$pow2(K) = 2^K$

For example, the binarian of array A such that:

$A[0]=1$

$A[1]=5$

$A[2]=4$

equals 50:

$$binarian(A)=pow2(A[0])+pow2(A[1])+pow2(A[2]) =pow2(1)+pow2(5)+pow2(4) =2+32+16 =50$$

Write a function:

int solution(vector<int>& A);

that, given an array A consisting of N non-negative integers, returns the length of the shortest array that has the same binarian as array A.

For example, given array A such that:

$A[0]=1$

$A[1]=0$

$A[2]=2$

$A[3]=0$

$A[4]=0$

$A[5]=2$

the function should retun 3 because:

$A[0]=0$

$A[1]=2$

$A[2]=3$

has the same binarian as array A and the shorest length.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range $[0..100,000]$;

• each element of array A is an integer within the range $[0..10,000]$.

赏

谢谢你请我吃糖果