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

楼主马上要面Google，最近刷了地里的一些面经，整理了几道Google近期的面试题，至于解法我没有找到特别好的，请各位大神不吝赐教哈！希望可以帮助到要面Google的同学们~

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

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

第七题：随机生成一个Candy Crush
黑人问号脸？有大神能详细描述下题目吗？




补充内容 (2018-6-11 11:33):
第二题解法有问题，由于可以随便走，所以应该用BFS，而非DP

第一题
Follow up 3：可以再做一次 dp，但是只走 <= H 的路径，再用总数减一下
Follow up 4：也是矩阵切割的思想，但是要处理先后顺序

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

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

第七题
没看过这题。。
[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]

flyingforce 发表于 2018-6-15 07:40
第五题，做起来发现倒也不难，刚看到完全懵懂

import java.util.*;

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

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

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 轴平行的线

第六题 是二分法吗 匈牙利算法之类的

第七题 感觉会不会是和Battleship game一样只要是valid就是随机生成直到排满。。。假如说不能没有地方可以动的话。。就再生成一遍？感觉好僵硬。

楼主啥时候面呀？

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

大神好厉害！我有些小疑问。

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

第四题：题目给定每人都是从头拿，不用考虑从尾拿的情况，所以感觉用一维DP就可以。
dp[i] is the max score of current player choosing from arr[i] to arr[n - 1]
dp[i] = sum[i] - dp[i + k], 1 <= k <= 3, sum[i] is sum of arr[i] to arr[n - 1]
maxFinalScore = max(dp[0], sum[0] - dp[0]), because dp[0] is the max score of player1, and sum[0] - dp[0] is the max score of player2.
是不是酱紫啊？~

BTW，第五题的思路很牛掰。。震惊了。。

第六题
那么每条直线假设可以用ax + b = y表示，然后是判断每个点在这条线的上方还是下方吗？怎么判断比较方便呢，楼主数学比较渣渣TQT

第七题直接塞糖果就好，如果按行塞你只需要检查左和上没有连续三个即可，塞完检查是否存在至少一个move，不存在就重新塞- 当然你也可以先存一（或几）个move进空图后再塞，这时就需要检查上下左右的连续了…

O0ooo0O 发表于 2018-6-11 01:26
第六题 是二分法吗 匈牙利算法之类的

第七题 感觉会不会是和Battleship game一样只要是valid就是随机生 ...

第六题给跪了啊，感觉一旦问到这种数学问题我就GG了。

我下周就面了，感觉略虚哈哈哈，leetcode我只做了easy & medium的题，希望各位面试官大大放我一马，别问我太难的~

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

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

额，感觉有些字符被吞掉了。。再发一遍：

1. dp[i] is the max score of current player choosing from arr[i] to arr[n - 1]
   
2. dp[i] = sum[i] - dp[i + k], 1 <= k <= 3, sum[i] is sum of arr[i] to arr[n - 1]
   
3. maxFinalScore = max(dp[0], sum[0] - dp[0]), because dp[0] is the max score of player1, and sum[0] - dp[0] is the max score of player2.

复制代码

wang2579 发表于 2018-6-11 03:02
第七题直接塞糖果就好，如果按行塞你只需要检查左和上没有连续三个即可，塞完检查是否存在至少一个move，不 ...

学到了！

小仙女加油啊~

谢谢楼主，下周面GG了