一亩三分地论坛

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

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

facebook一面跪经

[复制链接] |试试Instant~ |关注本帖
li3939108 发表于 2016-3-3 07:08:51 | 显示全部楼层 |阅读模式

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

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

x
第一次coding interview就面facebook,结果面挂了。发个面经攒人品。面完自我感觉良好,facebook西雅图office的一个三哥面的。第二天就发信问recruiter结果,然后就告诉我挂了。
上来先三哥先自我介绍了一下,楼主填preferred联系方式时脑残填了各skype,结果那天正好家里wifi信号不太好,听得模模糊糊。
. from: 1point3acres.com/bbs
然后是让我介绍一下我在做啥,就简单说了一下。大概过去了十分钟,然后开始coding。

第一题sparse vector dot product,跟这个帖子差不多http://www.1point3acres.com/bbs/thread-165666-1-1.html , 画风也差不多,各种讨论,代码也是只写了个框架。. more info on 1point3acres.com
楼主之前看过这题,但没仔细看,上来也写了O(mn)的解法,写完发现好像可以优化,就自己改成了O(max(m,n))的解法。然后就问我这个解法如果一个vector非常大可能会有什么问题,我说可能没有空间存储,然后他说不是这个问题,现在服务器内存都很大bla bla,然后继续问怎么改进,楼主这时终于想明白了,就说那个大的可以用hashmap去存,然后复杂度就是O(min(m,n)) 了。然后这题就放我过了。

第二题,也很简单,说是有K各排好序的数组N1,N2, ... ... ,Nk,要合并成一个,仍然是sorted,楼主说这不就是merge sort吗,三哥说嗯是,让我具体说一下。楼主本科不是CS的,就大概知道有merge sort 这么回事,具体怎么merge 怎么sort也不太记得了,然后就懵逼了,说是先把N1 和 N2合并了,然后one by one继续往下合并,然后三哥就问我这样复杂度是啥,我说两个好像是O(n1 + n2)。N个情况楼主算了一会儿,说好像是O( sum_j  (k - j) Nj ),然后三哥说这就是 O( k^2 max(Nk) )。然后问我还有啥办法,这会儿楼主总算又想明白了merge sort是怎么回事,说比如有N1,N2,N3,N4,可以先算r1=merge(N1,N2), r2 = merge(N3,N4), 然后就可以得到 r = merge(r1, r2). 这样复杂度就是 O(k log k max (NK))了,三哥表示是这样。然后,时间差不多了,三哥说不用写code了,这题就结束了。


然后就让我问问题,我问了下他是在哪个组的,他说他是在西雅图做monitoring的,具体monitoring啥,wifi信号比较差,也没太明白,说这个东西比较无聊,你可能不会感兴趣,然后又扯了一会儿之前他干过啥啥高大上的东西,好像是server 的power management。然后就结束了。


估计是三哥觉得TM merge sort你都还没整明白,赶紧滚。。。. from: 1point3acres.com/bbs
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

1

查看全部评分

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 01:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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