一亩三分地论坛

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

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

Facebook onsite

[复制链接] |试试Instant~ |关注本帖
ccgogo123 发表于 2014-10-31 03:33:25 | 显示全部楼层 |阅读模式

2013(10-12月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Fail

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

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

x
四轮技术面试,每轮四十五分钟。每一轮先聊简历十到十五分钟,接下来做题,最后留下五分钟问问题。
1st: Given a m * n grid and the coordination of left bottom cell is (1, 1) and the one of right top cell is (m, n). At each cell say (x, y), you have to choice to move, going up or right. If you go up, the destination is (x, x+ y). Otherwise your destination is (x + y, y). Find the minimum number of steps to reach the cell (m, n) from (1, 1).

2nd: Find k closest number in an array of a given value. 1point3acres.com/bbs

3rd: Leecode minimum window

4th: Check if a tree is BST

-google 1point3acres

评分

4

查看全部评分

Arthur2012 发表于 2014-10-31 03:43:07 | 显示全部楼层
lz你好,我想印证下我对第二题的理解,是求在一个array里面第k个最接近given value 的数对吗?
解法因为和求第k大的数一样,维护一个大小为k 的heap,对吗?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
谢谢啦!
回复 支持 反对

使用道具 举报

 楼主| ccgogo123 发表于 2014-10-31 03:55:52 | 显示全部楼层
不是第k个,是前k个。的确用heap。
回复 支持 反对

使用道具 举报

22691482 发表于 2014-10-31 04:07:33 | 显示全部楼层
这个题貌似都比较简单啊。。。
回复 支持 反对

使用道具 举报

王可雪 发表于 2014-10-31 04:26:45 | 显示全部楼层
array.map(abs(self - given number))
Then use min heap
回复 支持 反对

使用道具 举报

nostal 发表于 2014-10-31 04:46:30 | 显示全部楼层
看起来并不难,好好准备应该可以crack
回复 支持 反对

使用道具 举报

小白too 发表于 2014-10-31 05:02:46 | 显示全部楼层
22691482 发表于 2014-10-31 04:07
这个题貌似都比较简单啊。。。

第一题是dp么。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2014-10-31 05:19):
好吧,我想多了。。bfs就行
回复 支持 反对

使用道具 举报

ohmystill 发表于 2014-10-31 05:06:52 | 显示全部楼层
貌似 都很简单
回复 支持 反对

使用道具 举报

psyclaudeZ 发表于 2014-10-31 06:36:06 | 显示全部楼层
第二题如果不需要结果有序的话堆都用不着……直接上selection algorihtm, 选出跟target差绝对值第k大元素,然后返回A[0]到A[k - 1]就好了……O(n)时间,O(1)额外空间……

回复 支持 反对

使用道具 举报

 楼主| ccgogo123 发表于 2014-10-31 07:17:54 | 显示全部楼层
psyclaudeZ 发表于 2014-10-31 06:36
第二题如果不需要结果有序的话堆都用不着……直接上selection algorihtm, 选出跟target差绝对值第k大元素, ...

没错,有个朋友面另外一家公司,要求返回前k小的元素,不许用heap,就要用quickselect。
回复 支持 反对

使用道具 举报

linuxcoder 发表于 2014-10-31 08:14:43 | 显示全部楼层
lz第一题越界了怎么处理,如果比n大就算n吗
回复 支持 反对

使用道具 举报

 楼主| ccgogo123 发表于 2014-10-31 08:34:06 | 显示全部楼层
linuxcoder 发表于 2014-10-31 08:14
lz第一题越界了怎么处理,如果比n大就算n吗

某个方向越界,就代表不能朝这个方向移动。不好意思,漏了这个信息。
回复 支持 反对

使用道具 举报

austurela 发表于 2014-10-31 08:34:26 | 显示全部楼层
lz多久得到结果回复的?
回复 支持 反对

使用道具 举报

byrlhb 发表于 2014-10-31 09:07:59 | 显示全部楼层
第二题用找第K个数的方法可能做。。。哎,今天面facebook估计是挂了
回复 支持 反对

使用道具 举报

22691482 发表于 2014-11-5 05:27:34 | 显示全部楼层
psyclaudeZ 发表于 2014-10-31 06:36
第二题如果不需要结果有序的话堆都用不着……直接上selection algorihtm, 选出跟target差绝对值第k大元素, ...

你好, “选出跟target差绝对值第k大元素” 这个怎么实现?
回复 支持 反对

使用道具 举报

smzfeng 发表于 2014-11-5 05:33:00 | 显示全部楼层
这是哪个办公室啊 CA?
回复 支持 反对

使用道具 举报

22691482 发表于 2014-11-5 05:46:18 | 显示全部楼层
先根据target把数组换成diff (in place).
然后用quick select 找到the kth smallest.
然后再partition
然后恢复数组。
回复 支持 反对

使用道具 举报

 楼主| ccgogo123 发表于 2014-11-8 01:54:42 | 显示全部楼层
smzfeng 发表于 2014-11-5 05:33. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这是哪个办公室啊 CA?

对啊。不过已经跪了。
回复 支持 反对

使用道具 举报

smzfeng 发表于 2014-11-8 03:36:23 | 显示全部楼层
ccgogo123 发表于 2014-11-7 12:54
对啊。不过已经跪了。

跪的原因是什么?没做出来还是?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 13:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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