整理了Google一些最新高频面经题，求大神指教

nancyberry 发表于 2018-6-11 03:01
大神好厉害！我有些小疑问。

第二题 Follow-up的BFS解法没明白TQT，能再细讲一下吗~

第二题
题目是说最多能把一个 1 变成 0，那最优解就分两种情况：
* 原题解，路径上全是 0
* 路径上中间某个点是 1

这里考虑第二种，走的路径肯定是  "左上角 -> 0 -> 0 .. -> 1 -> 0 -> 0 -> 右下角"
然后，"左上角 -> 0 -> 0 .. -> 1" 就是求从左上角做为起点，每个 1 做为终点的 BFS，
类似，"1 -> 0 -> 0 -> 右下角" 就是求从右下角做为起点，每个 1 做为终点的 BFS
最后就是拼凑路径（枚举每个 1），把两段路径加起来求个最小值


第四题
哦只有一端拿的话就简单多了，如果是从两端拿，也可以扩展我想的二维 dp 的形式


第六题
直接比较就好了把，点(x', y') 如果满足 ax' + b < y'，那就在线下面了
比较 tricky 的地方就是和 y 轴平行的线

idatascience 发表于 2018-6-11 07:59
小仙女加油啊~

嗯哪

第二题和第一题不一样哦。可以走回头路

所以不能用DP。应该用dfs， followup只需要在node里面加一个remainingMagic即可。这个解法可以用于k次magic的followup Q2。不过一般面试都达不到这一问。

flymelody 发表于 2018-6-11 11:04
第二题和第一题不一样哦。可以走回头路

所以不能用DP。应该用dfs， followup只需要在node里面加一个rema ...

Nice catch! 那第二题应该用BFS，多谢！

第二题解法有问题，由于可以随便走，所以应该用BFS，而非DP

G为啥考这么多DP题。。

我记得第六题的面经是不是有个条件是任意三点不在同一直线上？
如果没有限制条件 那所有点在同一直线上 怎么也无法把点分成两部分吧...
但是如果有这个限制条件 那一定有一对点可以把剩下的点分成两部分(好像时钟）所以针对一个点枚举剩下的n-1个点不就可以了吗？ = =

第二题应该是google foobar
http://www.1point3acres.com/bbs/thread-203208-1-1.html
我当时是起点终点分别bfs到所有离0距离为1的点来做的

Altynai 发表于 2018-6-10 23:25
第一题
Follow up 3：可以再做一次 dp，但是只走

借楼主的帖子再发几个我不太清楚的面经题，希望高人指点一下，也希望能帮到各位同学

8. 产品中要monitor service response time，假设已经收集了大量数据，给定percentile的定义：如果说20ms的响应时间是90 percentile，代表收集的数据中90%的response time小于20ms，10%的response time大于20ms。同理，如果是说50 percentile，就是50%小于，50%大于。分析如何处理数据从而得到percentile。（这里假设了已经收集了大量数据，但是我们仍然就大量采集数据的系统环境进行了分析。最终还是回归到已经收集好的情况下）假设数据量大到memory无法存下，怎么处理？不考察系统设计，只根据实际需求在数据和算法层面进行优化。

9. 扫地机器人问题
给出了扫地机器人的interface，要让扫地机器人扫遍整个房间。房间设计成一个m*n的grid，0是路，1是障碍，实现几个function。
move() 朝着机器人面对方向移动一格
turnLeft(int k) 逆时针转动k次
turnRight(int k) 顺时针转动k次
clean() 打扫机器人当前格子
cleanRoom() 发动机器人清理整个房间，清扫任务的entry function。
难点主要在如何把move turn和clean的function扦插到具体的算法实现中

10. 一堆自行车和一些人在一个2D的matrix里，要每个人match到一辆自行车，人和自行车的距离越短越好

楼主想问下你这个第一题，题面到底是从左上到右下还是左上到右上？

如果是左上到右下感觉follow up 3没什么意义啊，反正要走到最后一个row

补充内容 (2018-6-13 09:19):
找到原帖了，是左上到右上：
http://www.1point3acres.com/bbs/thread-380867-1-1.html