一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1741|回复: 20
收起左侧

Google电面

[复制链接] |试试Instant~ |关注本帖
plm820 发表于 2015-1-29 01:42:52 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
发个GOOGLE新鲜面经,攒个人品~
.鐣欏璁哄潧-涓浜-涓夊垎鍦
coding就问了一道题,给一个sorted array,float类型,然后给了一个二次方程ax^2+bx+c, x即给的array中元素,返回一个sorted array.
优化到时间复杂度为O(n).

评分

4

查看全部评分

Linzertorte 发表于 2015-1-29 02:11:52 | 显示全部楼层
这个就是因为抛物线有个顶点,然后两点对称。所以就是相当于将这个array分成两部分,然后离对称轴越近,越大(或者越小)。 进行mergesort里merge那在步吧。
好题。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-1-29 02:12:45 | 显示全部楼层
这个就是因为抛物线有个顶点,然后两点对称。所以就是相当于将这个array分成两部分,然后离对称轴越近,越大(或者越小)。 进行mergesort里merge那在步吧。. from: 1point3acres.com/bbs
好题。
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-1-29 02:41:51 | 显示全部楼层
应该就是这个思路了 利用对称性
回复 支持 反对

使用道具 举报

rhett.lhy 发表于 2015-1-29 03:08:01 | 显示全部楼层
没太看懂题,给一个sorted array,返回一个sorted array?什么意思?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-1-29 03:26:56 | 显示全部楼层
这种题比直接考个leetcode wildcard有意思多了。
回复 支持 反对

使用道具 举报

狂暴CNM地 发表于 2015-1-29 04:17:44 | 显示全部楼层
这不是初中数学吗。。
回复 支持 反对

使用道具 举报

combatant 发表于 2015-1-29 05:02:55 | 显示全部楼层
绝对的好题
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-1-29 05:37:14 | 显示全部楼层
狂暴CNM地 发表于 2015-1-29 04:17. 1point3acres.com/bbs
这不是初中数学吗。。

是啊。但是比直接考merge two sorted array好很多。
回复 支持 反对

使用道具 举报

hanrui_542 发表于 2015-1-29 09:37:39 | 显示全部楼层
是不是说给了一个unsorted,要输出sorted?
回复 支持 反对

使用道具 举报

gnijuohz 发表于 2015-1-29 11:10:35 | 显示全部楼层
Linzertorte 发表于 2015-1-28 11:11
这个就是因为抛物线有个顶点,然后两点对称。所以就是相当于将这个array分成两部分,然后离对称轴越近,越 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
赞~

这么一说感觉很明显,但自己要想一会才可能有这个思路
回复 支持 反对

使用道具 举报

yourway 发表于 2015-1-29 22:47:47 | 显示全部楼层
狂暴CNM地 发表于 2015-1-28 15:17
这不是初中数学吗。。

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

. more info on 1point3acres.com仔细回想了一下初中数学的解法,应该是要把原表达式变成完全平方公式吧
y =  ax^2+bx+c. 鍥磋鎴戜滑@1point 3 acres
  = a(x^2+ 2 (b/(2a)) x + (b/(2a))^2)  - a (b/(2a))^2 + c
  = a(x + b/(2a))^2 - b^2/(4a) + c
. 1point 3acres 璁哄潧
=> 抛物线的顶点坐标 x = -b/(2a), y= c - b^2/(4a)

这个初中数学的的解法太麻烦了吧。还是有简单的解法我没有想到?
回复 支持 反对

使用道具 举报

hanrui_542 发表于 2015-1-30 00:18:32 | 显示全部楼层
yourway 发表于 2015-1-29 22:47
我的第一想法是通过求导来求极值点.鏈枃鍘熷垱鑷1point3acres璁哄潧
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。有谁能准确描述一下这道题么
回复 支持 反对

使用道具 举报

yourway 发表于 2015-1-30 00:52:48 | 显示全部楼层
hanrui_542 发表于 2015-1-29 11:18. 1point3acres.com/bbs
不用这么复杂吧,因为x是sorted,找到-b/2a最近的两x,往两边阔,然后一步一步把y merge成一个sorted arr ...

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

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

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

使用道具 举报

Linzertorte 发表于 2015-1-30 02:10:03 | 显示全部楼层
yourway 发表于 2015-1-30 00:52
我对这道题的理解和你是一样的。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我发前一个贴只是关注第一步,如何求得 -b/(2a).
. From 1point 3acres bbs
高大上的calculus.
回复 支持 反对

使用道具 举报

狂暴CNM地 发表于 2015-1-30 07:43:02 | 显示全部楼层
yourway 发表于 2015-1-29 22:47
我的第一想法是通过求导来求极值点
f(x) = ax^2+bx+c
f'(x) = 2ax+b=0

恩 初中的做法是配平方得到最值点。。 不过一般都背结论吧.. 求导当然是要好算一点
回复 支持 反对

使用道具 举报

hanrui_542 发表于 2015-1-31 08:21:05 | 显示全部楼层
yourway 发表于 2015-1-30 00:52. visit 1point3acres.com for more.
我对这道题的理解和你是一样的。

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

明白了。俺们上学那会都死机硬背。
回复 支持 反对

使用道具 举报

唯一 发表于 2015-2-17 06:15:07 | 显示全部楼层
这种题可不可以直接用-b/2a呢??貌似要判断a的正负,然后两个指针从两头往中间扫。

谢谢楼主分享。。祝好运~~~
回复 支持 反对

使用道具 举报

toeflibt 发表于 2015-2-17 08:07:37 | 显示全部楼层
有要求in place么
回复 支持 反对

使用道具 举报

zhenggao1986 发表于 2015-2-19 12:55:57 | 显示全部楼层
起码分成四块来做merge。
对称轴到左右两个根,两根之外。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 18:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表