Google/Youtube onsite 面经 @MTV

02/11面的。
刚收到HR邮件说明天约个时间打电话，说打个电话告诉结果，这种就是妥妥挂了。
非常不好意思，面完没记录，很多题都忘了。
一共五轮。
第一轮， 给一个list 的时间start, end, profits, 让求出来不冲突的最大profit，foll

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

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

近确实看G给onsite和offer确实少。


补充内容 (2016-3-2 09:33):
上次打电话，这周一进了HC，然后给挂了。

qjx026 发表于 2016-2-24 23:36
DP思路是对的，具体思路我记不太清楚了，最后时间复杂度是N^2.
大概思路是先把interval 按照endTime排序 ...

关于第一题，个人想法，不一定对：
可以优化一下，先排序，然后dp[i] = global max for interval 0 to i (do not need to include i), 然后只要找到i之前最近的valid interval和i-1比较，就能update了 , dp[i]=max(dp[i-1],dp[j]+A[i]) for A[i] not overlap A[j]，也就是两个状态，取当前interval和不取当前interval。 至于怎么找到之前最近的valid，可以用个priorityqueue来做，没实际做过，但是应该和meeting room ii差不多。 最后复杂度应该是NLog(N)

补充内容 (2016-2-25 00:00):
第四轮应该是leetcode的题吧！
第五轮 拓扑排序，阿三哥一直提示你就是说明他要挂你。。 感觉lz被黑了。。

hpplayer 发表于 2016-2-25 06:27
第一题LZ怎么做的？

我能想到的是用DP matrix

DP思路是对的，具体思路我记不太清楚了，最后时间复杂度是N^2.
大概思路是先把interval 按照endTime排序。用一个HashMap来存储该interval的前一个interval的序列序号，和当前的利润的最大值。
每次遍历到一个点时候，往前找到valid 的 最大利润点，然后更新HashMap.
大概思路是这样。

csgtc 发表于 2016-2-25 12:57
关于第一题，个人想法，不一定对：
可以优化一下，先排序，然后dp = global max for interval 0 to i (d ...

对对，第一轮我就是用你priorityQueue解法做的，不过我把dp[]换成了HashMap。第四轮这个是那个老白自己编的题。第五轮那个三哥看着挺老实的，不过老打断写代码这个也没法忍啊。
你的recruiter打电话前给你发邮件预约时间没？

bless lz!

第一题LZ怎么做的？

我能想到的是用DP matrix
dp[i][j]就是指从start = i到end = j的最大PROFIT
需要用4个循环来更新这个MATRIX，里面的两个循环是扫描START = I 到 END = J里所有组成的可能性

打电话不一定是坏事啊！ 我recruiter就是直接一个电话打给我说hc过了。。

我和你思路相似。

第一轮， 给一个list 的时间start, end, profits, 让求出来不冲突的最大profit，follow up, 求出最大的组合list。中间聊聊设计什么的。

我只想到了n方的解法，楼主怎么答的呢？

还有那个概率题是怎么样的，很多坑？