Autumn Recruitment

字节跳动

2019.07.09 字节提前批一面

上来介绍简历各个项目及技术栈，之后问数据库表示没怎么用，转而问数据结构相关问题

知道哪些数据结构

vector, list, stack, queue, priority_queue, set, multiset, map, unordered_map, unordered_set

priority_queue和queue对比

priority_queue本质是堆

id, name, score的结构体，按照id排序，然后根据id访问成绩

用map即可，因为map是红黑树可以对key排序

之后区块链项目多说了几句，再写了一道题，求区间覆盖长度

有多个区间，求覆盖长度，坐标类型为float

[1, 2.1], [2, 4], [5, 6]
[1, 4] + [5, 6] = 3

思路

将线段按照左端点排序，然后记录当前最远右端点，看当前最远的右端点有没有覆盖之后的左端点

• 覆盖 - 比较更新最远又断线
• 没有覆盖 - 计算前一段覆盖长度，然后再重新开始计算

代码如下

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

float getCoverageLength(vector<pair<float, float>>& data) {
    if (data.size() == 0) return 0;
    sort(data.begin(), data.end());
    float result = 0, l = data[0].first, r = data[0].second;
    for (auto p : data) {
        if (p.first <= r) r = max(r, p.second);
        else {
            result += (r - l);
            l = p.first;
            r = p.second;
        }
    }
    result += (r - l);
    return result;
}

int main() {
    vector<pair<float, float>> data = {{1, 3}, {2, 4}};
    cout << getCoverageLength(data) << '\n';
}

2019.07.12 字节提前批二面

一上来写算法题，都很简单

第一道

在横纵向都是有序的矩阵里查找一个数，从左下角或右上角开始查找即可

第二道

股票n天数据，单次买卖最大收益，两次买卖最大收益

121

123

感觉面试官就准备了这三道题，都写完后就简单问了些问题

1*2 2*2两种瓷砖铺2*n的路，有多少种方式

fibonacci数列

https原理

非对称加密传输证书，之后用动态加密来传输

2019.07.18 字节提前批三面

没问任何基础问题，上来问对后端怎么理解

之后说设计一个方案，完成多台服务器上某个服务的版本更新

回答选出几个代表，然后把更新传给代表，同时各服务器定时广播自己的版本，邻居发现其落后后，推送更新

如何查询版本更新状况

各服务器和代表机器定时沟通，作用是保证代表机器存在，类似于raft，同时推送自己的版本信息，由代表完成汇总

平时有看技术书的习惯吗，有哪些学习计划

瞎扯

过去实习哪段比较成功

瞎扯

大约20分钟左右就结束了三面

2019.07.26 Offer Call

完成三面后一直毫无音讯，极度焦虑的状态下度过了一周多，期间问过HR很多次，说面评挺好，应该没问题

下班回来后接到offer call，复旦的HR小姐姐说了下分配的组，确认了下工作地点在上海，然后就收到了意向书邮件

在AI Lab做后台开发工程师

---

云从科技

2019.08.01 一面

C++内存管理

TCP为什么是三次握手

应该是完成序列号的同步，并且都知悉对方获知了序列号

static作用

相比全局变量只是文件内可见

多态实现方式，虚函数原理

虚函数表来实现

C++智能指针机制

C++模板实现机制

无限数据流怎么随机抽样

思路就是在前面的数中以一定概率丢弃一个，然后一定概率插入后来来的数

假设要保留$m$个数，方案是对第$i>m$个数，以$\frac{m}{i}$概率保留这个数，在前面$m$个数中随机选取一个

这里用数学归纳即可推导

• 第$m+1$个数，如此操作，前$m$个数保留的概率为$\frac{1}{m+1}+\frac{m}{m+1}\times \frac{m-1}{m}=\frac{m}{m+1}$，每个数都是$\frac{m}{m+1}$概率保留，成立
• 若前$k$个数，都是以$\frac{m}{k}$概率保留
• 对第$k+1$个数，有$\frac{m}{k+1}$概率保留，那么前面的数保留概率为$\frac{m}{k}(\frac{k+1-m}{k+1}+\frac{m}{k+1}\times \frac{m-1}{m})=\frac{m}{k+1}$

故每个数都是等概率选取

一个数组，甲乙两个人从后面取数，目标是取得数之和最大，求先取的人的最大结果

动归

#include <iostream>
#include <vector>
using namespace std;

int f(vector<int>& v, int k) {
    vector<int> s(v.size(), 0);
    vector<int> dp(v.size(), 0);
    int sum = 0;
    for (int i = 0; i < v.size(); i ++) {
        sum += v[i];
        s[i] = sum;
    }
    dp[0] = v[0];
    for (int i = 1; i < v.size(); i ++) {
        int mx = INT_MIN;
        for (int j = 1; j <= k; j ++) {
            if (i - j < 0) break;
            int sum_j = s[i] - s[i - j];
            sum_j += (s[i - j] - dp[i - j]);
            mx = max(mx, sum_j);
        }
        dp[i] = mx;
    }
    for (int i : dp) cout << i << ' ';
    cout << '\n';
    return dp.back();
}

int main() {
    vector<int> v = {-1, -1, -1, -1, -1};
    cout << f(v, 2) << '\n';
}

2019.09.17 视频二面

问的数据库什么的都不会

---

网易

2019.08.03 笔试

选择题. 以下各类构造函数调用顺序

B b;
int main() {
    D* d = new D();
    A a;
    static C c;
}

B->D->A->C

1到n的数，给出一个排列，设是第i个排列，输出倒数第i个排列

将数字对换即可，i换成n+1-i

一个长n<=10^5的数组，然后求从1到n长的连续子序列的最大值的最小值，怎么解

例如数组为1 3 2 4 6 5，那么1的子序列只有一个数，最小值就是1，长为2的子序列有5个，最大值是3 3 4 6 5，其中最小的是2，类推，输出为1 3 3 4 6 6

没有思路，暴力解过了60%

后来大佬指点了下，用单调栈求每个数为最大值的最大区间长度，然后遍历一遍区间长度即可，以题中例子为例，每个值和其对应最大长度是

1 1
3 3
2 1
4 4
6 6
5 1

区间长度和该长度最小值对应为

1 2 3 4 5 6
1 / 3 4 / 6

然后从最小长度开始扫，如果该长度对应有值，那么该值即是这个长度最小的最大值；如果没有对应值，则为之后第一个对应值

如上，结果就是1 3 3 4 6 6

一个n*m的区域，有k个障碍点，之后有q个长方形货物，问是否能放下

矩阵前缀和

n,q<=200000，之后一个n的数组，数字范围也是1-n，之后是q次查询，每次输入一个1-n的数字，将数组中大于等于该数的所有数减一，并输出这些数的个数

input:
4 3
1 2 2 4
4
3
2
1

output:
1
1
3
4

用线段树来做

#include <iostream>
#include <algorithm>
using namespace std;

class Segment {
public:
    int left, right, num;
    Segment() {}
};

Segment st[419610];
int arr[200010];
int n, q;

int findNum(int rank, int num) {
    if (rank > 2 * n - 1) return 0;
    if (st[rank].right < num) return 0;
    else if (st[rank].left >= num) {
        st[rank].left --;
        st[rank].right --;
        if (st[rank].left == st[rank].right) return st[rank].num;
    } else if (st[rank].left < num && st[rank].right >= num) {
        st[rank].right --;
    }
    return findNum(rank * 2, num) + findNum(rank * 2 + 1, num);
}

int main() {
    cin >> n >> q;
    for (int i = 0; i < n; i ++) cin >> arr[i];
    sort(arr, arr + n);
    for (int i = n; i < 2 * n; i ++) {
        st[i].left = st[i].right = arr[i - n];
        st[i].num = 1;
    }
    for (int i = n - 1; i >= 1; i --) {
        st[i].left = st[2 * i].left;
        st[i].right = st[2 * i + 1].right;
        st[i].num = st[2 * i].num + st[2 * i + 1].num;
    }
    for (int i = 0; i < q; i ++) {
        int num; cin >> num;
        cout << findNum(1, num) << '\n';
    }
}

2019.08.14 视频一面

介绍项目

面试官对几段实习项目都问得比较细，然后一直在问有没有用到深度学习，对Tensorflow等框架有没有用过，然后通通答没有，感觉面试官很无语，然后就直接开始做题了。

一个街道N个位置，其中若干位置是需要照亮的，一个放在pos位置的台灯可以照亮[pos-1, pos+1]的位置，求最少需要几个路灯

直接贪心来做就行，每次发现一个照不到的位置，就在其后插一个路灯

正确性可以这样来想，每次插一个路灯，等于是把问题分为前半部分和后半部分，总体的最优解由两部分加起来即可

#include <iostream>
#include <string>
using namespace std;
int roadLamps(string road) {
    if (road.size() == 0) return 0;
    int last = -3, result = 0;
    for (int i = 0; i < road.size(); i ++) {
        if (road[i] == '.' && i > last + 1) {
            result ++; last = i + 1;
        }
    }
    return result;
}
int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i ++) {
        int n;
        string s;
        cin >> n >> s;
        cout << roadLamps(s) << '\n';
    }
}

n件零食，每件有一定体积，背包上限确定，求一共多少种放法

第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量。
第二行n个正整数v[i](0 <= v[i] <= 10^9),表示每袋零食的体积。

输出一个正整数, 表示牛牛一共有多少种零食放法。

因为背包上限和零食体积都是$10^9$量级，用迭代和动归感觉都会超出时间/空间复杂度

问面试官思路后说迭代+剪枝，想了下剪枝可以这样做

• 对零食体积排序，然后当剩余位置小于下一个节点位置时直接停止
• 保存已有结果，如果之后搜索过程中重复出现直接使用结果即可

面试官觉得还可以，不过时间问题没有写代码

线性回归和logstic回归什么区别

面试官最后还是问你啥都不懂为啥报这个，然后之前学过啥，然后随便问了这个问题

logstic回归主要用来解决分类问题，线性回归解决回归问题

2019.08.19 视频二面

false sharing和cache line

内存在不同GPU间是如何转移的

2019.08.26 HR面

打算放弃了

---

百度智能云

2019.08.07 电话一面

n个线段，每个有左右端点及高度，求累加的最大高度

这时候刚在看一道线段树的题，不自主地按这个来想，还好之后想了下排序就可以做

但好像不是面试官期望的解法，写完后和面试官解释了好一阵

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int height(const vector<vector<int>>& segments) {
    vector<pair<int, int>> ls, rs;
    for (auto& v : segments) {
        ls.push_back({v[0], v[2]});
        rs.push_back({v[1], v[2]});
    }
    sort(ls.begin(), ls.end());
    sort(rs.begin(), rs.end());
    int mx = 0, ptr = 0, height = 0;
    for (auto p : ls) {
        while (ptr < rs.size() && p.first >= rs[ptr].first) {
            height -= rs[ptr].second;
            ptr ++;
        }
        height += p.second;
        mx = max(mx, height);
    }
    return mx;
}
int main() {
    vector<vector<int>> v = {{1, 3, 2}, {1, 3, 1}};
  cout << height(v) << '\n';
}

字符串解析，[代表按下home，]代表按下end

题目很简单，直接上手写了代码

之后面试官说期望的是用链表来做，确实这样会简洁一些

#include <iostream>
#include <deque>
#include <iterator>
#include <string>
#include <list>
using namespace std;
std::string construct(std::string s) {
    std::list<char> l;
    std::list<char>::iterator it = l.begin();
    for (char c : s) {
        if (c == '[') it = l.begin();
        else if (c == ']') it = l.end();
        else l.insert(it, c);
    }
    std::string res = "";
    for (char c : l) res += c;
    return res;
}
string f(const string& s) {
    deque<string> d;
    int head = 0, tail = 0;
    bool dir = true;
    while (tail < s.size()) {
    if (s[tail] == '[' || s[tail] == ']') {
        string str = s.substr(head, tail - head);
        head = tail + 1;
        if (dir) d.push_front(str);
        else d.push_back(str);
        dir = s[tail] == '[' ? true : false;
    }
    tail ++;
    }
    if (head < s.size()) {
        string str = s.substr(head);
        if (dir) d.push_front(str);
        else d.push_back(str);
    }
    string res = "";
    for (auto str : d)
        if (str.size() > 0) res += str;
    return res;
}
int main() {
    cout << f("abc[[[xyz]123") << '\n';
    cout << construct("abc[[[xyz]123") << '\n';
}

2019.08.08 电话二面

Linux命令

• 匹配一些关键词
• 不匹配关键词
• 查看进程栈

从点击url到返回页面的全过程

红黑树、B+树、哈希表区别

简单说了一下各自的特点，感觉这几个没什么太大联系

有没有看过一种语言哈希表的具体实现方式

stl是用桶来完成，在元素超过哈希表大小后扩容

TCP TIME_WAIT状态

设计一个git

stoi代码

2019.08.13 电话三面

没有问任何技术问题，就项目和个人学习问了很多细节问题，几乎全程在扯淡，不知道这样能面出来什么东西？

讲一个之前做过的比较好的项目

最近问项目我都会说momenta那个，因为说这个面试官基本不了解，也不想在这个问题上多聊什么

但这次面试官揪着问了很多细节问题，例如为什么选这个讲？难度在哪里？重新设计会如何来做？写完是如何检查代码可以交付使用的？

平时怎么学东西

这里又问得很繁琐，举一个例子来说明，之后又问你学习过程中有遇到过哪些困难而放弃的例子，扯到了科研上，之后就一直乱扯

自己的短板

答太过注重细节，问怎么改正的，答先推进度再看细节

你有什么问题

问了下什么样的价值观是和百度匹配的，说到"简单可依赖"，多少年了还是这句空口号

---

猿辅导

2019.08.18 视频一面

线段拼接

排序，很快写完

BST中删除一个节点

面试官沟通有点奇怪，说是返回被删除的节点，其实这是做不到的

写了半天没写对，面试结束

leetcode原题 450

2019.08.24 视频二面

面试官比较年轻，上来后就写题

有个小插曲是信号不好，所以加了微信视频通话，结束后看了下朋友圈，发现是人大本科毕业就工作的，今年应该27岁

单向链表以N为单位进行翻转

刚开始说先翻转，然后每N个来翻，最后翻过来

然后问不翻转呢，用栈保存了一下，代码如下

#include <iostream>
#include <stack>
using namespace std;

class Node {
public:
    int n;
    Node* next;
    Node(int num) : n(num), next(nullptr) {}
};

Node* reserveInN(Node* root, int N) {
    stack<Node*> s;
    for (Node* node = root; node != nullptr; node = node->next) s.push(node);
    Node* head = nullptr;
    while (s.size() >= N) {
        stack<Node*> s1;
        for (int i = 0; i < N; i ++) {
            auto temp = s.top();
            s.pop();
            s1.push(temp);
        }
        while (!s1.empty()) {
            s1.top()->next = head;
            head = s1.top();
            s1.pop();
        }
    }
    while (!s.empty()) {
        s.top()->next = head;
        head = s.top();
        s.pop();
    }
    return head;
}

int main() {
    Node *node1 = new Node(1);
    Node *node2 = new Node(2);
    Node *node3 = new Node(3);
    Node *node4 = new Node(4);
    Node *node5 = new Node(5);
    Node *node6 = new Node(6);
    Node *node7 = new Node(7);
    Node *node8 = new Node(8);
    node1->next = node2; node2->next = node3; node3->next = node4;
    node4->next = node5; node5->next = node6; node6->next = node7;
    node7->next = node8;
    auto node = reserveInN(node1, 3);
    for (; node != nullptr; node = node->next) cout << node->n << ' ';
}

恢复二叉树

二叉树中两个节点交换，恢复回来

写了中序遍历得到结果，然后检查再恢复的代码

问能不能O(1)空间做，没写出来，其实是leetcode做过的题

99. Recover Binary Search Tree

思路其实完全一样，区别在于在中序遍历过程中，发现节点后就记录一下，最后交换过来

Linux下内核态和用户态，哪些系统调用

基础知识，却没答上来

chmod 741

三个用户组分别是User、Group、Other

权限是r=4，w=2，x=1

C++下LRU机制

hashmap+list

2019.08.31 现场终面

面试官是联合创始人之一，聊天感觉很舒服

没问太多问题，一道很简单算法题

然后问Linux文件系统，iNode，这里不知道

2019.09.20 现场加面

一开始问项目

之后问C++，问了C++11的智能指针和std::move

之后写了两道题，一道是大小堆找中位数加上哈希删除

---

腾讯

2019.08.09 视频一面

天美工作室打来的

• 面试官: 是否考虑成都
• 回答: 不考虑
• 面试官: 打扰了

面试不到一分钟结束

2019.08.17 笔试

1. 拼接字符串

HG[3|B[2|CA]]F
HGBCACABCACABCACAF

用栈做

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    string res = "";
    stack<int> numStack;
    stack<string> strStack;
    for (int i = 0; i < s.size(); i ++) {
        char c = s[i];
        if (c >= 'A' && c <= 'Z') {
            if (numStack.size() > 0) {
                strStack.top() += c;
            } else {
                res += c;
            }
        } else if (c == '[') {
            int num = 0;
            i ++;
            while (i < s.size() && s[i] != '|') {
                num = num * 10 + (s[i] - '0');
                i ++;
            }
            // cout << num << ' ' << s[i] << '\n';
            numStack.push(num);
            strStack.push("");
        } else if (c == ']') {
            int n = numStack.top();
            string all = "";
            string str = strStack.top();
            numStack.pop(); strStack.pop();
            while (n > 0) {
                n --;
                all += str;
            }
            if (numStack.size() > 0) strStack.top() += all;
            else res += all;
        }
    }
    cout << res << '\n';
}

2. 逆序对

输入n，范围为[1, 20]，之后给出2^n个整数，之后询问m次，m范围是$10^6$，每次给出一个q，范围是[0, n，对$2^q$长的各段进行颠倒，然后返回逆序对个数

很难，没有写对，思路大致如下

一个区间的逆序对个数=左区间逆序对+右区间逆序对+跨区间逆序对

用一个线段树来记录每个区间的逆序对数，以及是否颠倒，如果颠倒，逆序对个数就是n*(n-1)/2-equals减去原来逆序对个数

没写对

3. n条线段覆盖[0, L]

intput:
4 6
3 6
2 4
0 2
4 7
output:
3

说明，4条线段覆盖[0, 6]，用[0, 2]，[2, 4]和[4, 6]拼接即可，一共三段

排序后遍历即可

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, l;
    cin >> n >> l;
    vector<pair<int, int>> v;
    for (int i = 0; i < n; i ++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
    sort(v.begin(), v.end());
    int ptr = 0, end = 0, num = 0;
    while (end < l) {
        int mx = -1;
        while (v[ptr].first <= end) {
            mx = max(mx, v[ptr].second);
            ptr ++;
        }
        if (mx == -1) {
            cout << -1 << '\n';
            return 0;
        }
        end = mx;
        num ++;
    }
    cout << num << '\n';
}

4. 看楼房层数

n座楼房，问在每个位置能看到的楼房个数

input:
6
5 3 8 3 2 5
output:
3 3 5 4 4 4

说明，在第一个位置，能看到自身，向前看到3和8，一共是3

在位置3，向后看到5和3，向前看到3和5，加上自身，一共是5

解法就是对每个位置，算出来向前和向右能看到的楼数，然后加起来即可

计算部分，线性扫描一遍即可，用栈维护能看到的楼层，每次加入一个时pop掉被遮挡的楼

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> v(n, 0);
    for (int i = 0; i < n; i ++) cin >> v[i];
    vector<int> left(n, 0);
    vector<int> right(n, 0);
    stack<int> s;
    for (int i = 0; i < n; i ++) {
        left[i] = s.size();
        while(!s.empty() && v[i] >= s.top()) s.pop();
        s.push(v[i]);
    }
    stack<int> s2;
    for (int i = n - 1; i >= 0; i --) {
        right[i] = s2.size();
        while (!s2.empty() && v[i] >= s2.top()) s2.pop();
        s2.push(v[i]);
    }
    for (int i = 0; i < n; i ++) cout << left[i] + right[i] + 1 << ' ';
}

5. 休息天数

n天时间里，公司和健身房在若干天开放，不能连续两天工作或健身，问最少休息多少天

input:
4
1 1 0 0
0 1 1 0
output:
2

动归做即可，dpc[i]表示i天工作时所有忙碌天数，dpg[i]表示i天健身时所有忙碌天数

#include <iostream>
#include <vector>
using namespace std;

int company[1000000];
int gym[1000000];
int dpc[1000000];
int dpg[1000000];
int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i ++) cin >> company[i];
    for (int i = 0; i < n; i ++) cin >> gym[i];
    if (company[0]) dpc[0] = 1;
    if (gym[0]) dpg[0] = 1;
    for (int i = 1; i < n; i ++) {
        if (company[i]) dpc[i] = dpg[i - 1] + 1;
        else dpc[i] = max(dpc[i - 1], dpg[i - 1]);
        if (gym[i]) dpg[i] = dpc[i - 1] + 1;
        else dpg[i] = max(dpc[i - 1], dpg[i - 1]);
    }
    cout << n - max(dpc[n - 1], dpg[n - 1]) << '\n';
}

2019.08.22 PCG 光影研究室 一面

TCP拥塞控制算法

QUIC协议

http 1.1相比1.0的改进

I/O多路复用

C++为什么字节对齐

为了CPU一次可以完整读取

C++多态如何实现，如何防止菱形调用

虚继承

虚函数表机制

1000瓶药，有一瓶毒药，多少只老鼠试喝可以找出来

2019 late august 电话初面

电话面试问了一些项目问题，很快结束，不知道之后有没有复试

2019 medium september HR面

HR问你知道你要做什么吗，答不知道

莫名其妙的面试

---

美团

2019.08.28 现场一二三面

前两面都很简单，聊了聊项目，简单问了一道题，第三面HR面也是常规问题

2019.09.18 电话四面

先自我介绍

工作地点、工作内容的倾向

微软、百度实习项目介绍

P2P微博项目介绍

主要语言

new malloc调用过程

map查询修改时间，unordered_map的机制

你有什么问题问我

• 部门介绍
• 技术挑战
• 部门在北京和上海的分工

---

阿里

2019.08.30 笔试

做得很差

2019.09.08 阿里云 PolarDB 电话

问了很多问题，然后说会给过，接下来还有面试

2019.09.23 阿里高德 一面

开始问了一些C++问题

• new和malloc区别
• 空指针 悬垂指针
• 多态和重载
• C++内存

然后写了些代码

• 二分查找
• 最长公共子串

之后问了下项目

---

网易互娱

2019.09.07 笔试

笔试很简单，前三道题很快做完，第四道题一直超时，改到最后才AC

第一题 看一个整数的二进制是否回文

直接检查就行

#include <cstdio>

int T, N;
int main() {
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        scanf("%d", &N);
        int pos = 31;
        while (pos > 0) {
            if ((N >> pos) & 1) break;
            pos--;
        }
        int l = 0;
        bool result = true;
        while (pos > l) {
            if (((N >> pos) & 1) != ((N >> l) & 1)) {
                result = false;
                break;
            }
            pos--; l++;
        }
        if (result) printf("YES\n");
        else printf("NO\n");
    }
}

第二题 查看一个二叉树是否每层和递增

#include <cstdio>
#include <vector>
#include <deque>
using namespace std;

int nodes[1010];
int ls[1010];
int rs[1010];
int T, N, value, left, right;

int main() {
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        scanf("%d", &N);
        vector<bool> root(N, true);
        for (int j = 0; j < N; j++) {
            scanf("%d%d%d", &nodes[j], &ls[j], &rs[j]);
            if (ls[j] > -1) root[ls[j]] = false;
            if (rs[j] > -1) root[rs[j]] = false;
        }
        deque<int> q;
        for (int j = 0; j < N; j++) {
            if (root[j]) {
                q.push_back(j);
                break;
            }
        }
        bool result = true;
        long long s = nodes[q.front()];
        while (!q.empty()) {
            int size = q.size();
            long long tmp = 0;
            for (int j = 0; j < size; j++) {
                int rank = q.front();
                q.pop_front();
                if (ls[rank] > -1) {
                    q.push_back(ls[rank]);
                    tmp += nodes[ls[rank]];
                }
                if (rs[rank] > -1) {
                    q.push_back(rs[rank]);
                    tmp += nodes[rs[rank]];
                }
            }
            if (q.size() > 0 && tmp <= s) {
                result = false;
                break;
            }
            s = tmp;
        }
        if (result) printf("YES\n");
        else printf("NO\n");
    }
}

第三题 一个月三十天，隔至少K天才能喝一杯咖啡，而有M天必须喝咖啡，最多一个月喝多少杯

直接模拟即可

#include <cstdio>

int T, M, K;
int days[31];
int main() {
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        for (int j = 0; j < 31; j++) days[j] = 0;
        scanf("%d%d", &K, &M);
        int num = 0;
        for (int j = 0; j < M; j++) {
            int rank;
            scanf("%d", &rank);
            days[rank] = 1;
            num++;
            int l = rank - 1;
            while (l > 0 && rank - l <= K) days[l--] = 1;
            int r = rank + 1;
            while (r < 31 && r - rank <= K) days[r++] = 1;
        }
        int t = 0;
        for (int j = 1; j <= 30; j++) {
            if (days[j] != 0) t = 0;
            else if (t == 0) {
                t = K;
                num++;
            } else t--;
        }
        printf("%d\n", num);
    }
}

第四题 一个包含N*M个小方格的长方形，其中若干格子被染色，问最大的构成正方形十字架的范围，N和M范围都是[1, 2000]

遍历每个顶点，二分搜索得到可能的长度，然后检查是否是十字架

#include <iostream>
#include <string>
using namespace std;

int T;
int rec[2001][2001];
int M, N;
int A, B, C, D, MX;

int getNum(int a, int b, int c, int d) {
    return rec[c][d] - rec[a-1][d] - rec[c][b-1] + rec[a-1][b-1];
}
int testCross(int i, int j, int k) {
    if (getNum(i, j + k, i + 3*k - 1, j + 2*k-1) != k*k*3) return 0;
    if (getNum(i + k, j, i + 2*k - 1, j + 3*k-1) != k*k*3) return 0;
    if (getNum(i, j, i + 3*k - 1, j + 3*k - 1) != k*k*5) return 0;
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> N >> M;
        A = B = C = D = -1;
        MX = 0;
        for (int j = 1; j <= N; j++) {
            string s;
            cin >> s;
            int num = 0;
            for (int q = 0; q < M; q++) {
                if (s[q] == '1') num++;
                rec[j][q+1] = rec[j-1][q+1] + num;
            }
        }
        int upper = min(M, N) / 3;
        while (upper * upper * 5 > rec[N][M]) upper--;
        auto isEmpty = [&](int j, int q, int k) {
            if (j + 3*k - 1 > N) return false;
            if (q + 3*k - 1 > M) return false;
            return getNum(j, q, j + k - 1, q + k - 1) == 0;
        };
        for (int j = 1; j <= N; j++) {
            if (j + 3 * (MX+1) - 1 > N) break;
            if (MX == upper) break;
            for (int q = 1; q <= M; q++) {
                if (MX == upper) break;
                if (q + 3 * (MX+1) - 1 > M) break;
                int l = MX + 1, r = upper;
                if (!isEmpty(j, q, l)) continue;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (isEmpty(j, q, mid)) l = mid + 1;
                    else r = mid - 1;
                }
                int K = l - 1;
                if (K > MX && testCross(j, q, K)) {
                    MX = K;
                    A = j; B = q;
                    C = j + 3 * K - 1; D = q + 3 * K - 1;
                    q += (3*K - 1);
                }
            }
        }
        cout << A << ' ' << B << ' ' << C << ' ' << D << '\n';
    }
}

---

Google

Kickstart Round E

483名，意外接到了通过邮件，提交了申请

2019.10.25 视频一面

---

依图

2019.09.12 onsite

第一轮

写了两道题

33. Search in rotaed

15. 3 Sum

第二轮

问项目

快速阶乘

第三轮

一个大佬聊，问系统设计，不会做；翻转硬币智力题

HR

一周大概工作80小时，依图加班确实多

---

Bigo

2019.09.15 笔试

随便做了下，笔试编程题不是OJ而是简答形式，很奇怪

2019.09.20 面试

一共三面，每面都接近一个小时，很累

第一面就读写锁设计问了几道题，之后写了些代码

几面都感觉面试官很敷衍

2019.09.24 Offer Call

---

拼多多

2019.09.25 笔试

1. 乘法求和

N个数，从其中找M对数，求每对数乘积之和的最小值

先排序，然后取前2M个数首尾相乘再相加即可

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> nums(100010, 0);
int N, M;
int main() {
    scanf("%d%d", &N, &M);
    for (int i = 0; i < N; i++) {
        scanf("%d", &(nums[i]));
    }
    sort(nums.begin(), nums.begin() + N);
    long long res = 0;
    for (int i = 0; i < M; i++)
        res += nums[i] * nums[2 * M - 1 - i];
    printf("%lld\n", res);
}

2. 线段树

N个位置可以植树，编号为1到N，每个人植从Li到Ri的区间，每个人植完树后问现在有多少棵树

线段树解决即可

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;

int TreeN, N, M;
vector<int> tree;

void update(int rank, int left, int right, int L, int R) {
    if (right < L || left > R) return;
    if (tree[rank] == right - left + 1) return;
    if (left >= L && right <= R) {
        if (tree[rank] != right - left + 1) {
            int delta = right - left + 1 - tree[rank];
            tree[rank] = right - left + 1;
            while (rank != 1) {
                rank /= 2;
                tree[rank] += delta;
            }
        }
    } else {
        int mid = (left + right) / 2;
        update(rank * 2, left, mid, L, R);
        update(rank * 2 + 1, mid + 1, right, L, R);
    }
}

int main() {
    scanf("%d%d", &N, &M);
    TreeN = 1;
    while (TreeN < N) TreeN *= 2;
    tree.assign(2 * TreeN, 0);
    for (int i = 0; i < M; i++) {
        int L, R;
        scanf("%d%d", &L, &R);
        update(1, 1, TreeN, L, R);
        printf("%d\n", tree[1]);
    }
}

3. 字典序字符串

N个a，M个b，求由这些字母字典序第K个字符串

比如2个a，1个b，字典序如下

a
aa
aab
ab
aba
b
ba
baa

想拿中介数来做，没思路

其实可以这样做，每次判断当前位置放a后的所有可能性和K哪个大，如果K大说明这个位置应该放b，否则就放a

x个a和y个b的所有可能可以事先打表获得

4. 排列种类

N个位置，每个位置有0-3四种操作，要求相邻位置操作不同，固定一些位置必须是某种操作，求所有可能的操作数

对固定位置排序，然后逐个计算区间，等比数列求和即可

很蠢的是这里做题时直接写了除法，其实应该用费马小定律，写Pow(n, MOD-2)的

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int T;
long long N, M;
long long MOD = 1000000007;
long long Pow(long long a, long long b) {
    if (a == 0) return 1;
    long long result = 1;
    while (b) {
        if (b & 1) result = result * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return result;
}
vector<pair<long long int, int>> weekend;
int main() {
    weekend.assign(1100, {0, 0});
    scanf("%d", &T);
    for (int caseRank = 0; caseRank < T; caseRank++) {
        scanf("%lld%lld", &N, &M);
        long long result;
        if (M == 0) {
            result = 4 * Pow(3, N - 1) % MOD;
        } else {
            bool flag = true;
            for (int i = 0; i < M; i++) {
                long long int t;
                scanf("%lld", &t);
                weekend[i].first = t;
            }
            for (int i = 0; i < M; i++) {
                int t;
                scanf("%d", &t);
                weekend[i].second = t;
            }
            sort(weekend.begin(), weekend.begin() + M);
            result = Pow(3, weekend[0].first - 1);
            for (int i = 0; i < M - 1; i++) {
                long long int delta = weekend[i + 1].first - weekend[i].first;
                if (delta == 1) {
                    if (weekend[i + 1].second == weekend[i].second) {
                        result = 0;
                        flag = false;
                        break;
                    } else
                        continue;
                }
                long long int start = 0;
                delta--;
                if (weekend[i + 1].second == weekend[i].second) {
                    if (delta % 2 == 0) start = 3;
                    else start = 0;
                } else {
                    if (delta % 2 == 0) start = 2;
                    else start = 1;
                }
                long long int rank = 0;
                if (delta % 2 == 0) rank = (delta - 2) / 2;
                else rank = (delta - 1) / 2;
                long long int bei = (delta % 2 == 0) ? 18 : 6;
                long long sub = (Pow(9, rank) - 1) * Pow(8, MOD - 2) % MOD;
                sub = (sub * bei % MOD + start) % MOD;
                long long ori = Pow(3, delta) - sub;
                result = result * ori % MOD;
            }
            if (flag && weekend[M-1].first < N) {
                result = result * Pow(3, N-weekend[M-1].first) % MOD;
            }
        }
        result %= MOD;
        printf("%lld\n", result);
    }
}

2019.10.24 视频一面

问了很多数据库问题，最后写了一道单向链表k组翻转，回来后编译了一下发现还写错了

---

华为

2019.09.25 笔试

1. BIT

若干个位置，每个位置一个值，两种操作，一个是将位置A的值增加B，一个是求[L, R]区间的平均值

BIT即可

#include <cstdio>

int BIT[30010];
int N, M;

void update(int index, int val) {
    int i = index;
    for (int i = index; i <= N; i += i&-i)
        BIT[i] += val;
}

int query(int index) {
    int result = 0;
    for (int i = index; i > 0; i -= i&-i)
        result += BIT[i];
    return result;
}

int main() {
    scanf("%d%d\n", &N, &M);
    for (int i = 0; i < N; i++) {
        int num;
        scanf("%d\n", &num);
        update(i + 1, num);
    }
    for (int i = 0; i < M; i++) {
        char c;
        int A, B;
        scanf("%c%d%d\n", &c, &A, &B);
        if (c == 'U') update(A, B);
        else printf("%d\n", (query(B) - query(A-1)) / (B-A+1));
    }
}

2. 字符串替换

将字符串A中的敏感元素替换为字符串B，最多出现一次

find加替换即可

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    if (s1.find(s2) != s1.npos) {
        int num = s1.find(s2);
        cout << s1.substr(0, num) + string(s2.size(), '*') + s1.substr(num + s2.size()) << '\n';
    } else
        cout << s1 << '\n';
}

3. BIT

训练N天，每次失误[0, 100000]次，每次训练后，前面每有一天失误数小于这天的，状态值加1，大于这天，状态值减1，求过程中最大状态和最终状态

BIT即可

#include <cstdio>
#include <string>
using namespace std;

int BIT[100010];
int N, M, T;

void update(int index, int val) {
    int i = index;
    for (int i = index; i <= 100000; i += i&-i)
        BIT[i] += val;
}

int query(int index) {
    int result = 0;
    for (int i = index; i > 0; i -= i&-i)
        result += BIT[i];
    return result;
}

int main() {
    scanf("%d", &T);
    for (int caseRank = 0; caseRank < T; caseRank++) {
        memset(BIT, 0, sizeof(BIT));
        scanf("%d", &N);
        int mx = 0, state = 0;
        for (int i = 1; i <= N; i++) {
            int num;
            scanf("%d", &num);
            update(num, 1);
            state = state + query(num-1) - (query(100000) - query(num));
            mx = max(mx, state);
        }
        printf("%d %d\n", mx, state);
    }
}

---

Hulu

2019.10.11 视频一面

问了一道题，从1到N，求连续两个数因子数相同的个数，例如14和15，各有4个因子，(14, 15)就是一对

• 14: 1, 2, 7, 14
• 15: 1, 3, 5, 15

原题 Euler Project 179

当时想的是拿质数分解来做，写的很复杂，也没有跑对，实际遍历较小因子，每次将因数个数加2即可

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> factors(N + 1, 0);
    for (int i = 1; i * i <= N; i++) {
        factors[i * i]++;
        for (int j = i * i + i; j <= N; j += i) factors[j] += 2;
    }
    int res = 0;
    for (int i = 2; i < N; i++)
        if (factors[i] == factors[i + 1]) res++;
    cout << res << '\n';
}

2019.10.25 onsite