一亩三分地论坛

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

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

G家店面

[复制链接] |试试Instant~ |关注本帖
pineapple1985 发表于 2016-8-26 05:20:50 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
最近刚店面G家, 还没有结果。 发个面经挣RP。
给定一个 sorted array (e.g., x= [-2 , 0 ,2]) 与一个一元二次方程  y= a*x^2 + b*x + c (a, b, c是常数, a != 0)。 返回排好序的y array.

还给了对称轴的方程 x= -b/(2a)
.鐣欏璁哄潧-涓浜-涓夊垎鍦
一开始以为对称轴需要用。我就按对称轴对x分成左右两组(一组就是在对称轴左边, 另外一组在右边)算出两组y值。 两组y值数组分别有序,再做merge。这样的话需要对两次数组, 一次是读x数组是算两组y值, 第二次是读y数组然后merge.
. 鍥磋鎴戜滑@1point 3 acres
后来问能不能用复杂度 1*n 而不是 2*n

后来才想到只需要对x数组用两个pointer, 初始是一个是在开始(i = 0),一个在结尾(j = n -1), 读两个x值,然后算y值, 比较后依次直接存到结果数组。

写完后时间差不多到了。

听口音,面试官应该是华人mm.

是不是面一道题就差不多要跪了?

评分

2

查看全部评分

llatjob 发表于 2016-8-27 04:17:44 | 显示全部楼层
不能从两边扫,因为对称轴不一定在中间。要先找到对称轴,然后在往两边扫
回复 支持 0 反对 1

使用道具 举报

whitney94 发表于 2016-8-26 08:19:08 | 显示全部楼层
我觉得是不是要先判断a的大小,如果a大于0,说明最小值在对称轴,然后从对称轴往两边两个pointer的排y的值;如果a小于0,那两遍最小,从两遍往中间排就可以了
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-8-26 08:48:05 来自手机 | 显示全部楼层
都是从两边扫。对于a>0的时候,merge是从大是到小。a<0的时候,merge是从小到大
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-8-27 05:51:58 来自手机 | 显示全部楼层
不需要找对称轴的,就是所有的x坐标都在对称轴的一侧也是没问题的。就是只有一个指针变化而已。不会交替
回复 支持 反对

使用道具 举报

eins1179 发表于 2016-8-27 05:57:20 | 显示全部楼层
是LC原题 判断a大小然后从前往后填 或者从后往前填就好了。 祝LZ好运
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-8-27 06:31:37 来自手机 | 显示全部楼层
嗯,是这个思路的。当时一开始没想到这个思路,后来才想到。请问哪个题号?居然没印象有刷过。
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-8-27 06:31:43 来自手机 | 显示全部楼层
嗯,是这个思路的。当时一开始没想到这个思路,后来才想到。请问哪个题号?居然没印象有刷过。
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-8-27 06:35:17 来自手机 | 显示全部楼层
eins1179 发表于 2016-8-27 05:57
是LC原题 判断a大小然后从前往后填 或者从后往前填就好了。 祝LZ好运

觉得是sort transformed array. 加锁题,难怪没印象。其实题目不难,怪自己一开始没想到最优解。
回复 支持 反对

使用道具 举报

Ridingstar01 发表于 2016-8-27 12:19:25 | 显示全部楼层
llatjob 发表于 2016-8-27 04:17
不能从两边扫,因为对称轴不一定在中间。要先找到对称轴,然后在往两边扫

可以从两边扫,找到left 和right到x轴的距离,把大(小)的那个放到res里边。相当就都放。
回复 支持 反对

使用道具 举报

Olivialoveslife 发表于 2016-8-27 13:00:00 | 显示全部楼层
电面一个多礼拜了还是没消息,lz等了多久了?
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-8-27 13:04:33 | 显示全部楼层
这是G面筋lc360 sort transformed array
回复 支持 反对

使用道具 举报

 楼主| pineapple1985 发表于 2016-8-27 20:39:56 来自手机 | 显示全部楼层
Olivialoveslife 发表于 2016-8-27 13:00
电面一个多礼拜了还是没消息,lz等了多久了?

还没几天。祝大家好运
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-22 04:13:08 | 显示全部楼层
llatjob 发表于 2016-8-27 04:17
不能从两边扫,因为对称轴不一定在中间。要先找到对称轴,然后在往两边扫

可以从两边扫
回复 支持 反对

使用道具 举报

ericlee27 发表于 2016-9-24 09:16:26 | 显示全部楼层
corner case是 a=0 然后根据a的大小来判断搜索的方向 a>0越靠近对称轴越小 a < 0越靠近对称轴越大
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 18:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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