1/11 MTV SETI Onsite,三轮跪经

原帖地址:一亩三分地

1/11 MTV SETI加面三轮Onsite。已跪。之前11/23面的SWE,面挂了。HR问我调剂SETI要不要,我说要,于是1/11来MTV二进宫,三场面试。1/14送HC,当天下午通知跪了。
这里吐槽一句,谷歌HR的反馈就是个P。
面SWE的时候,HC给的反馈说是简单题做得好,难题做得不好,觉得我比较适合做测试去。尼玛,SETI的HC的反馈是,数据结构,算法都是Positive Sign,但是这个职位要的是测试,
你的测试能力不够,HC的建议是,你还是适合SWE。敢情能再不靠谱点吗?编理由的时候能看看之前反馈吗?你们两波HC敢换一下吗?是不是我就有两个Offer了???

第一场,烙印
说有N个File,N很大,每个File有很多int。你有很多Machine。
现在给你一个API int sum(int fileId, int machineId)。这个的意思是你令machineId这台机器,去计算fileId的Sum。
现在让你Implement int sumAll(int[] fileIds)。

我一开始,这个还不简单吗?你想我做甚。他说想多线程。我说Ok,每个线程都计算一个File的Sum,计算完了再一起算加和。
于是除了第一版
class Worker extends Thread {

private int fileId;
private int index;
private int[] sums;

public Worker(int fileId, int index, int[] sums) {
this.fileId = fileId;
this.index = index;
this.sums = sums;
}

public void run() {

while (true) {
try {
sums[index] = sum(fileId, nextAvailableMachine());
break;
} catch (RemoteException ex) {
// Log something
} catch (FileNotFoundException ex) {
// Log
System.exit(-1);
} catch (Exception ex) {
// Log
System.exit(-1);
}

}

}
}

class Controller {

private int[] sums;

public int sumAll(int[] fileIds) {
int len;
if (fileds == null || (len = filedIds.length) <= 0) { return 0; } sums = new int[len]; Worker[] workers = new Worker[len]; for (int i = 0; i < len; i++) { workers[i] = new Worker(fileIds[i], i, sums); workers[i].start(); } for (int i = 0; i < len; i++) { workers[i].join(); } int result = 0; for (int i = 0; i < len; i++) { result += sums[i]; } return result; } } 第一版写完了,但是中间讨论了很多问题。 1. int返回值又问题,因为File里面有很多,所以得返回BigInteger类型。否则会Overflow 2. 面试官使劲让我想到底sum这个API会报多少错误,我能想到的有机器当掉,网络当掉,文件没找着,文件有Concurrency Issue。他一直在试图激发我能回答多少。 3. 万一这串文件里有些文件特别小,有些特别大,那么整个进程受到大文件拖累。 4. 一个CPU开很多Thread,CPU负载过高,要爆的。 5. 整个网络Down掉的话,这个程序就停不掉了。 针对上面的问题又写了/改了很多代码。 1. int的返回值都用BigInteger 2. 差不多就这样 3. 把一个文件,拆成几份,放到多台机器之行 4. 设置一个阀值,最多开K个Thread,然后用Queue来存储,来开Thread。 5. 在Worker Thread里设置阀值,重试K次,就退出。 第二场,Geek美国人 ZigZag Iterator 输入是List itrs;
因为是面SETI,所以写完就在说Test Case。有个Test Case千万别漏,就是这个itrs里面有null。。。
然后谈到了Concurrency,怎么加锁。我大概说了16个Test Case吧。

第三场,美国人
class Node {
Node left, right, parent;
}

然后给定一个Node,给出他的inorder predecessor
Node findInorderPredecrssor(Node root);
这题目卡了五分钟,各位同学可以想一下,比inorder successor难写。

然后就是Test Case。大概说了10+个种类的Test Case

接着又是经典问题,一个树太大了,一台机器放不下怎么办(你妹的,老子11/23就遇到过了。。。)。我就说用DFS拆吧,反正你做的是inorder traversal。
然后开一个Service,知道哪个Node在哪个Machine上面。
接着优化,每次你去调用远程Node时候,可以用Cache存下一部分Node,这么计算的时候就方便许多。
然后跪掉的部分来了,面试官一直试图提醒我有啥办法可以减少Network Transmission
我死活想不出来,最后答案是,你在找Remote Node时候,你直接把这个交给另外一个Machine去算,这样Node就不用传来传去了。。。
哎,这种经典问题记得背熟,祝后面的同学们好运。