微软暑期实习笔试2021.02.26

01 - 编程题01

We will call a sequence of integers a spike if they first increase (strictly) and then decrease (also strictly, including the last element of the increasing part). For example (4, 5, 7, 6, 3, 2) is a spike, but (1,1, 5, 4, 3) and (1, 4, 3, 5) are not.

Note that the increasing and decreasing parts always intersect, e.g.: for spike (3, 5, 2) sequence (3, 5) isan increasing part and sequence (5, 2) is a decreasing part, and for spike (2) sequence (2) is both an increasing and a decreasing part.

Your are given an array A of N integers. Your task is to calculate the length of the longest possible spike, which can be created from numbers from array A. Note that you are NOT supposed to find the longest spike as a sub-sequence of Ak, but rather choose some numbers from A and reorder them to create the longest spike. (不是找子序列 而是可以重新排列)

Write a function:

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

which, given an array A of integers of length N, returns the length of the longest spike which can be created from the numbers from A.

Examples:

1. Given A = [1, 2] your function should return 2, because (1, 2) is already a spike.

2. Given A = [2, 5, 3, 2, 4, 1] your function should retum 6, because we can create the following spike of length 6: (2, 4, 5, 3, 2, 1).

3. Given A = [2, 3, 3, 2, 2, 2, 1] your function should return 4, because we can create the following spike of length 4: (2, 3, 2, 1) and we cannot create any longer spike. Note that increasing and decreasing parts should be strictly increasing/decreasing and they always intersect.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1 - 100,000]

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

---

还是要好好审题哈 这题要是不可排序就是典型的LIS问题了 前序LIS 后序LDS 然后枚举中间点找最大值

这题感觉就是简单的贪心了 首先统计每个元素出现的次数，然后最大值必在中间只能出现一次 剩下的元素最多出现两次（在左右两边） 好了

class Solution
{
public:
int solution(vector<int>& A) // 这是不行的 数组指针传参就没有大小信息了
{
    if(A.empty()) return 0;
    unordered_map<int, int> h;
    int max_val = -0x3f3f3f3f;
    for(int i = 0; i < A.size(); i++)
    {
        h[A[i]]++;
        max_val = max(max_val, A[i]);
    }
    int res = 1;
    for(auto& p : h)
    {
        if(p.first == max_val) continue;
        res += min(2, p.second);
    }
    return res;
}
}

02 - 编程题02

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: 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 2.

4. Given A = [1, 5, 2, 4, 3, 3], 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]

---

我也没有oj哈 但看这个意思得写一个O(n)

想了半天的DP 后来发现这个问题可以拆分成 枚举每个和出现的所有区间 然后计算最大不相交区间个数

我们先来回顾一下计算最大不相交区间个数的方法-> 贪心问题：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
using PII = pair<int, int>;
class Solution{
public:
    int solution(vector<int>& A)
    {
        unordered_map<int, vector<PII>> hash;
        for(int i = 1; i < A.size(); i++)
        {
            hash[A[i - 1] + A[i]].emplace_back(i - 1, i);
        }
        // 不必排序了 一定是有序的
        int res = 0;
        for(auto& p : hash)
        {
            res = max(res, find(p.second));
        }
        return res;
    }
    int find(vector<PII>& intervals)
    {
        int res = 0, cur_r = -2e9;
        for(int i = 0; i < intervals.size(); i++)
        {
            int l = intervals[i].l, r = intervals[i].r;
            if(cur_r < l)
            {
                cura_r = r;
                res ++;
            }
        }
        return res;
    }
}

---

03 - 编程题03

A non-empty array A consisting of N non-negative integers is given. Its 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: [1, 5, 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:

class Solution{public int solution(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 [1,0,2,0,0,2] the function should return 3 because: • the binarian of A is 13

• array B such that B[0] = 3, B[1] = 2 and B[2] = 0 also has a binarian of 13,

• there is no shorter array with a binarian of 13.

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

---

这题应该就是猛转二进制了吧.. 但是数据太大估计的用bitset

const int N = 10100;

class Solution{
public:
    int solution(vector<int>& A)
    {
        bitset<N> f;
        for(int i = 0; i < A.size(); i++)
        {
            int j = A[i];
            bool flag = true;
            while(flag)
            {
                flag = f[j] & flag;
                if(flag)
                    f[j++] = false;
                else
                    f[j++] = true;
            }
        }
        return f.count();
    }
};