google 电面  2014/9.15

问项目+两道算法题

#include<iostream>
#include <math.h>
using namespace std;
int cal(int n, int m){
	int x = n+m;
	int t = pow(-1, x);  // top down , or bottom up
	int y = t == 1? n+1 : m+1; //  
	y += (1 + x)*x/2; // E {1 2 3 ... x}
	return y;
}
int main(){
	cout<< cal(2, 0) << ":"<< cal(0, 0)<<endl;
	return 0;
}

#include<iostream>
#include <math.h>
#include<iomanip>
using namespace std;
#include <string.h>
#include <vector>
struct TreeNode{
	TreeNode *child; //first child
	TreeNode *sib; //sibling
	int val;
	TreeNode (int x):child(NULL),sib(NULL),val(x){}
};
TreeNode *dfs(const vector<vector<int> > &graph, vector<bool> &visit, int idx){
	TreeNode * root = new TreeNode(idx+1), *lc;
	visit[idx] = true;
	for(int i=0; i<graph[idx].size(); i++){
		int v = graph[idx][i];
		if(visit[v]) continue; // 有环
		if(!root->child) { root -> child = lc = dfs(graph, visit, v); }
		else { lc -> sib = dfs(graph, visit, v); lc = lc->sib; }
	}
	return root;
}
void dfs(TreeNode *root){
	if(!root) return;
	cout<<root->val<<endl;
	TreeNode *child = root->child;
	while(child){
		dfs(child);
		child = child -> sib;
	}
}

int main(){
	int n; cin>>n;
	vector<vector<int> > graph(n, vector<int> ());
	for(int i=0; i<n; i++){
		int m; cin>>m;
		for(int j=0; j<m; j++){
			int a; cin>>a; a--;	
			graph[i].push_back(a);
		}
	}
	vector<bool> visit(n, false);
	vector<TreeNode *> nodes;
	for(int i=0; i<n; i++){
		if(!visit[i]) 
			nodes.push_back(dfs(graph, visit, i)), dfs(nodes[nodes.size()-1]);
	}
	return 0;
}

Google 2014 面试

电面 1    两星半

对于其他数n > ns， 这几个子数在原来子数序列<2
3 4 .. m>基础上把右边的数移动： 如 10 =》 2 × 3 × 5， 11 =》 2 × 4 × 5 ， n = ns + （m-1)*k + t => (2 + k) × (3 + k) ... × (m-t+k)
    ×  （m-t+k)+1 × ... （m + k） + 1 

所以匆忙写了个程序，显然此时脑袋全蒙的情况下，题目对应的场景依旧理解不完全，所以写代码不够镇定，所以磕磕碰碰的写了一个鬼东西。现在想想，应该怎么写最简洁准确呢。

第二问，在原题基础上，这几个子数可以相等，求乘积最大

依旧很蒙，心想为什么还是出这种数字游戏题？

面试官看我没思路，于是让枚举几个，像上面一样找规律。发现：

对于任意数n，分解成子数序列都是由2、3构成。 另外优先考虑3。 诸如 6 =》 3 × 3。

虽然还没考虑明白为什么会这样，但面官让写代码。

赶紧写，这个地方竟然脑袋犯晕，转在这个坑上面： 

一个数分解成多个2和3， 那分解方案不唯一了， 怎么挑出分解到的3最多的那一个方案呢。脑袋完全不转；一片空白，感觉没有找到任何可靠论据来解决这个问题。当时我就懵逼了。

然后面试官又开始提示了， 试试讨论 n % 3 不同情形。 几乎是手把手的，我写完了 三个 if-else。 心都碎了。哥 不是这水平啊。

事后反思，第二题其实比第一题实现简单得多。原理也简单得多： 

考虑 n = k*m, 当 m^(n/m) 最大的时候， m=e 。因为 e 在 (2, 3) 区间上， 所以m取整数就只能是 2或3了。这就是为什么子数序列由2、3构成。

电面2    四星半

第一次电面很不理想。所以又加了一轮。

1 给一个图，找出连通分支个数。 

直接 for vertex i:  if(!visited[i]) dfs(i)

2 给一个表，每一列很多不同类型数据，问怎么对表中每一行进行指定列优先级排序。

我说每一行数据给字符串化，中间用分隔符分割一下什么的。数字的话前面补0补成定长。

然后对所有串进行字典序排序就行了。

3 记不得了

这一轮总算扳回了一城。

onsite 1  三星

上来一个华裔的guy，我想看起来蛮亲切，就跟他面试以外各种鬼扯。没想到还是栽在这里了？

1 给一串数字，找到一个点，左边序列和，右边序列和相等。

这线型扫两遍就行了，第一次记录总序列和， 第二次记录左边序列和， 到一半就ok。 也许我的解法还有可以优化的地方？

2 给一个蛇形矩阵N×N，让给出访问序列。

妈蛋，第一遍写完我说好了，他说sure？我看了下，发现有个地方没写好，貌似for循环起始点搞错了，有数组越界。然后改了下。

他又问有没错，我再看，又修正了一处bug。

anyway， 面完我想今天题目真简单。时间刚过了半小时。然后两人鬼扯了一下。 事后证明一定是这里出了问题。 简单题目也应该现场0 bug一气呵成。最后拍板的代码更不应该有bug。

onsite 2   四星半

上来一个加拿大的guy，紧张坏了，前一晚练了半天的自我介绍终于派上了用场。赶紧做了个自我介绍，还连夸他handsome，对方很开心的thx。

1 2sum

我说左右指针往中间跑。他问为什么可以work，我英语鬼扯了一番，写了代码，他说很好。

2 leetcode原题： 找一个点，左边连续递增，右边连续递增

我一上来说线型扫描。他说这是好方法，有没有更好的。我迟疑了几十秒。拍了下脑袋，原来是二分查找。

于是他问怎么二分查，我就用英语和粉笔跟他磕磕巴巴地解释着，画着。他连连点头，于是让我写。

好歹这道题我也是研究过的，噼里啪啦一顿敲，敲完给他。我知道这个题目有个坑，主要是因为递增序列中可能有相邻相等的点。当二分点是这种点的时候，我每次向右挪动一位就O了。保证没bug。他在脑袋里run了几个测试样例，赞许地说，这道题还很少有人现场写出来，这么简洁还貌似bug free的。

3 问有很多的文件，存在不同电脑的不同目录下，怎么找到他们并去重。

这是分布式海量数据处理的题目，我想了想，能不能用boosting做。他就让我说boosting原理，我解释了半天，怎么建bit map， 每一个内容入表的时候怎么用多个hash来置相应bit map点，以及如何从bit map中查找某个内容是否已经存在。他说很好，但是boosting是否是完全可靠的呢。我说不是，它的召回率准确率什么的。英语悲剧，好在人说英语不是问题，中国人发音老外能听懂。可是我听不太懂他说的，只能边说边画。最后结论是，boosting的情况下，判定出的不重复文件是一定不重复的。但判定的重复文件却也也可能是不重复的。因为存在hash碰撞。

   然后他问怎么办，我扯了一堆 md5加密算法，说这个hash算法的碰撞几乎很难出现。对每个文件生成md5字符串，然后对这些字符串再进行hash判重。他说这个是有效的。然后他称赞hash是很好的思路，hash是解决海量数据必不可少的神器云云。

在此之前我根据boosting临时开了个脑洞，说多次hash，一开始想分别存放这些hash，比较这些hash值；后来又想hash值连接起来。他也被我带到沟里去了，耐心地看我画各种奇怪的图，持续了半天， 汗 @ @。

onsite 3   四星半

过了一周，说准备最后一轮。当时临近腊月，我在北京的旅社里饥寒交迫，正要卷铺盖回家了，听到这消息有点郁闷又有点欢喜。毕竟知道上一轮面的还不错，应该有这一轮。郁闷的是gmail老是被各种墙，延迟了三天才知道最后一轮面试的通知。由于晚收到通知，这一周的档期都排满了，只能等下一周。可是我实在一秒也不想继续呆在那个旅社。其间续了5次费，因为担心又希望他把下一轮安排在年内。总之是无比矛盾。

终于到了下一周，在旅社里等待了12天之后，我再一次整装去清华园。第一天晚上没休息好，第二天上午又临阵磨了会儿枪，脑补了各种可能的题型和场景。下午坐车过去的时候当时那是无比的困。hr送了一杯咖啡，并道歉她来晚了，让我等了一刻钟。我啧了一小口。

第一个面官是谷歌北京这边的，人还nice，很实在那种，看了我简历说知识面已经很全面了，应该没问题，问我为什么一直低着头貌似不自信。我说因为我好困，眼睛都睁不开了。囧。。。。早知道不低头了。不过当时确实有点胆怯，因为几天没洗头洗澡（万恶的旅社。

1 给一个数，怎么分解成最少的几个素数的乘积。

当时我给了几种方案。比如贪心，然后挠头说这个貌似不是最优解。于是想了个dp查表记忆化搜索什么的，他说算下时间，我说O（n^2), 不过可以解决1000以内的解。 他说n很大怎么办，于是我又硬着头皮给了个dfs暴力深搜。在他的旁敲侧击之后，我一拍脑袋，可以深搜基础上剪枝，具体为用贪心结果来制约dfs搜索深度。当时好开心，这个题“有点trick”，竟然找到了state of art解决方案。然后让我写，我就写了个greedy，写了个dfs，里面加了个最大深度的判定更新和返回，给了个main函数表明怎么调用。他微微赞赏地说，恩不错，思路挺清晰的，然后问有没有办法继续优化。我又一想，这样dfs每次得到的数字序列可能组合相同而顺序不同，于是在dfs上加了一个参数
（dfs(vector<?>&tmp, int & mDep, int lastE) ) ，限定dfs里的for循环从lastE开始枚举，保证得到的数字序列顺序递增。他说这样可以，还有没有优化方案。我说对了，可以用dp查表，记录n很小的时候的解，这样当n被分解到很小的时候直接查表得到解，不用每次都算。他说这样也可以，还有没有。。。我说这应该是最优的了，因为有查表记录[1~1000],当什么情况下查表就能优化，所以没必要再用别的优化。

他说这题到这里，还有问题吗。我很诧异，这一面就一道题吗？他说你还想要几道题。我说意犹未尽啊。他说看你一开始低头好像不自信，不过你的简历上挺全面的了，应该自信些。像一个学长一样教导我，唉，于是有了最上面的对话。

onsite 4   四星

最后一个面官也是北京这边的。想起上一轮，两个都是美国那边出差过来面试的人，他们面的题目是那种看起来简单，但是容易疑惑或犯错的。这一轮，中国这边员工给出的面试题目则似乎更容易给人找到直觉，定位到解决方法。也许还是语言习惯或思维方式的问题。

前面两题好像比较简单。没印象了。

3 给一个序列，A1.... An, 计算B1....Bn，使得Bk为Ak之后第一个比他小的元素。

其实是用栈的题目。但因为跟面官很亲和，我也就放开了，问他这样对吗，那样呢。一开始我还是说好像可以线型扫描，他说怎么扫，我扫了下发现不对。然后他说观察下规律，于是我终于想到用stack<pair<A, k> >,每次进Ak的时候出去所有比他大的元素As并且更新相应Bs = Ak. 这么简单，但我当时直觉在这里迟钝了一下。可能还是太困，加上前面一轮耗费了不少脑力。

于是这一轮到这里了，我又膜拜了下面官，面官开心的说期待好运云云。过程就跟和陌生师兄寒暄一样。

HC   三星（半星加给诚实，一星减自诚实，半星减自推荐，最后由80变为60）

回家没多久，说恭喜面试通过了，进入Hiring Cometee， 然后忙绿地找人推荐写feedback，找成绩单。可惜呀可惜，成绩单难看，推荐人比较陌生、写的太客气不够生动，第一轮电面和第一轮onsite的少许负面声音 等种种元素导致最终遗憾败北。

当然，整体上公司还是很肯定我的。只是说算法和coding还可以进一步提升。确实，毕竟我跟最一流的高手还是有差距的，这种差距可以是秒杀简单题上的从容（第一轮onsite），可以是没见过的难题上的不慌不忙（第一轮电面），可以是应对第一次/轮时的表现出的先知一样的娴熟。

然而，我终究还是去了另外一家公司，开启了一段截然不同的征程。