Google 2019/03/15 Onsite

谢谢楼主分享，请问一下楼主第三轮，是两个人选择，还是多个人呀？

visa 发表于 2019-3-16 13:37
谢谢楼主分享，请问一下楼主第三轮，是两个人选择，还是多个人呀？

就是要把巧克力分给K个人，这K个人里包括我自己，怎么切由我决定，但我只能是最后一个选，相当于没有选择权，我只能拿最后剩下的那块，而且每个人选的时候都是Greedy的，就是挑当前状况下最甜的一块。由于我有权决定怎么切，那么我就能选择怎么切以使得自己能得到最大的

RicciWoo 发表于 2019-3-16 13:44
就是要把巧克力分给K个人，这K个人里包括我自己，怎么切由我决定，但我只能是最后一个选，相当于没有选择 ...

懂了， 谢谢楼主，这道题应该是找如何把array 分成k 块儿，要求最小的那个最大值最大

visa 发表于 2019-3-16 14:29
懂了， 谢谢楼主，这道题应该是找如何把array 分成k 块儿，要求最小的那个最大值最大

还不是很明白，若果是这样，切的人，就能得到第K甜的，把前K-1切出去？

多谢楼主
切巧克力应该和lintcode上的copy books一样的，binary search
schedule jobs的话，topo sort然后找最长路径就可以了，对吧？

RicciWoo 发表于 2019-3-16 11:46
我觉得用heap应该也可以，我是用的tree map，key是absolute time，value是callback函数指针，这样它自动 ...

这里有一个问题，把所有的callback和对应的absolute time存到treemap里之后，应该有内部的timer，当到时间之后调用最近的callback，对吧？
但是如果在timer还没有到时之前有新的callback request，而且absolute time还小于当前最早的callback，那么就会错过新的callback request
所以还需要condition/notify一类的机制？

3题410？

xiangwangtong6 发表于 2019-3-16 17:14
还不是很明白，若果是这样，切的人，就能得到第K甜的，把前K-1切出去？

换句话说，就是给一个无序数组，让你把它分成连续的k份，问怎么分能够使得分完后最小的那份在所有不同分法中取最大值。举个例子
k=3，nums=[2 3 4 2 3 3 2 3 1]，你可以这么切 2 3 4 | 2 3 3 | 2 3 1 ，即 9 | 8 | 6，那么k份中最小是6。
你也可以这么切 2 3 4 | 2 3 | 3 2 3 1 ，即 9 | 5 | 9 ，那么k份中最小是5，问怎么切能够得到最大值。

bdhmwzfa 发表于 2019-3-16 18:51
多谢楼主
切巧克力应该和lintcode上的copy books一样的，binary search
schedule jobs的话，topo sort然 ...

切巧克力确实是用copy books的思路，binary search，或叫二分答案。
schedule jobs，我面试一开始就说用topo sort，但面试官一直在说好像不太好用topo sort，
后来跟面试官讨论中，发现有一个level的结构，然后你得把jobs分配给p works，
一个level的jobs数目可能超过p，所有分配不完还得留给下一个level。举个例子
    0     k = 2，像这样第3层有3个job，要分派个2个worker，分派不了，
   / \               那就只能留到第4层，这样不停的往下分，最终应该能得到结果。
  1   2            这是面试者最后提示我的，这道题我没做完，连代码都没写。
/ \   |
3  4  5

bdhmwzfa 发表于 2019-3-16 18:51
多谢楼主
切巧克力应该和lintcode上的copy books一样的，binary search
schedule jobs的话，topo sort然 ...

schedule job楼顶题目里还有个工人的数目。而且需要计算的是完成所有工作的最短时间。