一亩三分地论坛

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

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

热乎乎的 Zenefits Fulltime Phone Interview

[复制链接] |试试Instant~ |关注本帖
lcl3356897 发表于 2015-10-31 07:05:02 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Zenefits - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚来的Zenefits电面, 可能是个白人小哥
上来先问了Behavior问题,然后做题

题目好像之前有人发过,类似 LeetCode 3Sum Smaller. 鍥磋鎴戜滑@1point 3 acres
一个array里有N个非负不重复的整数,找 a + b <= X 的对 (a, b)有多少个

比如{1, 2, 5, 7}, 7  那么就有3个对  (1, 2) (1, 5) (2, 5)

我说先排序,尽管大哥给的数组是有序的,然后双指针查找,时间复杂度是O(nlgn + n)
小哥说,好,写一下

然后小哥说你怎么知道你的答案是对的,怎么写Unit Test,我说那就naive way找所有的对,然后数一下有多少个
小哥说,好,写一下. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

然后小哥说输入怎么办,我说那就随机数来产生array的元素,给了个范围是0~10^6
小哥说,好,写一下

然后小哥说X怎么办,我说从0到10^6都试一遍. more info on 1point3acres.com
小哥说,不用,就用array里数的范围,就是min到2*max
我说,好,我写一下。。。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后小哥说再给你个条件,X <= 100 * N 的话你怎么改进你的算法
我说,....(过了好久).... 没思路,小哥你给我个提示
小哥说,你原来的方法里边最耗时的是啥
我说,排序
小哥说,怎么改进. 鍥磋鎴戜滑@1point 3 acres
我说,我知道桶排序和计数排序都是O(n)
小哥说,这样的话你怎么利用 X <= 100 * N 这个条件
我说,....(过了好久).... 每次比较桶的最大值max, 如果2 * max <= X 的话,前面的每两个数都可以成对,就不用重复计算了,然后...(其实我在瞎编). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
小哥说,Exactly! 就是这个意思
我就无言以对了。。。

然后小哥让我问他俩问题
然后就结束了. Waral 鍗氬鏈夋洿澶氭枃绔,

求RP啊啊啊啊,


. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


补充内容 (2015-11-3 08:52):
下午收到邮件,已跪

评分

2

查看全部评分

seonghae 发表于 2015-10-31 08:23:49 | 显示全部楼层
楼主请问重复的算一对还是两对?比如1,1, 2, 5, 7 要去重还是不去重?Leetcode上是去重的
回复 支持 反对

使用道具 举报

seonghae 发表于 2015-10-31 08:24:26 | 显示全部楼层
我指结果要不要去重呢?
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2015-10-31 08:24:49 | 显示全部楼层
seonghae 发表于 2015-10-31 08:23
楼主请问重复的算一对还是两对?比如1,1, 2, 5, 7 要去重还是不去重?Leetcode上是去重的

Array里边的元素是distinct的
回复 支持 反对

使用道具 举报

hello2pig 发表于 2015-10-31 08:29:24 | 显示全部楼层
同我google onsite 的第二面。。只不过换成了乘积  不断的follow up
回复 支持 反对

使用道具 举报

seonghae 发表于 2015-10-31 08:40:31 | 显示全部楼层
lcl3356897 发表于 2015-10-31 08:24
Array里边的元素是distinct的

ok了解了。X <= 100 * N 这个条件怎么用呢想不出来啊
回复 支持 反对

使用道具 举报

seonghae 发表于 2015-10-31 08:42:34 | 显示全部楼层
X <= 100 * N 是不是用来限定桶排序的范围呢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 08:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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