谷歌onsite

哇好崩啊。感觉题都特别简单，但打得不好，估计是挂了。看来平时还是得多刷题啊！

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

反省就是，谷歌的题最近其实并不难，比如这次准备了一些复杂的数据结构和算法union find, binary indexed tree, trie这些都没有考到。但是题目比较新颖，需要反应很快，迅速转化成编程模型。楼主刷题不过200道，这次面试也学到了很多，之后再接再厉了。

流星无痕 发表于 2018-8-23 12:36
输入是List flowers, int[] query (一次一个query)
不搜索的话直接对每个花花可以算出它在query点的芳香 ...

这个题，我的想法是 1）对花花按芳香值从大到小排序；2）（按从大到小的顺序）计算花花在每个grid的芳香值；3）计算grid芳香值是以每个花为中心，向外BFS，一旦发现grid已有芳香值已经大于这朵搜索花在这个grid的芳香值，就停止搜索。

edu 发表于 2018-8-23 13:51
这个题，我的想法是 1）对花花按芳香值从大到小排序；2）（按从大到小的顺序）计算花花在每个grid的芳香 ...

不用搜索啊。直接使用公式Math.max(0, S - R * (Math.abs(xf - xq) + Math.abs(yf - yq))) 就好了 其中S是这朵花的原始香气，R是减弱速率，Math.abs(xf - xq) + Math.abs(yf - yq)这是曼哈顿距离。对于每朵花更新整个board每次取max就好了！Ta-da!

fropen 发表于 2018-8-23 11:09
第四轮，输入是 List nodes? Node 里存有left，right指针。这题是不是topo 排序啊？计算每个点的入度，从入 ...

感觉不太像拓扑排序吧比如：node1: left -> node2 right -> node 3 node2: right -> node4 node3: left -> node4这样是存在一个拓扑排序的但是并非二叉树

第五轮貌似是 853. Car Fleet
用需要的时间扫一遍，看看能形成几个小集团

楼主可否解释一下第一题，车长度为2或3，只能前后移动，应该可以转弯吧

rexue70 发表于 2018-8-23 08:28
第五轮貌似是 853. Car Fleet
用需要的时间扫一遍，看看能形成几个小集团

差不多，就是一个简单的变种，没有target，也没有position，就是一个队列，让求最终的car fleet array

sean1993519 发表于 2018-8-23 08:49
楼主可否解释一下第一题，车长度为2或3，只能前后移动，应该可以转弯吧

不可以转弯的噢。车宽度=1，长度要么是2要么是3

第三轮，不搜索，怎么做？输入是  int[][] grid, int[][] querys？

第四轮，输入是 List<Node> nodes? Node 里存有left，right指针。这题是不是topo 排序啊？计算每个点的入度，从入度为0的Node 循环。

流星无痕 发表于 2018-8-22 21:45
不可以转弯的噢。车宽度=1，长度要么是2要么是3

那岂不是只能走直线

sean1993519 发表于 2018-8-23 11:39
那岂不是只能走直线

对 就是这么平凡的设定哈哈哈