技术 / 杂项

2019-05-06

【2019暑期实习】微软面经

写在前面

  • 以下经历均为笔者和女友在2019年暑期实习的面试经历, 本文仅作我二人整理复盘之用, 请勿转载.
  • 4月18面试，4月23收到C信，4月25收到正式offer，这速度也是没谁了，给个赞！

女友一面 (20190418, 60min)

  • 自我介绍, 项目
  • 10盒小球, 每盒10个, 其中有一盒小球19克每个, 其余小球20克每个, 有一台秤, 称一次求出哪盒小球为19克
  • 输入：size和path, 其中size=0代表path是文件夹, 不为0代表文件, 输入若干size和path, 求某文件夹下的文件总大小(手撕)
  • 二叉树中两个节点的最低公共祖先(手撕)

女友二面 (20190418, 60min)

  • 自我介绍
  • 剪绳子问题 , 给你一根长度为N的绳子, 请把绳子剪成任意段(m,n都是整数), 每段绳子的长度记为k[0],k[1],k[2]…. 请问如何剪绳子使得k[0],k[1],k[2]的乘积最大, 例如：绳子长度8 最大乘积18 = 2x3x3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

int Solve(int n)
{
    if(n<2)
        return 1;
    if(n==2)
        return 2;
    if(n==3)
        return 3;
    int *p=new int[n+1];
    p[0]=0;
    p[1]=1;
    p[2]=2;
    p[3]=3;
    int max = 0;
    for(int i=4; i<=n; i++)
    {
        max=i;
        for(int j=1; j<=i/2; j++)
        {
            int q = p[j]*p[i-j];
            if(max<q)
                max=q;
        }
        p[i]=max;
    }
    max=p[n];
    delete[] p;
    return max;
}
  • 二叉树, 求所有根节点到叶子节点和等于指定值的路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14

vector<vector<int> > res;
vector<int> node;
vector<vector<int> > FindPath(TreeNode* root, int sum)
{
    if(!root)
    return res;
    node.push_back(root->val);
    if(!root->left && !root->right && sum-root->val==0)
        res.push_back(node);
    FindPath(root->left, sum - root->val);
    FindPath(root->right, sum - root->val);
    node.pop_back();
    return res;
}

女友三面 (20190418, 45min)

  • n进制高精度乘法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

#include <bits/stdc++.h>
using namespace std;
 
char radix[16] = { '0',' 1',' 2',' 3',' 4',' 5',' 6',' 7',' 8',' 9',' A',' B',' C',' D',' E',' F' };
map<char, int> radixindex = { {'0',0},{'1',1},{'2',2},{'3',3},{'4',4},{'5',5},{'6',6},{'7',7},{'8',8},{'9',9},{'A',10},{'B',11},{'C',12},{'D',13},{'E',14},{'F',15} };
 
string delete_zero(const string& s1)
{
    string a = s1;
    stringstream sres;
    int i = 0;
    while (a[i] == '0')
        i++;
    for (; i < s1.size(); i++)
    {
            sres << a[i];
    }
    string res = sres.str();
    if (res.size() == 0)
        return "0";
    return res;
}
 
string HA_add(const string& s1, const string& s2, const int& n)
{
    auto a = s1, b = s2;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    for (int i = min(a.size(), b.size()); i < max(a.size(), b.size()); ++i)
    {
        if (a.size() <= i)
            a += "0";
        if (b.size() <= i)
            b += "0";
    }
 
    stringstream sres;
    int i = 0;
    int carry = 0;
    while (i < a.size())
    {
        int cur = radixindex[a[i]] + radixindex[b[i]] + carry;
        if (cur >= n)
        {
            cur -= n;
            carry = 1;
        }
        else
            carry = 0;
        sres << radix[cur];
        i++;
    }
    if (carry == 1)
        sres << carry;
    string res = sres.str();
    reverse(res.begin(), res.end());
    return delete_zero(res);
}
 
string HA_multi_single(const string& s1, const int&  single, const int& n)
{
    string a = s1;
    reverse(a.begin(), a.end());
    stringstream sres;
    int carry = 0;
    for (int i = 0; i < a.size(); i++) {
        int cur = radixindex[a[i]] * single + carry;
        sres << radix[cur % n];
        carry = cur / n;
    }
    while (carry != 0)
    {
        sres << radix[carry % n];
        carry /= n;
    }
    string res = sres.str();
    reverse(res.begin(), res.end());
    return delete_zero(res);
}
 
string HA_multi(const string& s1, const string& s2, const int& n)
{
    string a = s1, b = s2;
    if (s1.size() < s2.size())
    {
        a = s2;
        b = s1;
    }
    reverse(b.begin(), b.end());
    string res = "0";
    for (int i = 0; i < b.size(); i++)
    {
        stringstream tmp;
        tmp << HA_multi_single(a, radixindex[b[i]], n);
        for (int j = 0; j < i; j++)
            tmp << "0";
        res = HA_add(res, tmp.str(), n);
    }
    return delete_zero(res);
}
 
int main()
{
    cout << HA_add("15", "15", 10) << endl;
    cout << HA_multi("15", "125F", 16) << endl;
}

笔者一面 (20190419, 42min)

  • 自我介绍.
  • 有3个连续的自然数, 大于6的整数, 已知第一个和第三个是质数, 第二个数能被 6 整除.
  • LeetCode 164
    >有一个无序整型数组, 如何求出这个数组排序后的任意两个相邻元素的最大差值？要求时间和空间复杂度尽可能低. (例如：无序数组 2、3、1、4、6, 排序后是1、2、3、4、6, 最大差值是 6-4=2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
bool flag = true;
int MapToBucket(const LL& num, const LL& len, const LL& min, const LL& max)
{
    return (num - min) * len / (max - min);
}
LL MaxGap(const vector<LL> & nums)
{
    if (nums.size() < 2)
    {
        flag = false;
        return 0;
    }
    int len = nums.size();
    LL a = nums[0];
    LL b = nums[0];
 
    for (int i = 0; i < len; ++i)
    {
        a = min(nums[i], a);
        b = max(nums[i], b);
    }
 
    if (a == b)
        return 0;
 
    vector<bool> BucketNum(len + 1, false);
    vector<LL> mins(len + 1);
    vector<LL> maxs(len + 1);
 
    for (int i = 0; i < len; ++i)
    {
        int BucketID = MapToBucket(nums[i], len, a, b);
        if (BucketNum[BucketID])
        {
            mins[BucketID] = min(mins[BucketID], nums[i]);
        }
        else
        {
            mins[BucketID] = nums[i];
        }
 
        if (BucketNum[BucketID])
        {
            maxs[BucketID] = max(maxs[BucketID], nums[i]);
        }
        else
        {
            maxs[BucketID] = nums[i];
        }
 
        BucketNum[BucketID] = true;
    }
 
    LL res = 0;
    LL preMax = maxs[0];
 
    for (int i = 1; i <= len; i++)
    {
        if (BucketNum[i])
        {
            res = max(res, mins[i] - preMax);
            preMax = maxs[i];
        }
    }
    return res;
}
 
int main()
{
    vector<LL> a = { 12,4,2,54,9 };
    cout << MaxGap(a) << endl;
    return 0;
}

笔者二面 (20190419, 60min)

  • 自我介绍, 项目
  • top k问题
  • Fibonacci数列：F[0]=0,F[1]=1,F[i]=F[i-1]+F[i-2], 假设FF[i]=F[i]xF[i], sum(FF[l...r]) % M == 0 | min(r)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int sort(int a[], int low, int high)
{
    int pivot = a[low];
    low++;
    if (low < high)
    {
        while (low < high && a[high] >= pivot) // <-
            high--;
        a[low++] = a[high];
        while (low < high && a[low] <= pivot)
            low++;
        a[high--] = a[low];
    }
    a[low] = pivot;
    return low;
}
 
int kth_element(int nums[], int low, int high, int k)
{
    if (low > high)
        return nums[low];
    else
    {
        int mid = sort(nums, low, high);
        if (mid > k)
            return kth_element(nums, low, mid - 1, k);
        else if (mid < k)
            return kth_element(nums, mid + 1, high, k); // <-
        else
            return nums[mid];
    }
}
 
/*
F[0] = 1
F[1] = 1
F[2] = 2
F[3] = 3
F[4] = 5
...
FF[i] = F[i] * F[i]
sum(FF[l...r]) % M == 0 | min(r)
*/
 
int sumFF(int n, int m) {
    // sum FF[0...n]
    int a = 1;
    int b = 1;
    if (n == 0)
        return a;
    if (n == 1)
        return b;
    int res = 2;
        for (int i = 2; i <= n; i++)
        {
            int tmp = res;
            res = (a + b) % m;
            a = b;
            b = res;
        }
    return (res % m) * ((res + b) % m);
}
 
pair<int, int> FFModMEquals0(int m) {
    int l = 0, r = 0;
    while (true)
    {
        for (int l = 0; l < r; l++)
        {
            int res = sumFF(r, m) - sumFF(l, m);
            if (res == 0)
                return make_pair(l, r);
        }
        r++;
    }
}

笔者三面 (20190419, 45min)

  • n个有序链表 求至少在m个链表中出现的元素集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include<bits/stdc++.h>
using namespace std;
 
// n个升序的链表, 找一个集合, 至少在m个链表中出现. 
 
struct ListNode {
    int val;
    ListNode* next;
};
 
bool flag = true;
vector<int> FindMTimes(const vector<ListNode*>& LinkedList, const int& m)
{
    vector<int> res;
    for (auto& i : LinkedList)
    {
        if (i == nullptr)
        {
            flag = false;
            return res;
        }
    }
    int minval = LinkedList[0]->val;
    for (auto& i : LinkedList)
    {
        minval = min(i->val, minval);
    }
 
    vector<ListNode*> pointer(LinkedList.size(), nullptr);
    for (size_t i = 0; i < pointer.size(); i++)
    {
        pointer[i] = LinkedList[i];
    }
    int count = LinkedList.size();
 
    int pivot = minval;
    while (count > 0)
    {
        int tmp = 0;
        int nextpivot = pivot;
        for (size_t i = 0; i < pointer.size(); i++)
        {
            bool has = false;
            while (pointer[i] != nullptr && pointer[i]->val == pivot)
            {
                has = true;
                pointer[i] = pointer[i]->next;
            }
            if (has)
                tmp++;
            if (pointer[i] == nullptr)
                count--;
            else
                nextpivot = min(pointer[i]->val, nextpivot);
        }
        if (tmp >= m)
            res.push_back(pivot);
        pivot = nextpivot;
    }
    return res;
}
 
int main()
{
    return 0;
}

Tags:

Share

You may also like...

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。