传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1185|回复: 6
收起左侧

热乎乎的 Zenefits Fulltime Phone Interview

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
刚来的Zenefits电面, 可能是个白人小哥. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
上来先问了Behavior问题,然后做题

题目好像之前有人发过,类似 LeetCode 3Sum Smaller
一个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找所有的对,然后数一下有多少个
小哥说,好,写一下. visit 1point3acres.com for more.

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

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

然后小哥让我问他俩问题 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后就结束了

求RP啊啊啊啊,. From 1point 3acres bbs
. From 1point 3acres bbs




补充内容 (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上是去重的
. Waral 鍗氬鏈夋洿澶氭枃绔,
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. Waral 鍗氬鏈夋洿澶氭枃绔,
Array里边的元素是distinct的

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-23 17:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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