微软暑期实习笔试2021.03.05

01 - 编程题01

这题还有中文哈哈哈 还是看看英文吧

You are a programmer in a scientific team doing research into particles. As an experiment, you have measured the position of a single particle in N equally distributed moments of time. The measurement made in moment K is recorded in array A as A[K].

Now, your job is to count all the periods of time when the movement of the particle was stable.

Those are the periods during which the particle doesn't change its velocity: i.e. the difference between any two consecutive position measurements remains the same. Note that you need at least three measurements to be sure that the particle didn't change its velocity. For example:

• 1, 3, 5, 7, 9 is stable (velocity is 2)

• 7, 7, 7, 7 is stable (particle stays in place)

• 3, -1, -5, -9 is stable (velocity is -4)

• 0, 1 is not stable (you need at least three measurements)

• 1, 1, 2, 5, 7 is not stable (velocity changes between measurements)

More formally, your task is to find all the periods of time A[P],A[P+1], ...,A[Q] (of length at least 3) during which the movement of the particle is stable. Note that some periods of time might be contained in others (see example test).

Write a function: class Solution { public int solution(int[] A};

that, given array A consisting of N integers representing the results of the measurements, returns the number of periods of time when the movement of the particle was stable. The function should return -1 if the result exceeds 1,000,000,000. Examples: Given array A = [-1, 1, 3, 3, 3, 2, 3, 2, 1, 0] the function should return 5, because there are five periods during which the movement of the particle is stable, namely: (0, 2), (2, 4), (6, 9), (6, 8) and (7, 9). Note that the last two periods are contained by (6, 9).

Assume that • N is an integer within the range [0..100];

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

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

---

这题我以为是签到题了 看来后面还有更签到的

这题解法多啦 总的来说就是计数DP 找到等差数列的数量

状态：f[i]表示以A[i]结尾的等差数列个数

f[i] = f[i - 1] + 1; f[i - 1] 就是之前接上A[i]的个数 1就是（A[i-2], A[i-1], A[i])

举个例子： 1 2 3 4 -> 5; f[4] = 2([2,3,4], [1,2,3,4]) , f[5] = 3([3,4,5], [2,3,4,5],[1,2,3,4,5])

当然空间可以优化成o(1)

class Solution
{
public:
    int solution(vector<int>& A)
    {
        int n = A.size();
        vector<int> A(n + 1);
        int res = 0, f = 0;
        for(int i = 2; i < n; i++)
        {
            if(A[i] - A[i - 1] == A[i - 1] - A[i - 2])
                f = f + 1;
            else f = 0;
            res += f;
        }
        return res;
    }
};

02 - 编程题02

You are given an array A consisting of N integers within the range [1..N]. In one move, you can increase or decrease the value of anyone by 1. After each move, all numbers should remain within the range [1..N].

our task is to find the smallest required number of moves to make all elements in the array pairwise distinct (i.e. no value can appear in the array more than once). Write a function:

class Solution { public int solution(int[] A))

That, given an array A consisting of N integers, returns the smallest number of moves required to make all elements in the array •airwise distinct. If the result is greater than 1,000,000,000, the function should return -1.

examples:

1. Given A = [1, 2, 1], the function should return 2, because you can increase A[2] twice: [1, 2, 1] -> [1, 2, 2] -> [1, 2, 3]. In this example, ou could also change the array to the following values in two moves: [3, 2, 1], [1, 3, 2], [2, 3, 1].

2. Given A = [2, 1, 4, 4], the function should return 1, as it is sufficient to decrease A[2] or A[3] by 1, resulting in [2, 1, 3, 4] or [2, 1, 4, 3].

3. Given A = [6, 2, 3, 5, 6, 3], the function should return 4, because you can achieve the following array in four moves: [6, 2, 1, 5, 4, 3].

Write an efficient algorithm for the following assumptions: • N is an integer within the range [1.200,000]: • each element of array A is an integer within the range [1..N].

---

这题想不明白有一个测试点过不去🆘

很直接了 从小到大排序 计算到 [1,2,3,4, ... N]的距离就好了

class Solution
{
public:
    int solution(vector<int>& A)
    {
        sort(A.begin(), A.end());
        int res = 0;
        for(int i = 1; i <= A.size(); i++)
            res += abs(A[i] - i);
        return res;
    }
}

---

03 - 编程题03

You are given N fractions. Fractions are represented as two arrays, X and Y of length N, containing the fraction numerators and denominators respectively. Write a function solution that, given such arrays X and Y of length N, returns the number of possible ways to choose a pair of ractions that sum up to 1.

Since the answer can be large, provide it modold 10^9 + 7 (1,000,000,007). Note that a single fraction can orm multiple pairs.

Examples:

1. Given X = [1, 1, 2], Y = [3, 2, 3], the function should return 1. The input represents fractions 1/3,1/2, 2/3, and the only pair that sums up to 1 is (1/3, 2/3)

2. Given X = [1, 1,1], Y = [2, 2, 2], the function should return 3. The input represents 1/2,1/2,1/2. There are three ways to choose a pair hat sums up to 1.

3. Given X = [1, 2, 3, 1, 2, 12, 8, 4], Y = [5, 10, 15, 2, 4, 15, 10, 5], the function should return 10.

Write an efficient algorithm for the following assumptions

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

• each element of arrays X, Y is an integer within the range [1..1,000,000,000].

---

这题Leetcode第一题的化身啊哈哈哈 用哈希表存target - A[i]出现的次数即可

这里难一点的地方无非在分数的化简和pair不能哈希上面，都比较好解决；

using ULL = unsigned long long;
const int mod = 1e9 + 7;
class Solution{
public:
    int gcd(int a, int b)
    {
        return b ? gcd(b, a % b) : a;
    }
    ULL hash_func(int a, int b)
    {
        return a * 1000000001 + b;
    }
    int solution(vector<int>& X, vector<int>& Y)
    {
        unordered_map<ULL, int> hash;
        int res = 0;
        for(int i = 0; i < X.size(); i++)
        {
            int a = X[i], b = Y[i], ab = gcd(a, b);
            ULL query = hash_func(b / ab - a / ab, b / ab), cur = hash_func(a / ab, b / ab);
            if(hash.count(query))
                res = (res + hash[query]) % mod;
            hash[cur]++;
        }
        return res;
    }
}