一亩三分地论坛

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

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

热乎乎的facebook一面

[复制链接] |试试Instant~ |关注本帖
liuyue952 发表于 2015-11-6 11:00:11 | 显示全部楼层 |阅读模式

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

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

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

x
下午刚刚面完,发到地里回馈大家。面的不好,求人品
面试官是东欧人,在Site Integrity Infrastructure team。上题目。

Given一个unsorted array, find the greatest natural number N, such that, there exists at least N numbers in the array which are greater or equal to N. From 1point 3acres bbs
比如input是【5,5,5】的话,output是3

我先给的最简单的解法,sort array,然后从最大开始找起,就是O(nlogn),然后面试官问我有没有O(n)的解法。
我当时跟他说的是类似quick sort的方法,找一个pivot,然后看看需要把多少大于他的数移到右边。如果那个number正好等于pivot的值的话,循环终止。不然的话,如果pivot大于移到右边的个数的话,在pivot左边找,反之在右边找。
现在想一想这个方法应该是妥妥可以O(n)完成的(终止条件还需要再想想),因为每比较一次一半的数就不用考虑了,然并卵。。。他打断跟我说觉得这个解法太复杂,我们来想一想能不能把sort变成O(n)的。
他说假如我告诉你这个array所有integer的值都在【-2N,2N】之间呢?N=array_length。我说count sort,于是就O(n)了。然后他说好吧,你写。写了大概有三到五分钟。然后他说,那么现在我们去除这个假设怎么办?当时一看时间不到五分钟脑袋是懵的,没get到他整个在往哪里走。。。他就提示我,如果array里面数的值都比N大的话你的结果是不是总是N?是不是所有大于等于N的数不用区分了?额,等我反应过来他已经没耐心了。其实他意思就是count sort加点小小改动,因为所有小于0的数都不用跟0区分了,所有大于N的数也都不用跟N区分了

. from: 1point3acres.com/bbs
感觉已跪,智商捉急加紧张,这种没遇到的题会慌,不能集中精神思考。。。求人品爆发至少再给个二面吧
.1point3acres缃
Augustus 发表于 2015-11-6 11:10:10 | 显示全部楼层
既然都用count sort为什么不直接用set存...
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-11-6 11:18:37 | 显示全部楼层
感觉这个面试官不走寻常路啊
回复 支持 反对

使用道具 举报

 楼主| liuyue952 发表于 2015-11-6 11:20:10 | 显示全部楼层
haifengc 发表于 2015-11-6 11:18. 鍥磋鎴戜滑@1point 3 acres
感觉这个面试官不走寻常路啊

哎人品啊。。。
回复 支持 反对

使用道具 举报

mooc 发表于 2015-11-6 11:22:38 | 显示全部楼层
这是h index问题吧,leetcode有原题的
回复 支持 反对

使用道具 举报

cocaptainco 发表于 2015-11-6 11:27:34 | 显示全部楼层
楼主我是周二面的,也面的不咋地。。。还没消息呢,话说你recruiter是Philipp吗,有update跟我说声呗
回复 支持 反对

使用道具 举报

 楼主| liuyue952 发表于 2015-11-6 11:28:02 | 显示全部楼层
mooc 发表于 2015-11-6 11:22
这是h index问题吧,leetcode有原题的

嗯是的,谢谢提醒
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-11-6 11:29:12 | 显示全部楼层
看看这个算法可以不:(如果所有的数都是整数)
(1) count the number of integers that large or equal to n  (n is the size of the array).鐣欏璁哄潧-涓浜-涓夊垎鍦
(2) go through the array, if the integer is negative, skip it, else if the number is less than n, swap(num[i], num[num[i]])
(3) then from the end of array, count the number of integers large or equal to the index
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-11-6 14:24:47 | 显示全部楼层
说实话,这题,算是比较简单的 基数排序的应用了。楼主,继续努力
回复 支持 反对

使用道具 举报

snowwolf 发表于 2015-11-6 15:46:20 | 显示全部楼层
mooc 发表于 2015-11-6 11:22
这是h index问题吧,leetcode有原题的

这题并不是h-index,两者有明显区别

补充内容 (2015-11-6 15:53):
好吧,好像是同一个,我看错了
回复 支持 反对

使用道具 举报

 楼主| liuyue952 发表于 2015-11-6 23:15:34 | 显示全部楼层
cocaptainco 发表于 2015-11-6 11:27
楼主我是周二面的,也面的不咋地。。。还没消息呢,话说你recruiter是Philipp吗,有update跟我说声呗
. From 1point 3acres bbs
不是philipp,应该是个女生。好的,大家加油啊
回复 支持 反对

使用道具 举报

 楼主| liuyue952 发表于 2015-11-6 23:17:05 | 显示全部楼层
haifengc 发表于 2015-11-6 11:29
看看这个算法可以不:(如果所有的数都是整数)
(1) count the number of integers that large or equal to  ...

不好意思不是特别懂你的解法,举个例子?
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-11-7 01:29:30 | 显示全部楼层
liuyue952 发表于 2015-11-6 23:17
不好意思不是特别懂你的解法,举个例子?

比如说:

6 4 34 4 -1 5

n = 6

然后大于等于6的数是2个
之后再用一个指针从左到右
6 4 34 4 -1 5 (大于等于6,改为-1,因为已经统计过)
-1 3 34 4 -1 5 (3和index为3的交换,得到下面的)
-1 4 34 3 -1 5 (3 和index为4的交换). more info on 1point3acres.com
-1 -1 34 3 4 5 之后都换完了
. from: 1point3acres.com/bbs
然后从右开始,
5有3个数大于5. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
4 有4个数大于等于4
所以结果是4. from: 1point3acres.com/bbs

.鐣欏璁哄潧-涓浜-涓夊垎鍦
. more info on 1point3acres.com
3 4 34 3 -1 5
3 -1 34 3 4 5
3 -1 -1 3 4 5.1point3acres缃
. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

喜马拉雅疯子 发表于 2015-11-22 00:26:49 | 显示全部楼层
这道题可以用leetcode H-index的方法做啦
首先咱们可以确定,这个要找的自然数最大只能是输入数组(假设是nums)的长度
所以咱么可以吧数组中大于这个长度的数都放在最后,对于负数同理
步骤如下:
1)建立一个新数组,长度为nums.length + 1
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 2)扫描nums,当前访问的数字为number
如果当前的数字小于等于零,则times(0)++
如果当前数字大于等于nums.length 则times(nums.length)++
否则times(number)++
3)然后从times的尾部向前扫描,如果当前的index<=(times在index之后的总和加上times(index))那么就找到了这个数N
4)否则返回零
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 13:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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