Google电面

发个GOOGLE新鲜面经，攒个人品~

codi

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

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

优化到时间复杂度为O(n).

狂暴CNM地 发表于 2015-1-28 15:17
这不是初中数学吗。。

我的第一想法是通过求导来求极值点
f(x) = ax^2+bx+c
f'(x) = 2ax+b=0
=> x = -b/(2a)

仔细回想了一下初中数学的解法，应该是要把原表达式变成完全平方公式吧
y =  ax^2+bx+c
  = a(x^2+ 2 (b/(2a)) x + (b/(2a))^2)  - a (b/(2a))^2 + c
  = a(x + b/(2a))^2 - b^2/(4a) + c

=> 抛物线的顶点坐标 x = -b/(2a), y= c - b^2/(4a)

这个初中数学的的解法太麻烦了吧。还是有简单的解法我没有想到？

yourway 发表于 2015-1-29 22:47
我的第一想法是通过求导来求极值点
f(x) = ax^2+bx+c
f'(x) = 2ax+b=0

不用这么复杂吧，因为x是sorted，找到-b/2a最近的两x，往两边阔，然后一步一步把y merge成一个sorted arry。

不知道这道题是不是说给定sorted x array，通过二次方程求一个sorted y array。有谁能准确描述一下这道题么

hanrui_542 发表于 2015-1-29 11:18
不用这么复杂吧，因为x是sorted，找到-b/2a最近的两x，往两边阔，然后一步一步把y merge成一个sorted arr ...

我对这道题的理解和你是一样的。

我发前一个贴只是关注第一步，如何求得 -b/(2a).

是因为楼上有朋友说这是初中数学，但是按我的理解，用初中数学求极值点不如用微积分简单。

这个就是因为抛物线有个顶点，然后两点对称。所以就是相当于将这个array分成两部分，然后离对称轴越近，越大（或者越小）。 进行mergesort里merge那在步吧。
好题。

这个就是因为抛物线有个顶点，然后两点对称。所以就是相当于将这个array分成两部分，然后离对称轴越近，越大（或者越小）。 进行mergesort里merge那在步吧。
好题。

应该就是这个思路了 利用对称性

没太看懂题，给一个sorted array，返回一个sorted array？什么意思？

这种题比直接考个leetcode wildcard有意思多了。

这不是初中数学吗。。

绝对的好题

狂暴CNM地 发表于 2015-1-29 04:17
这不是初中数学吗。。

是啊。但是比直接考merge two sorted array好很多。

是不是说给了一个unsorted，要输出sorted？