Google加面

一共两轮。

题库一武。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

题库三思铃。

alanlxl 发表于 2018-4-22 09:29
找到-b/2a之后，左右两边transform之后就是两个有序数组了
两个有序数组找合并后的第k大，是有logk的解 ...

对的对的，我也想到了LC 4 Median of two sorted Array 这里是变成了找第K大的数，思路还是用binary search的方法找两个长度，分别是 K-i 和 i，从而得到这两个小数组merge后最后那number正好就是第K大的数，感觉这题如果面试前没有理解很清楚的话，很难做的啊...

补充内容 (2018-4-25 00:11):
如果真要写的话, corner case感觉很难想得很清楚，不出错的话

nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5
对称轴  -b/2a= -1.5,  abs diff 数组相当于：nums = [   2.5, 0.5, 3.5,  5.5   ]  
方案一： Quick Select 找第K大数字的index, 比如K=3， 找到3.5，index = 2 ， O(n) 时间复杂度
方案二： Binary search 找K 大数字，相当于 search in roated sorted array O(logn) 时间复杂度
然后 把2 转变成 15 就可以了

注意四种情况
a > 0，
a < 0,
a == 0 && b >= 0,
a == 0 && b < 0

请问加面后多久给的消息啊？recruiter本来说这周一二跟我确定加面时间地点，结果人又消失了

vicky95 发表于 2018-4-20 04:21
请问加面后多久给的消息啊？recruiter本来说这周一二跟我确定加面时间地点，结果人又消失了

哦这要催催，这看他们心情。。
放心催

第二题follow up，比O(n)还要快，需要从原数组中间找到nums[i] <= -b/2a, nums[i+1]>-b/2a，从i处将数组分成前后两部分，这两部分转换后就是单调有序的，用二分查找找第k大就可以吧

alanlxl 发表于 2018-4-21 22:11
第二题follow up，比O(n)还要快，需要从原数组中间找到nums -b/2a，从i处将数组分成前后两部分，这两部分转 ...

我想你指的应该是用二分查找找到-b/2a的位置，o(logN), 然后分成两组之后应该是用two pointer类似于merge sort的方法找到第k个吧， 所以是o(logN)+o(k)
当然这里还要考虑a是否大于零的情况，甚至是等于零的一些特殊情况

BlindLockhart 发表于 2018-4-22 07:10
我想你指的应该是用二分查找找到-b/2a的位置，o(logN), 然后分成两组之后应该是用two pointer类似于merge ...

找到-b/2a之后，左右两边transform之后就是两个有序数组了
两个有序数组找合并后的第k大，是有logk的解法的，LC的第四题《两个有序数组找中位数》就可以用这个方法解决，这里有算法讲解：https://www.jianshu.com/p/9bd57fd52062

alanlxl 发表于 2018-4-22 09:29
找到-b/2a之后，左右两边transform之后就是两个有序数组了
两个有序数组找合并后的第k大，是有logk的解 ...

只不过这里两边数组的排序方向相反（一个升序一个降序），所以处理下标的时候比两个同为升序或者降序的要麻烦一些。

alanlxl 发表于 2018-4-22 09:30
只不过这里两边数组的排序方向相反（一个升序一个降序），所以处理下标的时候比两个同为升序或者降序的要 ...

了解啦，谢谢回复，我之前没有想到那个算法
算法复杂度是o(logK)还是o(logL), L是分隔之后两个数组之中较短那个的长度