Google电面11.12

下午刚面了谷歌电面,
不好确定小哥是哪国人,有口音,电话也有杂音,全程还是蛮慌的。
题目本身不难,但是叙述比较繁琐,用了好久才沟通明白。
给一个功能函数 bool worseCommit(int commit1, int commit2),如果 commit2 worse than commit1,返回true, 反之返回false。
给你一串没有improvement的评论序列,找出其中worse的评论。
Example:
Input:start=1,end=1000, 若其中worseCommit(2,3), (500,501)返回了true,
output:[3,501].

二分法做的,但是全程沟通不是很顺畅,求好运

我理解的楼主的意思是“在一个(非单调)递减序列A中,找出满足A(i) > A(i-1)的所有i”。只不过你不能直接获取A(i)的值,而只能比较任意两个元素A(i)和A(j)的大小。

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

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

给你一串没有improvement的评论序列,找出其中worse的评论。

楼主可以再解释一下吗

没明白 果然难懂 到底返回什么?

没看懂啊。。是不是只是求一堆里最差的那个?

是给一串评论 然后通过接口函数返回值找到worse comment吗

不理解为什么要二分,不是需要返回所有的吗?必须要把所有的相邻的都scan到吧

楼主,请问是怎么二分的呀

刚开始我写了scan,所有相邻的,时间复杂度稳定O(n).
但是评论数据里有大量一样的commit,比如1,2,3,4…99,100全部都一样,如果二分一次就全部去掉了,能大大提高效率,我跟面试官这么说的,他也表示同意。

没有improvement的意思就是 后面的评论比前面的差,或者一样,不会比前面的好