2019-08-18

Summary

Google实习总结

知乎回答：https://www.zhihu.com/question/336859540/answer/761912465

我的Google账号：xiangyunding@google.com，但check out之后就不能用了。

感谢以下个人/组织：

host: wenjies，co-host: chaoyuel
recruiter：irene, rosy, yun, etc.
帮我内推的sunyq和帮我介绍内推的jzh
帮我review代码，还有其他帮助我的Googler
一起入职的小伙伴们
Dataz group
Google

申请过程

关于正式的招聘流程和最新的招聘信息，请关注：

微信公众号：Google招聘包打听
知乎：Google谷歌中国校园招聘
其他官方消息渠道

我大概的流程是这样的：

2018.12.23 在群里看到转发的招实习生的通知，就发了简历申请。
2018.12.26 收到官方邮件，填写申请表格，主要是：
- 基本信息，简历
- 期望的面试时间，我选的是寒假之后的。
2019.1.4 通过recruiter review
2019.2.26 第一轮电话面试。两道算法题，都做对了。
2019.3.7 第二轮电话面试。还是两道算法题，也都做对了。
2019.3.13 收到offer。与hr商量实习时间，还考虑到期末可能事情比较多，最后确定了5.6-8.30。因为Google的实习生要求实习天数60-70天（不能少也不能超）。
2019.5.6 入职

说实话，最开始只是随便投了一下，都没想到真的能过。几点经验总结：

一定要事先调试好设备和网络（需要用google docs）。
多与面试官交流。Google不喜欢闷着头做题的人。

Google的申请流程很正规，一步一步很清楚，不过流程也比较漫长。每周recruiter都会发邮件sync进度，有问题也可以发邮件咨询。Google对实习生招聘要求的很严格，每位FTE想招实习生，都要写一份详细的报告，实习生总数也控制的很严。今年实习生与往年相比招了很多，北京上海两个办公室一共140人左右（包括RS，SWE，ML SWE和EP）。另外Google招聘对女生很照顾，即使不算EP，感觉男女数量也差不多（假设男生女生水平一样，招聘的男女比应该与高校计算机专业的男女比一样才对，看看贵系男女比我就不好说什么了）。学校和专业虽然说不考虑，但我认识的intern还是清北居多，并且硕博比较多。

有想申请的同学请关注的官方消息。我虽然离职了应该也可以帮忙推简历的。至于实习待遇方面，可以说工资、工作环境没有其他公司能跟Google比了。具体薪资应该不让说，但可以给个参考价，比头条多不少，而且包三餐，而且发好多房补。很多人跟我一样可以住学校，房子根本没花钱，但Google就是这么大方。

实习

实习项目是WikiTrust Revamp，维基百科的恶意修改检测。因为签了保密协议，这部分就不详细讲了。只是做了一点微小的工作。据说这个project的由来是，去年特朗普发现维基百科经常被恶搞，就在twitter上@了一下Google。WikiTrust很久之前有人搞过，不过效果非常差，于是Google就安排了几个人做新的WikiTrust，他们就取了个名字叫WikiTrust Revamp，修补的意思。当然整个Dataz组做的事情就很多了。

Google作为世界顶级的软件公司，内部工具和文档、开发流程、代码质量控制都做的太成熟了，之前上软工的时候还觉得这些东西好麻烦，为什么要写单元测试，为什么要搞文档和注释，来到Google才发现这些东西是真的游泳。在Google提交每一份代码，首先都要通过g4 fix自动调整一下风格，比如每行不超过80字符，include顺序等等。然后至少两人review，包括代码逻辑、代码风格、可读性、可维护性检查，觉得不好的地方可以写comments。然后，针对每一个comments修改代码，重复上面的流程。在这之间系统会运行presubmit（包括很多静态检查、运行所有相关的单元测试等）。直到所有的reviewer都认为可以提交了，并且presubmit也通过了，这时才可以点击submit按钮，将这份代码提交到代码库里。我交的最慢的一个cl交了两个多星期，是临时找了一位美国那边的精通C++的同事review，给我提了五十多条comments，改的时候整个页面comments比code还多。注释和单元测试就更不必说了，没有这些不可能让你提交的。Google内部的工具和文档真的太全面了，比如moma、codesearch、critique、piper、cider、flume等等，而且都有十分详细的文档或codelab帮助使用。除了这些开发用的工具之外，其他用的也几乎都是Google自家的产品：查资料用Google search，邮件用gmail，浏览器用Chrome，文件用Google docs，表格用Google sheets，ppt用Google slides，开会用meetings，英文看不懂的用Google translate，有问题上moma（内部的search），发消息用hangout chat，等等。Google的基础设施真的让人很震撼。

工作环境方面，真的是太太太太太好了。一日三餐，零食水果尽情享受，还有健身房、按摩椅、乒乓球台、游戏机……还有好多我没有尝试过的。据我观察，正式员工大多9-10点到公司，下午5-6点就走，晚饭后公司就基本没人了。正式员工都是采用OKR工作法，同事之间、上下级之间交流也非常轻松愉悦。由于Google是美国企业，入职时还给我们宣传Google的价值观。印象最深的是比较注重个人隐私，然后开放自由之类的。

Intern offsite去的是这个地方：http://www.dianping.com/shop/97821752 。我个人不是很喜欢这种室内娱乐场所，不过这是大家投票决定的。午饭每人100元budget随意吃。晚餐去的这里：http://www.dianping.com/shop/69719009 ，人均270的自助。Offsite这天工资还照发，舒服。

总结

其实开始找内推的时候真的没想到能来。并且后面找工作的时候才发现，Google的实习经历真的管用，简历几乎没有被卡过（我清华同学本科无实习的简历有时就会被卡）。

TBD

2019-08-17

Algorithm

BZOJ AC代码

我之前把在BZOJ上的密码忘了，最近又找管理员要了一下。不过会员早就没了，有一些题看不了了。

我把我的账号xindubawukong的所有AC代码下载到了这里：Google Drive。html格式。有兴趣的可以看看。

UPD: online version https://xindubawukong.github.io/bzoj-ac-code/

2019-08-17

Others

Collection of Movies I Have Watched

This is a list of the movies I have watched.

总结一下。不然都忘了。按汉语拼音排序。

电影

007：大战皇家赌场（Casino Royale）

007：黑日危机（The World Is Not Enough）

007：大破量子危机（Quantum of Solace）

2012

电视剧

神探夏洛克（Sherlock）

非自然死亡（Unnatural）

行尸走肉（The Walking Dead）

持续更新中。。。

2019-08-16

Algorithm

Leetcode 1125. Smallest Sufficient Team

题目

https://leetcode.com/problems/smallest-sufficient-team/

有n个数，m个数集，要从中选出k个数集，使得这k个集合的并集包含这n个数。求最小的k。

n <= 16, m <= 60

做法

状态压缩动态规划。设f[S]表示包含集合S中的数的最少集合数。枚举S的每一个子集A，那么f[S] = min(f[A] + f[S - A])。通过给定的m个集合初始化即可。代码如下：

class Solution {
public:
    
    int n;
    
    void getans(const vector<int>& from, const vector<int>& go, int S, vector<int>* ans) {
        if (S == 0) return;
        if (go[S] != -1) {
            ans->push_back(go[S]);
            return;
        }
        int subset = from[S];
        if (subset == 0 || subset == S) return;
        getans(from, go, subset, ans);
        getans(from, go, S ^ subset, ans);
    }
    
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        n = req_skills.size();
        vector<int> f(1 << n);
        vector<int> go(1 << n);
        f[0] = 0;
        for (int i = 1; i < f.size(); i++) {
            f[i] = 1e8;
        }
        for (int i = 0; i < go.size(); i++) {
            go[i] = -1;
        }
        for (int i = 0; i < people.size(); i++) {
            int S = 0;
            for (const string& skill : people[i]) {
                for (int k = 0; k < req_skills.size(); k++) {
                    if (req_skills[k] == skill) {
                        S |= 1 << k;
                        break;
                    }
                }
            }
            // 枚举S的子集
            for (int subset = S; subset > 0; subset = (subset - 1) & S) {
                f[subset] = 1;
                go[subset] = i;
            }
        }
        vector<int> from(1 << n);
        for (int S = 0; S < f.size(); S++) {
            for (int subset = S; subset > 0; subset = (subset - 1) & S) {
                int num = f[subset] + f[S ^ subset];
                if (num < f[S]) {
                    f[S] = num;
                    from[S] = subset;
                }
            }
        }
        vector<int> ans;
        getans(from, go, (1 << n) - 1, &ans);
        sort(ans.begin(), ans.end());
        return ans;
    }
};

下面分析时间复杂度。显然我们枚举了n个数的所有子集的所有子集。包含k个数的子集有$C_n^k$个，他们子集都分别有$2^k$个。因此时间复杂度为：
$$\sum_{k=0}^{n}C_n^k\times2^k=C_n^0\times2^0+C_n^1\times2^1+C_n^2\times2^2+…+C_n^n\times2^n$$
高中时学过杨辉三角，可以知道上面这个式子就是$(2+1)^n$的展开式。因此总时间复杂度O($3^n$)，$3^{16}=43046721$，四千多万，可以通过。

2019-08-15

Algorithm

Leetcode 1147. Longest Chunked Palindrome Decomposition

题目

https://leetcode.com/problems/longest-chunked-palindrome-decomposition/

给一个字符串，要求将其分割成a1, a2…ak，每一份长度>0，并且a[i] = a[k + 1 - i]。例如”ghiabcdefhelloadamhelloabcdefghi”可以分割为”(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)”。求最大的k。字符串长度<=1000。

做法

本来看n<=1000觉得是O($n^2$)的做法，枚举中间一块的长度，然后从中间向两边贪心，判断字符串相等使用hash。后来发现，直接从两边往中间贪心就行了。。连hash都不用，直接暴力判断。这也是hard题。。

class Solution {
public:
    int longestDecomposition(string text) {
        int n = text.length();
        int ans = 0;
        int l = 0, r = 0;
        while (r * 2 + 1 < n) {
            if (text.substr(l, r - l + 1) == text.substr(n - r - 1, r - l + 1)) {
                ans += 2;
                l = r + 1;
                r = l;
                continue;
            }
            r++;
        }
        if (n % 2 == 0 && l == n / 2) return ans;
        return ans + 1;
    }
};

2019-08-14

Algorithm

Leetcode 1157. Online Majority Element In Subarray

题目

https://leetcode.com/problems/online-majority-element-in-subarray/

给定一个长度为n的数组，m次查询，每次查询[l, r]区间内出现次数>=threshold的数是哪个。保证 threshold * 2 > r - l + 1 。强制在线。n, m <= 20000。

做法

暴力做法：对于每个query，扫描l到r区间中的数，用hash表存下每个数的出现次数。时间复杂度O(n*m)。

这个题中要求的数是majority，也就是出现次数大于总次数的一半。这是一个很强的限制。我们可以发现，暴力算法处理慢的地方在于区间较长的时候，也就是threshold较大的时候。而threshold较大时，满足条件的数的个数就会很少！

于是可以取$\sqrt{n}$作为阈值，分两种情况讨论：

若threshold<$\sqrt{n}$，则区间长度<$2\sqrt{n}$，按照暴力做法求解，每次询问时间复杂度O($\sqrt{n}$)。
若threshold>$\sqrt{n}$，满足这样条件的数不超过$\frac{n}{\sqrt{n}}=\sqrt{n}$个。因此在开始时进行预处理，求出这$\sqrt{n}$个数，那么只需要在查询时知道每一个数在[l, r]中出现了多少次。我的方法是对每个数维护一个长度为n的前缀和数组，这样O(1)的时间即可得到其在[l, r]中的出现次数，每次询问的时间复杂度为O($\sqrt{n}$)。

总时间复杂度O($n\sqrt{n}$)。代码如下：

class MajorityChecker {
public:
    
    vector<int> arr;
    vector<int> frequent;
    vector<vector<int>> sum;
    
    MajorityChecker(vector<int>& arr) {
        this->arr = arr;
        map<int, int> count;
        for (int x : arr) {
            count[x]++;
        }
        for (auto it = count.begin(); it != count.end(); it++) {
            if (it->second > 100) {
                frequent.push_back(it->first);
            }
        }
        sum.resize(frequent.size());
        for (int i = 0; i < frequent.size(); i++) {
            int x = frequent[i];
            sum[i].resize(arr.size());
            for (int j = 0; j < arr.size(); j++) {
                if (x == arr[j]) {
                    sum[i][j] = 1;
                }
                if (j > 0) {
                    sum[i][j] += sum[i][j-1];
                }
            }
        }
    }
    
    int work1(int left, int right, int threshold) {
        unordered_map<int, int> count;
        for (int i = left; i <= right; i++) {
            if (++count[arr[i]] >= threshold) {
                return arr[i];
            }
        }
        return -1;
    }
    
    int work2(int left, int right, int threshold) {
        for (int i = 0; i < frequent.size(); i++) {
            int cnt = sum[i][right] - (left == 0 ? 0 : sum[i][left - 1]);
            if (cnt >= threshold) {
                return frequent[i];
            }
        }
        return -1;
    }
    
    int query(int left, int right, int threshold) {
        if (threshold <= 100) {
            return work1(left, right, threshold);
        }
        else {
            return work2(left, right, threshold);
        }
    }
};

在Google被人逼着养成了良好的代码风格，好处就是代码比较容易看懂，坏处就是写的过程非常痛苦。

其他人的做法

交了之后看了一下discuss（这个题暂时还没有solution），发现有些人用线段树做的。这种做法基于摩尔投票算法。这个算法专门用来求数组中的majority，也就是出现次数大于一半的数。伪代码如下：

Initialize an element m and a counter i with i = 0
For each element x of the input sequence:
    If i = 0, then assign m = x and i = 1
    else if m = x, then assign i = i + 1
    else assign i = i − 1
Return m

看完大概就能明白，这个算法只能做找majority这么一件事情，并且如果没有majority它也会返回一个值，需要再check一下结果是不是majority。

这个题正好是要找majority。不过，我没怎么想清楚他们是怎么用线段树维护这个东西的。他们的代码写的我觉得有点问题，但是竟然能过。这种方法的时间复杂度是O($n\log_{2}^{2}{n}$)，实际跑起来比我的做法还要慢一些。

2019-08-14

Technology

换机Huawei nova 5 Pro

今天买了一部新的华为nova 5 pro，换掉了用了三年的iphone 6s plus。

搭梯子

拿到手机后，先把不需要的能卸载的app全都卸载，华为助手之类的全部禁用。然后开始搭梯子。我用的是自己配的shadowsocks，可以到 https://github.com/shadowsocks/shadowsocks-android 下载。shadowsocks服务器端搭建方法可参考 https://www.cnblogs.com/iStu/p/9992535.html 。服务器是之前在 https://www.hostwinds.com/ 租的。配置好后确保能通过浏览器访问Google即可。

安装谷歌服务框架

国产Android手机上默认都不会预装谷歌服务框架。对于现在还在Google实习的我来说没有Google怎么行呢。安装谷歌服务框架可以参考：https://www.zhihu.com/question/333903896/answer/761587221

下载谷歌服务助手之后，一步一步安装即可。这样就安装了谷歌服务框架和Google Play Store。然后就可以在Play Store里下载想要的应用了。如果不小心把Play Store删了也没事，照上面的步骤再来一遍就行了。

有一些Google应用不能通过国区的Play Store账号下载，比如Google Drive，Google Docs等。可以参考 https://www.zhihu.com/question/21999528/answer/447913645 切换地区。

后续

后面装sim卡，恢复微信备份之类的就没必要写了。恢复备份需要电脑和手机连同一wifi，但是不知为什么我连公司的GoogleGuestPSK不行，最后用原来的手机开了个热点才备份好的。全面屏真的爽。而且还支持快充，3000块钱也值了。iphone留着当备用机了。

2019-08-13

Technology

Build Blog on Github Pages with Hexo

Blog Repository

https://github.com/xindubawukong/xindubawukong.github.io

This repo only contains static html files. The comments function of the blog is based on the issues of this repo.

References

https://pages.github.com/

https://hexo.io/

https://zhuanlan.zhihu.com/p/26625249

http://menuet.xyz/technology/tool/Hexo%E9%97%AE%E9%A2%98%E6%80%BB%E7%BB%93/

主题：https://github.com/wayou/hexo-theme-gstyle

图床：https://postimages.org/

markdown公式渲染：https://zhuanlan.zhihu.com/p/36302775

评论功能：https://github.com/utterance/utterances

每页显示个数设置：http://www.yuzhewo.com/2015/11/21/Hexo%E7%A8%8B%E5%BA%8Farchive%E9%A1%B5%E9%9D%A2%E6%95%B0%E9%87%8F%E8%AE%BE%E7%BD%AE/

2000-01-01

Hello World

大家好！测试图片：

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment

申请过程

实习

总结

电影

A

B

C

D

F

G

H

J

K

L

M

N

P

Q

R

S

T

V

W

X

Y

Z

电视剧

题目

做法

题目

做法

题目

做法

其他人的做法

搭梯子

安装谷歌服务框架

后续

Blog Repository

References

Quick Start

Create a new post

Run server

Generate static files

Deploy to remote sites