新鲜Google intern 电面 大概率挂经

刚刚完成人生第一次面试，分享一下：
真的是心态不大行，太紧张了，感觉无法正常思考，大概率是挂的。。。

两轮都是相同顺序，上来自我介绍，问最喜欢的自己的项目，这俩我都没有准备，现场编。。。
然后问题目，最后问复杂度。

第一个是个Local女面试官，体验很不好，全程冷漠，最主要的是我在思考的时候她就一直在敲键盘。。。  本来就紧张。。

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

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

第二个是个Local男的，很nice，一直在鼓励我，我问他我做的对不对，他说应该对，最后非让我问他问题，我就问你觉得我今天表现得咋样，他说对于第一次面试的来说已经很不错了，估计是客套话。。

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

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

大概率挂了，还是希望亚麻爸爸能捞我吧。

祝大家都顺利，另外别忘了加米！！

第二题有点像离寇药姚凌饵？不过最大值变成了最小值。

加油加油，我也是人生第一次就是面的谷歌实习，也以为挂掉了，居然给了加面，过了一个月还是给过了。。

第二题题目大意是给一个n*n 非负数的整型矩阵，要求找到从右上到左下所有路径中最小的EFFORT(可能有多条路径符合，所以只要返回EFFORT), EFORT的定义是在这个路径中所有2个相连的cell的差值的绝对值的最大值（这个要理解清楚）。
解法：
类似dijkstra的贪心。就是BFS 从右上开始直到找到右下那个cell，把所有相邻的cell 加到 一个min heap里(最小优先队列)，heap用当前cell和前一个cell差值的绝对值（diff）作为排序条件。这样在BFS处理的是所有路径中当前effort最小的那条，如果到达了右下点就可以停止了。
如果有受益 请加大米

第一题leetcode 815

不知道小帅 发表于 2019/12/12 07:34:56
加油加油，我也是人生第一次就是面的谷歌实习，也以为挂掉了，居然给了加面，过了一个月还是给过了。。

但愿有好运啊 哈哈

给zb打call

bupt0001 发表于 2019/12/12 09:11:25
给zb打call

峰哥宁来啦😇

请问一下楼主第二题咋做的呀，已加米

茶园葱绿 发表于 2019-12-12 16:07
请问一下楼主第二题咋做的呀，已加米

第二题binary search, binary search的每一步都是一个bfs:

1. 
   
2. int l = 1, h = INT_MAX;
   
3. while(l < h) {
   
4.      int mid = l + (h - l)/2;
   
5.      bfs from top left to bottom right to see whether there is a path;
   
6.      if(yes) h = mid; else l = mid + 1;
   
7. }
   
8. return l;
   

复制代码

补充内容 (2019-12-13 05:11):
bfs from top left to bottom right with max consecutive difference <= mid

茶园葱绿 发表于 2019/12/12 16:07:33
请问一下楼主第二题咋做的呀，已加米

我跟面试官说了应该是DFS或者DP，我用DFS做的，类似number of islands那种，但是感觉好像不太对；我感觉正确刀想法应该是DP；面试官还问我你为什么放弃了DP，我没好意思说我不会写啊……

Zbeeee 发表于 2019-12-12 22:20
我跟面试官说了应该是DFS或者DP，我用DFS做的，类似number of islands那种，但是感觉好像不太对；我感觉正 ...

DFS+memorization = DP
res = min(for neighbor in neighbors: max(abs(diff), dfs(neighbor)))
memo[i][j] = res