一亩三分地论坛

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

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

Zenefits 二面

[复制链接] |试试Instant~ |关注本帖
tianshaobo47 发表于 2015-11-26 07:21:48 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Zenefits - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x
刚刚结束的SKYPE二面,没做出来,必然已经跪了。

Skype上来是个印度小哥,以为要被坑。但是其实小哥人很好,一直提醒我,可惜自己太渣,哎。。
. From 1point 3acres bbs
input 是一个数组。
比如[1, 4, 10, 50, 60, 44, 32,] 返回66
再比如[55, 33, 22, 11, 13, 44] 返回11
再比如[1, 4, 9, 11, 22, 33]返回 -1;
就是中间有一个turing point, 没有的话返回-1;.1point3acres缃
要求log N 解决。。
. 1point 3acres 璁哄潧
最后没做出来小哥给了答案。。其实不太难。只怪自己渣 啊

发个面经造福后人。

评分

1

查看全部评分

水逼一枚 发表于 2015-11-26 07:30:54 | 显示全部楼层
是不是就是类似二分啊?
回复 支持 反对

使用道具 举报

sanguine 发表于 2015-11-26 08:11:57 | 显示全部楼层
第一个为啥返回的是66?
回复 支持 反对

使用道具 举报

 楼主| tianshaobo47 发表于 2015-11-26 13:44:21 | 显示全部楼层
sanguine 发表于 2015-11-26 08:11
第一个为啥返回的是66?

60.. 不好意思
回复 支持 反对

使用道具 举报

 楼主| tianshaobo47 发表于 2015-11-26 13:44:42 | 显示全部楼层
水逼一枚 发表于 2015-11-26 07:30
是不是就是类似二分啊?

对啊,要么怎么logN啊。
回复 支持 反对

使用道具 举报

Cherubic_girl 发表于 2016-2-5 03:03:59 | 显示全部楼层
有个方法就是一个boolean 先判断这个sequence是递增先还是递减先, 递增就找最大值,递减就找最小值,没有就-1。但是有个前提是turn number不能有duplicates。。啊好麻烦啊。。估计面到要问清楚很多requirement
回复 支持 反对

使用道具 举报

pharrell 发表于 2016-2-5 17:06:47 | 显示全部楼层
先判断递增或递减没错。这题其实就是binary search的变形。我的方法类似于maintain一个size为3的sliding window,left = 0,right = n - 1, 先找到整个array的median=>m,
(1)if array[m] > array[m-1] && array[m] > array[m+1] || array[m] < array[m-1] && array[m] < array[m+1] => return array[mid],说明array[mid]为这三个数的极大或极小值,即turning point
. 1point 3acres 璁哄潧(2)如果整个array是先递增再递减的话(如果turning point存在):1)如果 array[m] > array[m-1] && array[m] < array[m+1],即sliding window is in ascending order,我们可以discard array[m]左边的numbers,update left => m;else update right => m. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
(3)反之如果整个array是先递减再递增的话(如果turning point存在):1)如果 array[m] < array[m-1] && array[m] > array[m+1],即sliding window is in descending order,我们可以discard array[m]左边的numbers,update left => m;else update right => m
(4)如果 right <= left + 1,此时size of sliding window < 3,停止循环,return -1. From 1point 3acres bbs
用LZ的 example为例: array = [55, 33, 22, 11, 13, 44],可知这个array是先递减的,array[m-1] = 33,array[m] = 22, array[m+1] = 11,满足上述(3)里的1),left = m。接下来,array[m-1] = 33,array[m] = 11, array[m+1] = 13, 满足(1),即array[m]为turning point,return array[m]。
自己create了几种情况的test case,用code测试了一下发现没有问题。欢迎讨论:-p
回复 支持 反对

使用道具 举报

pharrell 发表于 2016-2-5 20:04:06 | 显示全部楼层
Cherubic_girl 发表于 2016-2-5 03:03
有个方法就是一个boolean 先判断这个sequence是递增先还是递减先, 递增就找最大值,递减就找最小值,没有 ...

按turning point 的定义应该不包含重复的。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 08:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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