Google过经

给大家来提供一个data point，顺便求米。我面的L4，但是因为紧张前两轮发挥不好，所以被降到了L3。不过拿的应该是L3顶包。

technical phone interview 国人姐姐帮忙放水，就不放题目了。真的很简单，这轮纯粹运气轮。

onsite
1. LeetCode 56， 不过每一个interval还对应一个price，要求最后merge完成的结果里面只包含最低的price。
比如：day1-day5, price = 5
          day2-day10, price = 10
          day4-day6, price = 2
那么结果应该是[1-4, 5], [4-6, 2], [6-10, 10]
2. 有一个商人，在AB两个城市做生意，他每天只能在AB城中的一个城，每天在A或者B城能赚到的钱会给你。但是每次他从A跑到B或者从B跑到A都要花一个cost。问最大盈利。
例子：A[1, 10, 15, 8]
          B[100, 1, 3, 1]
          cost = 1
那么他所在的位置应该是：BAAA，他的盈利为100 - cost + 10 + 15 + 8
3. 给一个tree
a -> b -> c -> d -> e -> f
        ^         

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

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

说他没有follow up觉得我做得很好，他主要就看能不能想到需要两遍dfs。所以剩下的时间就扯了扯闲天儿。

第四轮大概想了想就给了个用Queue做的O1的算法，不过现在看来都不需要用queue。follow up用的是stack，面试官提示了一下让我想interval乘threshold的物理意义是什么。我就想到了其实是最大长方形面积。所以也是一个O1的算法。不过这道题其实用greedy algorithm可以做，不过如果不给时间t的具体值，比如他问你在所有的时间里是否包含满足情况的interval，greedy就不work了。

最后offer已接，特此回馈地里。顺便求米求米求米！也祝大家大吉大利，今晚拿offer！
edit:
VO之后一周通知过HC，一周后team match成功，三天后发offer

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

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

感觉第一题更像而异吧，skyline的变形

楼主辛苦！面经很详细很有帮助 🙏

恭喜楼主，能请教一下VO之后大概多久有消息吗？谢谢

这么详细的面经，点赞

请问楼主第三题 的 字母 e为什么不压缩进去，以及可否再讲讲如何2遍dfs，很想知道！~已加米

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

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

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

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

第二题dp可以做吧， dp_a[i] = max(dp_a[i-1], dp_b[i-1] - cost) + A[i];
dp_b[i] = max(dp_b[i-1], dp_a[i-1]-cost) + B[i];
res = max(dp_a[n-1], dp_b[n-1]),
dp_a /b是i天在 A/B工作目前为止的总收入。

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

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