7.10山景城google

先说总体的体验： 谷歌的面试官真是我见过最nice的。hint给的非常专业，作为业界最高high bar的公司，每一轮都感觉完爆我在西雅图面过的各种玄学社。
..
早上10.30 check in。哼着小曲唱着歌，反正也没抱着指望，心情反倒轻松不少。

第一轮： 美国白人大叔，工作了20年，去过英伟达苹果又来谷歌。 问的题目是一个数组是乱序的， 例如 3 2 1 4。最短经过多少步的swap, 可以变成排序好的状态。 和做题网站854差不多，唯一的区别是要打印路径，楼主说再加个dfs就行。楼主板书太烂而且聊了20分钟简历， 他对cuda非常感兴趣。。。于是dfs没写完。（当然这题本身也不算难）。

第二轮: 东南亚小哥，面经题，不过我也没读懂面经lol。面的时候才知道题的意思。 两个一维数组  例如：      2 3 4     代表你往前看，往左看，能看到的最高的building。 然后让你估算这个城市的大概的体积。 楼主听完一脸懵逼， 于是小哥带我分析一个暴力解法。 例如例子里的 填满就是 2  3  4 。再求和就行。                                                                                  1
                                     1    1  1  1                                                                                                           3
                                     3    2  3  3                                                                                                           2
                                     2    2  2  2

            反正稀里糊涂就变成了行列对应的最小值，暴力做法是o (m * n)每个遍历一次。小哥问能不能更快，那只有二分查找了。 于是又是得到一堆hint写了个二分查找。。。。期中还把弱智复杂度说错了一次。小哥感觉看傻逼一样的看我。                                   
午饭我是一点不客气。。。面条鸡蛋水果和甜品拉满。俄罗斯小哥不大热情，不过我们还是聊了很多NBA和中国的百度防火墙啥的。 （他是勇士球迷233，夺冠那年粉的，不知道说啥好）                                                                                                                第三轮： 不知道中国还是日本小哥。 看起来比我年轻工作了10年了。问了个做题网站的 5， 还有一个n的array怎随机挑选k个组成个subset。楼主这个居然扯错了5分钟。follow up不修改array咋做， array变成int 咋做。 follow up没写完。
第四轮： 前端美女。 问了一个链表是一个环， 然后我们按照规律删除奇数的节点。 楼主加了个dummy node直接写了。 第二题是找图中经过输入节点最小的环， 输入给你一个图的节点 和 图。这个她说时间可能不够咱们逼逼一会。又是bfs。但是中间路径表示我卡了很一会，有8分钟吧，最后提示用了个hashmap。

总体体验比微软的6轮轻松多了，而且面试官人很nice让你放松。狗家爱考图搜索和binary search。手如果稳的话感觉去还是很稳的。比做的做题网站题目容易多了。 大家加油。楼主恰恰是个手不稳的人，单机做题可以白板可能有bug。 估计挂了move on。                                                                                                                                                


补充内容 (2018-7-11 07:40):
我电面2月结束的，拖了5个月，hr气的想骂我了233,2018 hc的末尾面试

补充内容 (2018-7-14 02:19):
32楼有面经题解法

补充内容 (2018-7-18 02:15):
update:挂了冻一年无feedback。标准最烂结局

补充内容 (2018-8-4 07:18):
有人说我第三轮的抽样该用蓄水池抽样。最近刷新的做题网站题目发现519的那个题高票解答就是我当时用的办法。叫做Fisher-yates shuffle。有兴趣的朋友们可以看看

第二题的话
给你一行data 是int[] row, int[] col。 例如是            2    1    3
                                                                        1     1    1    1
                                                                        2     2    1    2
                                                                        2     2    1    2

这题就是看你如何能快速统计每一行的元素和，注意每个位置的元素的值是由该行和列元素的最小值来决定的，明白了这点就可以做了
（1）根据int[] col 排序
（2）根据int[]col 算出每个位置的prefixSum
（3）对于每个int[] row 的元素，假如是row[j]，二分搜索排序好的int[] col, 得到的 位置 假如为 i， 那么该行的元素和就等于 prefixSum[i] + (len(col) - i) * row[j]的值
  (4)  对于（3）的结果求和.

bowenzh 发表于 2018-7-12 10:48
加油啊！！   第二题我在我准备电面的那时候见过类似的面经~~    我觉得反馈还是可以的，等等HC结果看一看 ...

嘿嘿谢谢大兄得

一定能进的。
话说k select那题，用水库抽样法可以嘛，因为水库的话是每个都有1/n概率被选中，那我乘个系数k如何呢？
顺祝offer

FML 发表于 2018-7-11 07:17
一定能进的。
话说k select那题，用水库抽样法可以嘛，因为水库的话是每个都有1/n概率被选中，那我乘个系 ...

我觉得可能可以？我忘了咋写了，我都approach是每次随机pick一个Index， 把他和数组的最后一个数字交换。然后缩小random的范围。 面试官感觉觉得还行？ 例如 1 3 4 2我们从4个里面找到个3。我们就把3和2交换，同时把3放到结果中。1 2 4 3里面下次只找1 2 4。反正粗暴直接千万别多想

祝顺利 感觉不好不一定结果不好呀

h604364120 发表于 2018-7-11 07:41
祝顺利 感觉不好不一定结果不好呀

楼主感觉挺好的，毕竟每题都会做。不过经过了这么多破事我已经不相信自己的rp，说不定我白板有bug就挂了lol

请问lz能再说下第二轮  给的例子好像格式乱了

blactangeri 发表于 2018-7-11 10:04
请问lz能再说下第二轮  给的例子好像格式乱了

我晚点写个word....这里的编辑太难受了

blactangeri 发表于 2018-7-11 10:04
请问lz能再说下第二轮  给的例子好像格式乱了

应该是利口儿要把 原题。。

sarahzjn 发表于 2018-7-11 07:24
我觉得可能可以？我忘了咋写了，我都approach是每次随机pick一个Index， 把他和数组的最后一个数字交换。 ...

你这做法应该是最优解了

忘记密码 发表于 2018-7-11 10:57
应该是利口儿要把 原题。。

不是 ，字数字数字数