2022一月份谷歌加面两轮coding据

刚收到据信，心中意难平，节假日花了大量时间准备面试，愧对家人。。。

大厂5.5年经验，12月底内推后跳过了phone screen，约了一月份onsite。级别是E5，感觉面的还行，满心欢喜。。。onsite第二周收到邮件要加面两轮coding，当天就回复约了下周加面。

第一轮， 美国小哥，campus bike, 第一问， assign each bike to the nearest employee, the lower id wins if same distance, 第二问， minimize the longest distance. 第一问我的解法是从所有的bikes 开始bfs。 第二问

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

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

！！！

第一问觉得代码量太大了，一共40分钟做题时间，开始还要5分钟去读题和clarify，时间太紧了。第二题， 我底下想了又想，还是没想到dp如何去做 （dp 解 job scheduling 我刷过，感觉这个题不能套用）。地理的朋友们如果知道怎么做请指教。

从欢喜到凉凉再到欢喜再到凉凉，心中意难平。

第一题的第二问感觉是匈牙利算法加一个binary search？

狗家面挂经验：如果面试官让你先问问题（关于组，关于每日工作），然后开始coding，一定委婉回绝坚持先做题。做系统设计的时候，即使面试官说是web based，也要当作所有的api是从cli直接调用，就当user session之类的不存在。

PacificDou 发表于 2022-2-7 10:27
想讨论一下第二题。如果 schedule的最大的时间 在一定范围内 (比如10**5)的话，好像DP是可以解的，我的思路 ...

又想了下，这个assume第k个interval 应该加在 [j. q], 没有考虑到应该加在 [0,j] 的情况。
所以应该是 dp[n][k] = max{dp[j][k], dp[j][k-1] + overlap(j, q)},

谢谢分享.
你已经很棒了.先放松一下.
如果有其他面试的话.总结经验,继续前行.
祝以后的面试有好结果.
(谷歌可以来年再试)

请问这种情况不会downgrade到L4么？

Google 不值得，钱不多，现在招人也水，phd+大厂5.5年经验可以试试staff了吧。亚麻L6 60w不香吗

想问lz可以给一个第二题的例子吗？太菜了没有看懂 :(
找到maximum overlapping -> 是说找到最多有多少个overlapping的区间..？找到最长的overlapping区间..？

感谢楼主分享 我反而觉得第二题比第一题简单。
楼主之前的onsite能分享下吗，感谢楼主！！！第一题的followup除了dfs实在想不到啥其他方法。

lsssss 发表于 2022-2-6 17:00
想问lz可以给一个第二题的例子吗？太菜了没有看懂 :(
找到maximum overlapping -> 是说找到最多有多少个ov ...

有一些uncovered 的 oncall schedule, 每个长度不等， 如果添加k个人，每人可以cover连续的q小时。 问最多能cover多少个hours of oncall.

input: [[8, 12], [14, 15], [20 25] [30, 33]] (inclusive), k=1, q=8
output: 7 hours

wuqun597090371 发表于 2022-2-6 19:19
感谢楼主分享 我反而觉得第二题比第一题简单。
楼主之前的onsite能分享下吗，感谢楼主！！！第一题的follo ...

我是楼主，至今没有想到第二题怎么做，你可以分享一下思路吗？谢谢！

wuqun597090371 发表于 2022-2-6 19:19
感谢楼主分享 我反而觉得第二题比第一题简单。
楼主之前的onsite能分享下吗，感谢楼主！！！第一题的follo ...

关于onsite，等我回忆一下开个新帖。

想讨论一下第二题。如果 schedule的最大的时间 在一定范围内 (比如10**5)的话，好像DP是可以解的，我的思路是这样的：
设  最后一个schdule的结束时间是n，添加k个人后，最大overlapping为f[n][k]，那么可以根据  第k个人的开始时间  来讨论,
f[n][k] = arg maxj f[j][k - 1] + overlap(j, q), where j = n-q, n-q+1, n-q+2,...,n, overlap(j, q) = max overlap if k-th person start at time j
时间复杂度的话，每个f计算量是O(q)，总共n*k个，所以就是O(n*k*q)