Chapter 43 Google 2017 12

http://www.1point3acres.com/bbs/thread-311725-1-1.html

2018(4-6月) 码农类博士全职 Google - 内推 - Onsite |Otherfresh grad应届毕业生
上周面的,心里没谱,发面经攒点人品!!.
1. Given HeightMap (matrix),starting position, ending position, 输出从起点到终点的effort.effort有给定的function,可以根据相邻两点高度计算.
2. topological sort
3. Leetcode 334
4. Research
5. 参见狗家面经第三轮

http://www.1point3acres.com/bbs/thread-307481-1-1.html

2017(10-12月) 码农类本科全职 Google - 校园招聘会 - Onsite |Otherfresh grad应届毕业生
今天刚面的新鲜面筋,感觉是跪了…还是造福一下地里的大家吧
第一轮:
一个口音很重说话很轻的白人大哥,让我写一个class来为user generate一个maze.很开放,几乎没有任何要求,需要和面试官讨论,因为开放性很大,lz答的也很一般就不提lz咋做的啦.
第二轮:
面筋机器人扫地,lz用的dfs backtrack.还剩一点时间简单的问了一个和lc伞玲巴很像的一道题,就是indexed tree.
第三轮:
给个html的文件,输入用tree来表示,让你比较两个html文件显示出的东西是否一致
e.g.
Hello
打出来就是 “Hello”,这里不考虑(斜体)的差异,“”是因为有

.
lz用dfs做的
follow up:如果string很长怎么办,lz想的就是不一次性吧整个string generate出来,一点一点generate,然后看两个html的前部分是否一个是另一个的substr
第四轮:
lc原题的变种,就是那个两个玩家每轮从左右两端选一个拿走的题(抱歉没找到题号),原题是返回先手是否能赢,这个体让输出先手的人最多能拿到的数字和是多少.本质一样的,就是很简单的dp.
还问了一道爆难的智力题(有可能是我太菜了),面试官一开始就说没指望我做出来.应该是因为我前一个写的比较快,就当玩考了考我(可能我天真了,其实这个才是重点?).
是给一个01组成的矩阵,每次可以click一个点,这样这个点周围的十字行的bit全都flip.问给一个matrix能不能通过这个操作变成全0..
最后几乎是面试官喂给我答案…说是0肯定是被flip偶数次,1是奇数次,然后每个点click两次没有意义,所以只会被click 0或1次.然后就可以列出很多式子
比如
01
10
的matrix,用c1到c4表示每个点被click的次数.列出来的式子有:
c1+c2+c3=0 or 2
c1+c2+c4=1 or 3.
c1+c3+c4=1 or 3.
c2+c3+c4=0 or 2.
至于怎么解面试官说的很笼统,就是把c1消掉什么的…
感觉跪了,lz一三轮答的有点慌张,因为感觉题怪怪的,最后勉强写出来了也不知道面试官满不满意.真的很向往google,骗骗自己求一下人品,大家加油
补充内容 (2017-12-7 11:47):
于12.06收到过HC的电话

http://www.1point3acres.com/bbs/thread-314690-1-1.html

2018(1-3月) 码农类硕士全职 Google - 内推 - Onsite |Otherfresh grad应届毕业生
刚面完.
第一轮白人,给一个有向图,图里面有label和state.state的取值范围有多种,其中有一种是end. 给你任意个图的node,问能否gurantee 走到end,即他所有的neibors都必须能走到end,只要有一个return false. 我carify 有没有可能出现环,他说好问题,然后让我直接返回false. 我用dfs + hashSet直接秒了,然后他让我跑两个test case.最后他说应该能work,然后剩几分钟聊天了.
第二轮老中,Majority number,第一问找1/2,我从sort讲起,讲常见的sort方法以及他们的时间空间复杂度,然后讲hash Map, bit 操作.然后假装不知道vote算法, 他让我进一步优化,我说我试试水涨船高.然后demo了下,写了下算法,最后问1/3的情况.每一种算法再分析下,让我继续用vote算法.最后他说pretty good.
第三轮:比较版本的新旧.给两个String,比如“1.1.1”“3.1.1”,“3.1.1”是新版本.我跟他clarify时,说了下null 和size==0的情况,他问我这两种情况有什么不同,我给他分析了stack heap结构.然后问我应该各自返回什么,我说为null时一般视为异常,然后写了try catch结构抛出异常.但是其中一个String size == 0时返回另一个String即可.他说很好.然后写代码.挨个比较,最后他问我“1.1”和“1.1.0”和“1.1.0000”该怎么办,我说那我们需要pre process或者Pro precess,让我分析哪种好,我说时间复杂度和空间复杂度都一样,所以两种方法没区别,他说对.然后我写了preprocess,把最后的0全都删除掉.
第四轮:一办BQ,问我最近的项目,最难的地方在哪里,我答最难的地方也是我最骄傲的地方是当我们的用户增加时,我的架构需要做相应的优化.然后见我使用了cache,问使用cache常见的风险是什么,我说风险是cache的数据会掉电消失,我们使用log的方式从掉电中恢复cache数据.然后剩一半时间问我假如一辆车只有一排位置,每次乘客上车后都希望能坐在最长的interver 的中间.位置是double,一提到double我就说我们要小心double的比较,然后他问为什么,然后跟他扯double的精度问题.然后分析corne case,分析null 和 empty两种情况,接着他问如果是empty的话,返回什么比较好,我说一般情况下可以返回特定值,然后他又问这么做有什么潜在的问题,我说也许这个特定值本身是有效的.然后他又问既然如此有什么更好的解决方法么,我说那我把double改成Double,返回NULL,然后他说much better.最后用mapHeap把这题秒了,然后我自己分析时间空间复杂度,他挺满意,最后让我跑两个test case.
第五轮:interval问题.这一轮最蛋疼,他首先介绍了下谷歌的分布式系统有很多的task要运行,告诉我每个task的起始时间和终止时间,要我们判断有哪些任务可以第一个执行.花了将近二十分钟的时间才把问题抽象成算法问题,然后暴力解,先sort,又跟他扯常见的sort算法及时间空间复杂度.然后两层for loop比较.最后分析时间复杂度O(n^2)空间复杂度O(1).然后让我优化比较次数,时间就剩一点点了,没想出来,时间到了后他自己跟我说了下他的解法,我说原来就是用两个heap,他说是的.