一亩三分地论坛

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

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

Facebook电面

[复制链接] |试试Instant~ |关注本帖
Qomo 发表于 2015-2-14 04:33:25 | 显示全部楼层 |阅读模式

2015(1-3月) Other 博士 实习@Facebook - 内推 - 技术电面 |Other

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

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

x
刚刚面完Facebook的phone interview,是面的Facebook AI research的internship。一共两轮,第一轮pirate,大概问了下current research。第二轮ninja,问题如下:
(1) sparse vector dot product。follow up: what if the number of nonzero elements of one vector is 10^10 and the other is 10^2, how can you make it faster?. 1point 3acres 璁哄潧

(2) stock leetcode原题。follow up:stock II leetcode原题。another follow up: what if there are some transition fee for each transition?

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-2-18 05:02):. more info on 1point3acres.com
今天收到HR发来的offer

评分

1

查看全部评分

本帖被以下淘专辑推荐:

zhuyisong 发表于 2016-2-28 13:41:02 | 显示全部楼层
为什么第一题不用hash_map存呢, 这样follow up不是更快吗?
回复 支持 2 反对 0

使用道具 举报

又见紫风铃 发表于 2015-4-3 10:54:39 | 显示全部楼层
第一题两个vector长度不相等咋么dot product?顺便同求问18楼的问题
回复 支持 1 反对 1

使用道具 举报

ccjobhunter2011 发表于 2015-10-23 12:09:00 | 显示全部楼层
swx1031 发表于 2015-6-3 03:12
请问能不能大概说一下思路,想了半天没想出来,局部和全局怎么写呢?非常感谢

public int maxProfit(int[] prices, int[] transFee) {
    if(prices == null || prices.length == 0) {
        return 0;
    }
    int maxProfit = 0;
    for(int i=1; i < prices.length; i++) {
        int buy = prices[i-1]+transFee[i-1];
        int sell = prices-transFee[i-1];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        if(sell > buy) {
            maxProfit += sell-buy;
        }
    }   
    return maxProfit;. from: 1point3acres.com/bbs
}
回复 支持 2 反对 0

使用道具 举报

坐北朝南的学渣 发表于 2016-2-12 12:57:46 | 显示全部楼层
我觉得对于stock的follow-up,可以先找出多次transaction的区间,买的价钱用start表示,卖用end,like intervals,然后进行合并。因为每次买卖都有fee,所以要选择性合并,合并的依据是intervals[i].end-intervals[i+1].start<= transaction fee && intervals[i].end <= intervals[i+1].end. 如果interval[i].end-interval[i].start <= fee, 删除这个。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

南若冲 发表于 2015-2-14 04:37:22 | 显示全部楼层
感谢楼主
请问楼主是什么时候开始投?什么时候拿到面试的呢?
不知道后面fb的实习还有没有电面机会
回复 支持 反对

使用道具 举报

NdrZmansN 发表于 2015-2-14 04:43:06 | 显示全部楼层
有点意思.楼主能不能讲讲follow up的思路?
回复 支持 反对

使用道具 举报

zengm321 发表于 2015-2-14 07:34:15 | 显示全部楼层
第二道题的最后一个follow up,不还是进行一次交易时的结果吗? 因为要交易次数尽量少,而且锁定了min,max后,profit是一定的啊。. Waral 鍗氬鏈夋洿澶氭枃绔,
进行无限次交易没有cost,和进行一次交易,最优值一样吗?
回复 支持 反对

使用道具 举报

china_tiger 发表于 2015-2-14 11:07:35 | 显示全部楼层
那个follow up感觉应该用dp求出所有[i,j]区间内交易的最大收益,0 <= i < j < n
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-2-14 13:35:57 | 显示全部楼层
这个dot product到底是啥啊
看过好几次了?有没有解法看看
回复 支持 反对

使用道具 举报

iorisli 发表于 2015-2-14 15:07:32 | 显示全部楼层
第二题最后一个followup时间复杂度多少啊..? 想到2维DP
回复 支持 反对

使用道具 举报

ysong1pt3ac 发表于 2015-2-15 10:57:31 | 显示全部楼层
houqingniao 发表于 2015-2-14 13:35
这个dot product到底是啥啊
看过好几次了?有没有解法看看
. visit 1point3acres.com for more.
http://www.cs.cmu.edu/~scandal/cacm/node9.html
.鏈枃鍘熷垱鑷1point3acres璁哄潧
如果都是sparse vectors,那思路就是把每个vector都表示成(index, non-zero value) pairs:
A =[0,2,0,2,0,0,3,0,0,4] ==> A={(1,2), (3,2), (6,3), (9,4)}
B=[0,0,0,0,5,0,2,0,0,8]  ==> B={(4,5), (6,2), (9,8)}

for each index i,  a = val of pair (i, v_in_A), b= val of pair (i, v_in_B)
鏉ユ簮涓浜.涓夊垎鍦拌鍧. dot_product(A,B) = sum_of ( a * b )  

.鐣欏璁哄潧-涓浜-涓夊垎鍦A dot product B = 3*2 + 4*8 = 38
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-2-17 09:15:59 | 显示全部楼层
ysong1pt3ac 发表于 2015-2-15 10:57. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
http://www.cs.cmu.edu/~scandal/cacm/node9.html

如果都是sparse vectors,那思路就是把每个vector都 ...

恩懂了 多谢
回复 支持 反对

使用道具 举报

 楼主| Qomo 发表于 2015-2-18 03:46:43 | 显示全部楼层
南若冲 发表于 2015-2-14 04:37
感谢楼主. 1point3acres.com/bbs
请问楼主是什么时候开始投?什么时候拿到面试的呢?
不知道后面fb的实习还有没有电面机会

我大概去年12月找人给我投的,第一轮面试是今年一月初。
回复 支持 反对

使用道具 举报

fsc111 发表于 2015-2-28 03:51:41 | 显示全部楼层
第一题的follow up,楼主怎么解决的?
回复 支持 反对

使用道具 举报

 楼主| Qomo 发表于 2015-3-3 02:54:12 | 显示全部楼层
fsc111 发表于 2015-2-28 03:51
第一题的follow up,楼主怎么解决的?

我是用的binary search,可以从O(max(m,n))降低到O(n*log(m)), where m = max(m,n)
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-7 08:23:44 来自手机 | 显示全部楼层
就面了一轮就拿offer了??这么爽
回复 支持 反对

使用道具 举报

 楼主| Qomo 发表于 2015-3-8 00:43:35 | 显示全部楼层
北航小涵 发表于 2015-3-7 08:23
就面了一轮就拿offer了??这么爽

两轮。。请仔细读帖
回复 支持 反对

使用道具 举报

 楼主| Qomo 发表于 2015-3-8 00:45:07 | 显示全部楼层
南若冲 发表于 2015-2-14 04:37
感谢楼主
请问楼主是什么时候开始投?什么时候拿到面试的呢?
不知道后面fb的实习还有没有电面机会

我是去年12月初找人内推的。第一轮面试安排在今年一月初。HR说FAIR组的intern基本没什么位置了
回复 支持 反对

使用道具 举报

 楼主| Qomo 发表于 2015-3-8 00:45:57 | 显示全部楼层
NdrZmansN 发表于 2015-2-14 04:43
有点意思.楼主能不能讲讲follow up的思路?

第一题的follow up看12楼
回复 支持 反对

使用道具 举报

南若冲 发表于 2015-3-8 01:53:48 | 显示全部楼层
Qomo 发表于 2015-3-8 00:45
我是去年12月初找人内推的。第一轮面试安排在今年一月初。HR说FAIR组的intern基本没什么位置了

感谢分享 我也是刚拿到电面机会
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-3-30 10:52:26 | 显示全部楼层
Qomo 发表于 2015-3-2 13:54
我是用的binary search,可以从O(max(m,n))降低到O(n*log(m)), where m = max(m,n)

请教下LZ, 如果 Vector A with size m, Vector B with size n  m >> n 我们可不可以去A中找B的idx, 这样复杂度就是O(min(m, n))了 求LZ介绍下二分的思路
回复 支持 反对

使用道具 举报

likenisha 发表于 2015-3-31 04:36:05 | 显示全部楼层
两轮就offer么,不onsite么
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 00:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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