Google 11/30 onsite 面经

11月30号面的，这周三通知过了HC进入final stage of offer review precess发个面经攒点人品，求offer！！

round 1：
ABC小哥 题目是：给你一大堆文件，每个文件里面是排序好的数，一行只有一个数字，文件可能很大，内存装不下。要求把所有文件里的数字排序好放到一个输出文件里面。
我看到题目第一反应是用[size=15.008px]External sorting和小哥交流后发现有问题。然后就讨论如何读取文件里的数字，感觉小哥在这里给我提示，每次读取一行，我最后用priority queue。
[size=15.008px]写完后，小哥说我的程序可以优化，讨论好好久才优化完。
[size=15.008px]

[size=15.008px]round 2：
[size=15.008px]白人小哥 题目是：给你一棵树的root节点，还有一个函数boolean shouldRemove(Node node) 返回是否需要删除这个节点。 要求输出一个list<Node>，list是删除所有节点后原来的树分裂成的子树的集合。
[size=15.008px]和白人小哥讲述了递归的思路，然后写了代码。写完口头跑了几个test case 被指出一个大bug，然后修改掉。 小哥说还有十几分钟但时间已经不够再出一道题了，就开始聊天扯淡，问了小哥很多关于Google new grade的事情，小哥都很耐心的解答了。
[size=15.008px]

[size=15.008px]lunch：

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
f">[size=15.008px]第二问刚拿到题目很是懵逼，无从下手，就和小哥讨论，写了超多的例子，期间小哥也一直在说，我也一直在说我的想法，后来得出了一个结论，然后写了代码。写完发现已经面了一个小时了..然后小哥就把我送走了，离开前还说了句good luck，当时感觉要崩。 第二问可能题目理解的不太到位，一直没get到小哥要的点，但最后小哥好像理解了我的一些错误想法..然后在各种提示下终于写出了代码，自己太渣，现在已经忘记当时是怎么写的了..隐约记得是调用第一问的函数，测试当前这个词和之前所有猜过得词之间的different然后与之前的反馈比较，好像是需要反馈相同。
[size=15.008px]

[size=15.008px]面完感觉自己运气特别好，总体题目难度不大，没碰到三哥，碰到了好多亚洲面孔，第二轮的白人小哥也特别友好。从7月份开始准备找工作，也面了几家了，希望这次有个好结果，求人品，求过，求offer！


补充内容 (2017-1-3 02:20):
12月27号收到offer！ 谢谢大家

天天甜甜去美国 发表于 2017-4-28 06:30
哇塞我才看到你这个帖子！你这么早就拿了google的offer！！！膜拜！

运气运气

freemail165 发表于 2016-12-18 21:43
第一题是不是这样

public List remove(Node root) {

你的这个解法是preorder traversal, 需要把parent node传进来。可以用postorder traversal, 代码简洁些。让这个helper method返回当前处理的这个node是否会被删除，这样在方法里面，可以处理current node和children的关系了。

第一题是不是这样

public List<Node> remove(Node root) {
   List<Node> result=new ArrayList<>();
   helper(null,root,result);
   return result;
}

public void helper(Node parent,Node cur,List<Node> result) {
     if(cur==null) return;
     if(shouldRemove(cur)) {
             if(parent!=null) {
                      if(parent.left==cur) parent.left=null;
                      else parent.right=null;
             }
             helper(null,cur.left,result);
             helper(null,cur.right,result);
    } else {
             if(parent==null) result.add(cur);
             helper(cur,cur.left,result);
             helper(cur,cur.right,result);   
    }
}

补充内容 (2016-12-19 10:44):
不好意思，应该是第二题

第四轮跟我好像！

同样good luck

恭喜楼主！题目难度感觉就是汉子题呢！还好楼主够厉害！google大礼包已经在路上啦！

恭喜楼主，offer肯定没问题的。

问下楼主第二题，能给个输入和输出吗？

我的想法是一棵树，并且有个函数boolean判断是否应该删除某个节点，那是不是遍历完整颗树后去掉应该删除的节点就可以了？

zyoppy008 发表于 2016-12-18 06:34
第四轮跟我好像！

请问下，第二问您当时是怎么想的

aangel 发表于 2016-12-18 12:49
恭喜楼主，offer肯定没问题的。

问下楼主第二题，能给个输入和输出吗？

是的，就是遍历这棵树，然后删除掉应改删除的节点，有一点要注意的是就是比如这个点要删除，那他的父节点对应的孩子要设成NULL。用递归就可以了。

楼主一定拿offer 想问下第一题为什么不能有external sort。 楼主priorityqueue的做法是怎么样的？ coding时要写从文件读数据的代码吗

wsrrzxl 发表于 2016-12-19 04:48
楼主一定拿offer 想问下第一题为什么不能有external sort。 楼主priorityqueue的做法是怎么样的？ coding时 ...

第一题就是merge k sorted array ah....
you should use priorityQueue to resolve LC23, is that correct?

freemail165 发表于 2016-12-19 09:59
第一题就是merge k sorted array ah....
you should use priorityQueue to resolve LC23, is that corre ...

有道理，把所有文件的BufferedrReader当成LinkedList