Google 2019/03/15 Onsite

bdhmwzfa 发表于 2019-3-16 18:56
这里有一个问题，把所有的callback和对应的absolute time存到treemap里之后，应该有内部的timer，当到时 ...

这是这道题好玩的地方，不用notification机制的。
一开始我的想法是，每次先把absolution时间需要最早执行的Callback提交上去，
然后如果要新的Callback加进来，而且执行时间比已经提交的更早，
那么我要把已提交的callback重新保存起来，然后把新的提交上去覆盖掉原来的。
后来在面试官提示下，是可以这样的，你写一个callback，用于直接执行时间到了的callback，
每次提交的时候，传的是你写的callback，这样提交callback相当于只是一个定时系统，
现在才明白，这就是他为什么一开始就说假设我们有一个定时服务系统。

木易wen 发表于 2019-3-16 20:41
3题410？

哇，是的呢，是LC410的变种，这里要的是
maximize the smallest sum among these k subarrays

除了第一题都看过，感觉我面经读得还行，谢谢楼主分享了

巧克力那题看过几种包装，其他还有“给一个数组表示一系列的工作难度，执行顺序必须由左到右，分成K天执行，尽可能不要让一天的工作难度太大”之类的，反正就是“给了是数组”,“分成几部份”,“加总最小值”是利口嗣妖龄关键字就对了

RicciWoo 发表于 2019/03/16 21:41:31


哇，是的呢，是LC410的变种，这里要的是
maximize the smallest sum among these k subarrays

请问是最多分成k还是分成exactly K ?

补充内容 (2019-3-17 02:02):
感觉exactly k的话和LC上greedy+binary search做法就不太一样了

kaipeng21 发表于 2019-3-16 23:48
巧克力那题看过几种包装，其他还有“给一个数组表示一系列的工作难度，执行顺序必须由左到右，分成K天执行 ...

是啊，看来我看面经还是太少了，每道题对我来说都没见过，哈哈

补充内容 (2019-3-17 02:21):
我错了，其实第2题我是见到过的

wtcupup 发表于 2019-3-17 01:38
请问是最多分成k还是分成exactly K ?

补充内容 (2019-3-17 02:02):

是exactly k份，是LC410变种，Greedy+Binary Search能做的。
思路是这样的，答案在[1, sum/k]之间，sum是整个数组的和，
在这个区间做Binary Search，而判断mid是否可行，用Greedy就好了。



补充内容 (2019-3-17 02:31):
后来简化了，每个方格的数值在1-10之间，所以不用计算sum，直接sum=10*N就行

第五轮的这个循环法：珀斯特顺序遍历二叉树，对空间复杂有要求么？可以就是常规的while-loop加一个站么？

14417335 发表于 2019-3-16 21:27
schedule job楼顶题目里还有个工人的数目。而且需要计算的是完成所有工作的最短时间。

嗯嗯，我一开始的确想错了

RicciWoo 发表于 2019-3-16 21:27
切巧克力确实是用copy books的思路，binary search，或叫二分答案。
schedule jobs，我面试一开始就说用 ...

大概明白了
那么这道题其实也可以用拓扑排序的，只不过排序方法不一样，按照入度进行排序，入度为零的点就是第一层需要执行的任务，执行一个任务之后，这个任务后续所有的任务入度都减1，这样不断的迭代，可以一层层推进的
当然这里面还有一个问题，就是如果一层中入度为零的节点数超过工人数，那么就需要有筛选，就是要挑出一组节点，使得优先执行这组节点的情况下，总用时最短，这个筛选我没想出什么好办法