一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2615|回复: 19
收起左侧

1/11 MTV SETI Onsite,三轮跪经

[复制链接] |试试Instant~ |关注本帖
yucheyang2 发表于 2016-1-15 23:13:29 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
1/11 MTV SETI加面三轮Onsite。已跪。之前11/23面的SWE,面挂了。HR问我调剂SETI要不要,我说要,于是1/11来MTV二进宫,三场面试。1/14送HC,当天下午通知跪了。
. 鍥磋鎴戜滑@1point 3 acres这里吐槽一句,谷歌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;. more info on 1point3acres.com
                this.index = index;
                this.sums = sums;
        }


        public void run() {. 1point3acres.com/bbs

                while (true) {
                        try {
                                sums[index] = sum(fileId, nextAvailableMachine());. from: 1point3acres.com/bbs
                                break;
                        } catch (RemoteException ex) {
                                // Log something
                        } catch (FileNotFoundException ex) {
                                // Log
                                System.exit(-1);.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        } catch (Exception ex) {. more info on 1point3acres.com
                                // Log
                                System.exit(-1);
                        }. visit 1point3acres.com for more.

                }

        }
}

class Controller {
        -google 1point3acres
        private int[] sums;

        public int sumAll(int[] fileIds) {
                int len;
                if (fileds == null || (len = filedIds.length) <= 0) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        return 0;. From 1point 3acres bbs
                }

                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;. Waral 鍗氬鏈夋洿澶氭枃绔,

        }

}
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一版写完了,但是中间讨论了很多问题。
1. int返回值又问题,因为File里面有很多,所以得返回BigInteger类型。否则会Overflow
2. 面试官使劲让我想到底sum这个API会报多少错误,我能想到的有机器当掉,网络当掉,文件没找着,文件有Concurrency Issue。他一直在试图激发我能回答多少。-google 1point3acres
3. 万一这串文件里有些文件特别小,有些特别大,那么整个进程受到大文件拖累。. from: 1point3acres.com/bbs
4. 一个CPU开很多Thread,CPU负载过高,要爆的。
5. 整个网络Down掉的话,这个程序就停不掉了。
. 1point 3acres 璁哄潧
针对上面的问题又写了/改了很多代码。
1. int的返回值都用BigInteger
2. 差不多就这样. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
3. 把一个文件,拆成几份,放到多台机器之行
4. 设置一个阀值,最多开K个Thread,然后用Queue来存储,来开Thread。
5. 在Worker Thread里设置阀值,重试K次,就退出。

第二场,Geek美国人
ZigZag Iterator
输入是List<Iterator> itrs;
因为是面SETI,所以写完就在说Test Case。有个Test Case千万别漏,就是这个itrs里面有null。。。
然后谈到了Concurrency,怎么加锁。我大概说了16个Test Case吧。

第三场,美国人
class Node {
        Node left, right, parent;
}. 1point 3acres 璁哄潧

然后给定一个Node,给出他的inorder predecessor. Waral 鍗氬鏈夋洿澶氭枃绔,
Node findInorderPredecrssor(Node root);.鏈枃鍘熷垱鑷1point3acres璁哄潧
这题目卡了五分钟,各位同学可以想一下,比inorder successor难写。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后就是Test Case。大概说了10+个种类的Test Case. From 1point 3acres bbs

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



评分

4

查看全部评分

本帖被以下淘专辑推荐:

epochou 发表于 2016-1-16 08:28:19 | 显示全部楼层
请问LZ第一题是不是需要一个BlockingQueue来计算sum? 直接用一个数组存global sum太大了。还有如果开线程的时候需要自己写算法用哪个machine计算吗?
回复 支持 反对

使用道具 举报

yuqi2 发表于 2016-1-16 08:39:46 | 显示全部楼层
Hello yucheyang, Don't be sad,I think you are good. I think the interview is kind of hard and lots of system level problem. I am gonna have a interview in SETI(entry level),I want to ask you does all interview of SETI  have so many system problem, are you interview the entry level? And can you give me some suggestion. Thank you.
回复 支持 反对

使用道具 举报

 楼主| yucheyang2 发表于 2016-1-16 12:48:04 | 显示全部楼层
epochou 发表于 2016-1-16 08:28. Waral 鍗氬鏈夋洿澶氭枃绔,
请问LZ第一题是不是需要一个BlockingQueue来计算sum? 直接用一个数组存global sum太大了。还有如果开线程的 ...

Sum的那个API是给定的,我自己提了一个API,getNextAvailableMachine()。什么太大了?BlockingQueue怎么用?这题很开放,面试官明着说,我想看你能答到什么程度。。。
回复 支持 反对

使用道具 举报

 楼主| yucheyang2 发表于 2016-1-16 12:48:32 | 显示全部楼层
yuqi2 发表于 2016-1-16 08:39
Hello yucheyang, Don't be sad,I think you are good. I think the interview is kind of hard and lots o ...

第一个面试官是问System的,二,三都问了一堆测试。
回复 支持 反对

使用道具 举报

epochou 发表于 2016-1-16 12:57:57 | 显示全部楼层
yucheyang2 发表于 2016-1-15 23:48
Sum的那个API是给定的,我自己提了一个API,getNextAvailableMachine()。什么太大了?BlockingQueue怎么 ...

我的想法类似producer, consumer模式,用两类threads, 一类threads 不断算出各个file的sum 存在queue里,另一个thread不断读queue里已经算好的sum然后累加。还有sum(fileId, machineId) 应该返回的也是BigInteger吧?
回复 支持 反对

使用道具 举报

epochou 发表于 2016-1-16 12:59:48 | 显示全部楼层
还有请问LZ最后一题那个经典问题在哪能看到呢?不是很明白怎么解决,感谢!
回复 支持 反对

使用道具 举报

 楼主| yucheyang2 发表于 2016-1-16 13:08:31 | 显示全部楼层
epochou 发表于 2016-1-16 12:57
我的想法类似producer, consumer模式,用两类threads, 一类threads 不断算出各个file的sum 存在queue里, ...

也有道理额。对的,都是返回BigInteger
回复 支持 反对

使用道具 举报

 楼主| yucheyang2 发表于 2016-1-16 13:08:51 | 显示全部楼层
epochou 发表于 2016-1-16 12:59. 1point 3acres 璁哄潧
还有请问LZ最后一题那个经典问题在哪能看到呢?不是很明白怎么解决,感谢!

就是一颗二叉树太大了,一台机器装不下,怎么办。
回复 支持 反对

使用道具 举报

Nero_hu 发表于 2016-1-17 02:10:13 | 显示全部楼层
LZ好伤....
PS: 我也1/11 SETI加3轮结果HR14号没送进去...cross finger等下周....
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-19 10:06:25 | 显示全部楼层
第一题是不是可以用mapreduce来解?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-19 10:20:43 | 显示全部楼层
写了下inorder predecessor. From 1point 3acres bbs
  1. public class InorderPredecessor {
  2.         static class Node {
  3.                 Node left, right, parent;
  4.                 int val;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.                 public Node(int val) {
  6.                         this.val = val;
  7.                 }. 1point 3acres 璁哄潧
  8.         }
  9.        
  10.         public static Node findInorderPredecessor(Node node) {
  11.                 if (node == null) {
  12.                         return null;
  13.                 }. From 1point 3acres bbs
  14.                 if (node.left != null) {. 1point 3acres 璁哄潧
  15.                         return findMax(node.left);
  16.                 }
  17.                 Node parent = node.parent;
  18.                 while (parent != null && node == parent.left) {
  19.                         node = parent;
  20.                         parent = node.parent;
  21.                 }
  22.                
  23.                 return parent;
  24.         }

  25.         private static Node findMax(Node node) {
  26.                 while (node.right != null) {
  27.                         node = node.right;
  28.                 }
  29.                 return node;
  30.         }
  31.        
  32.         public static void main(String[] args) {
  33.                 Node root = new Node(1);
  34.                 root.left = new Node(2);
  35.                 root.right = new Node(3);
  36.                 root.left.parent = root;
  37.                 root.right.parent = root;
  38.                 root.left.left = new Node(4);
  39.                 root.left.right = new Node(5);
  40.                 root.left.left.parent = root.left;
  41.                 root.left.right.parent = root.left;
  42.                 System.out.println(findInorderPredecessor(root.left).val);
  43.                 System.out.println(findInorderPredecessor(root.right).val);
  44.                 System.out.println(findInorderPredecessor(root.left.right).val);
  45.         }
  46. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| yucheyang2 发表于 2016-1-19 12:01:19 | 显示全部楼层
bobzhang2004 发表于 2016-1-19 10:06
第一题是不是可以用mapreduce来解?

我也是这么想的。。。但是MapReduce不会。。。
回复 支持 反对

使用道具 举报

 楼主| yucheyang2 发表于 2016-1-19 12:01:54 | 显示全部楼层
bobzhang2004 发表于 2016-1-19 10:20
写了下inorder predecessor

差不多就是这个意思,往Parent翻的时候,要去判断是左子树还是右子树
回复 支持 反对

使用道具 举报

七夜雪 发表于 2016-1-27 14:57:56 | 显示全部楼层
。。。想起老板申请funding给的4个review其中一个说实际生活的应用阐述的不够具体,另外一个说实际生活的应用阐述的太多。。。
回复 支持 反对

使用道具 举报

dgswh 发表于 2016-5-10 08:58:50 | 显示全部楼层
请教lz,seti测试方面的问题可以怎么准备呢?
回复 支持 反对

使用道具 举报

 楼主| yucheyang2 发表于 2016-5-10 21:23:40 | 显示全部楼层
dgswh 发表于 2016-5-10 08:58
请教lz,seti测试方面的问题可以怎么准备呢?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我觉得单看些测试Case不够的。。。我就是这么弄的,感觉面试官意犹未尽。。。我觉得你真的去测试你一个Project,方方面面练一遍吧
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-11 02:24:43 | 显示全部楼层
总体答的不错阿
只有最后一道
楼主因为什么跪?
回复 支持 反对

使用道具 举报

 楼主| yucheyang2 发表于 2016-5-11 02:34:37 | 显示全部楼层
tcomein2009 发表于 2016-5-11 02:24
总体答的不错阿-google 1point3acres
只有最后一道. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主因为什么跪?
-google 1point3acres
其实不然,这个SUM这么多,开这么多Thread有问题的,估计面试官想我答Map Reduce吧。HR给的反馈是扯淡,说我算法没问题,但是我们这个职位是测试。。。所以就跪了
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-11 03:33:43 | 显示全部楼层
epochou 发表于 2016-1-16 12:57
我的想法类似producer, consumer模式,用两类threads, 一类threads 不断算出各个file的sum 存在queue里, ...

好主意,而且是不是机器数量小于文件数量
那样的话放进queue的就是available machine
楼主说map reduce也是好主意
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 15:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表