cf36987
(野火春风)
1
下午刚面了谷歌电面,
不好确定小哥是哪国人,有口音,电话也有杂音,全程还是蛮慌的。
题目本身不难,但是叙述比较繁琐,用了好久才沟通明白。
给一个功能函数 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].
二分法做的,但是全程沟通不是很顺畅,求好运
bm18369
(迷你宝马)
2
我理解的楼主的意思是“在一个(非单调)递减序列A中,找出满足A(i) > A(i-1)的所有i”。只不过你不能直接获取A(i)的值,而只能比较任意两个元素A(i)和A(j)的大小。
bean
3
二分不可能求出所有的bad commit,只能保证求出一个bad commit
cf36987
(野火春风)
4
不是 是利用worseCommit这个功能 返回序列中所有比前面评论差的
cf36987
(野火春风)
5
给你一串没有improvement的评论序列,找出其中worse的评论。
楼主可以再解释一下吗
是给一串评论 然后通过接口函数返回值找到worse comment吗
tz38546
(和睦堂主)
9
不理解为什么要二分,不是需要返回所有的吗?必须要把所有的相邻的都scan到吧
cf36987
(野火春风)
11
刚开始我写了scan,所有相邻的,时间复杂度稳定O(n).
但是评论数据里有大量一样的commit,比如1,2,3,4…99,100全部都一样,如果二分一次就全部去掉了,能大大提高效率,我跟面试官这么说的,他也表示同意。
cf36987
(野火春风)
12
没有improvement的意思就是 后面的评论比前面的差,或者一样,不会比前面的好