Google电面11.12

fangdanzai 发表于 2018-11-13 07:08
没看懂啊。。是不是只是求一堆里最差的那个？

不是 是利用worseCommit这个功能 返回序列中所有比前面评论差的

请问楼主worse的定义是必须连续的两个，第二个比第一个worse吗？就是我找出满足 worseComment(int i-1, int i) == true 的 i, 而不考虑 i-1 之前的对吧？

圈圈熊 发表于 2018-11-13 08:01
请问楼主worse的定义是必须连续的两个，第二个比第一个worse吗？就是我找出满足 worseComment(int i-1, int ...

worse的定义不是，但是题目的意思我问了面试官，是检测连续的两个

yxing05 发表于 2018-11-13 07:24
刚开始我写了scan，所有相邻的，时间复杂度稳定O(n).
但是评论数据里有大量一样的commit，比如1，2，3， ...

可是楼主怎么知道，从哪里进行二分，以及分开之后的部分，有没有包含相等情况呢？

Coco7988 发表于 2018-11-13 11:54
可是楼主怎么知道，从哪里进行二分，以及分开之后的部分，有没有包含相等情况呢？

楼主的意思是不是每到一个位置，用二分法找到这之后第一个更坏的？初始区间是【下一index，末尾index】。

yxing05 发表于 2018-11-13 07:24
刚开始我写了scan，所有相邻的，时间复杂度稳定O(n).
但是评论数据里有大量一样的commit，比如1，2，3， ...

二分不可能求出所有的bad commit，只能保证求出一个bad commit

坨坨 发表于 2018-11-13 15:08
二分不可能求出所有的bad commit，只能保证求出一个bad commit

同意，而且加入每一个元素都不一样，可能要运行nlogn找到所有的worsecommit，好像是比n慢一些？

感觉LZ的意思是，worseCommit()的两个参数不必相邻，可以为任意值，但是返回值是[array of i ] for all i if input[i] worse than input[i-1]....... 这样的话，二分是可以说的通的。

应该是lt278 find bad version吧？或者稍微变形?