详谈如何最大化利用career fair

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 2953|回复: 8
收起左侧

FB电面

[复制链接] |试试Instant~
我的人缘0
zengm321 发表于 2016-10-15 03:15:53 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (25)
 
 
3% (1)  踩

2016(10-12月) 码农类General 博士 全职@Facebook - 猎头 - 技术电面  | Other | 在职跳槽

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

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

x
刚面的。
一烙印面的,上来一道简单的题,intersection of two arrays。 看到这么简单的还挺激动,但故事肯定不是这么简单啦。
先把简单的two pointer解法写完,然后问可不可优化。尼玛,都O(m + n)了,还要咋。
于是说如果一个特长,那就binary search吧。好写完了。问如何优化? 尼玛,都mlog(n)了,还咋样啊。
于是说如果找到了,一个元素,那就用这次的index作为下次binary search的开始。可以节约掉之前的东西,不用search了。然后问,如果找不到呢,如何优化。尼玛
折腾了一会儿,说如果找不到,也返回上次search 结束的index,然后下次接着search。终于时间到了。
. from: 1point3acres 感觉要黑也是有操作空间的。
现在FB是不是喜欢问follow up, 而不是2个问题了?


上一篇:刚面完FB,感觉要跪
下一篇:Twitter coding challenge 面经
我的人缘0
wangyuesong2 发表于 2016-10-15 04:41:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (126)
 
 
5% (7)  踩
要是一个数组特别长,sort两个数组不是就要max(mlogm, nlogn)了吗,这个会比m+n快吗
回复

使用道具 举报

我的人缘0
 楼主| zengm321 发表于 2016-10-15 05:26:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (25)
 
 
3% (1)  踩
wangyuesong2 发表于 2016-10-15 04:41. from: 1point3acres
要是一个数组特别长,sort两个数组不是就要max(mlogm, nlogn)了吗,这个会比m+n快吗

说漏一点,两个数组都是sorted array
回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-16 06:20:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (61)
 
 
12% (9)  踩
"折腾了一会儿,说如果找不到,也返回上次search 结束的index,然后下次接着search",这个的意思是维护一个lastIndex变量,只有上一次找到时,才更新他是吗?面试官想要的就是这个意思?

楼主有消息了吗?
回复

使用道具 举报

我的人缘0
 楼主| zengm321 发表于 2016-10-16 23:44:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (25)
 
 
3% (1)  踩
iPhD 发表于 2016-10-16 06:20
"折腾了一会儿,说如果找不到,也返回上次search 结束的index,然后下次接着search",这个的意思是维护一个 ...

就是上一次找到了,就用这个index;如果找不到,也有一个ending index,就用那个index当starting index。. 牛人云集,一亩三分地
比如1, 89, 100, 去找90;如果不存在,那么bi search的ending index应该是89,所以下次就从那个index开始。-google 1point3acres
. 留学申请论坛-一亩三分地
我周五面的,现在没有消息。

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-16 23:48:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (61)
 
 
12% (9)  踩
zengm321 发表于 2016-10-16 23:44
就是上一次找到了,就用这个index;如果找不到,也有一个ending index,就用那个index当starting index。 ...

多谢楼主!!!不过你那个例子里如果找90,下次应该从100开始吧?就像Arrays.binarySearch里,如果找不到,会返回要插入的位置-(index + 1),index是要插入的位置,是这样吧?. 1point 3acres 论坛

祝楼主好运!!
回复

使用道具 举报

我的人缘0
 楼主| zengm321 发表于 2016-10-17 06:04:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (25)
 
 
3% (1)  踩
iPhD 发表于 2016-10-16 23:48
多谢楼主!!!不过你那个例子里如果找90,下次应该从100开始吧?就像Arrays.binarySearch里,如果找不到 ...

对。我写的就是返回要插入的index的。
但是不管返回89还是100的index都无所谓,反正只差一个,对performance没有明显影响的。
回复

使用道具 举报

我的人缘0
youto 发表于 2016-10-28 12:41:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  60% (15)
 
 
40% (10)  踩
和楼主面了同样的一道题,而且followup问的也都差不多,面试官也是三哥,估计是同一个人,多谢楼主的面经分享🙏🙏🙏🙏🙏🙏🙏🙏
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-28 13:44:48 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
Intersection of two sorted arrays: 每次binary search时,找出第一个不小于目标的index(C++ std::lower_bound),那么若没有找到,index就是下次search的起点;若找到了,index+1是新的起点。
  1. // assume vector A is longer than a
  2. vector<int> getIntersectionSorted(vector<int>& A, vector<int>& a) {
  3.   vector<int> res; // store intersection values
  4.   vector<int>::iterator pos = A.begin(); // start position of binary search
  5.   for (int x:a) {
  6.     // find position of first element which is no less than x with binary search
  7.     if ((pos = lower_bound(pos,A.end(),x)) == A.end()) return res;-google 1point3acres
  8.     else if (*pos == x) { res.push_back(x); pos++; }. 1point3acres
  9.   }
  10.   return res;
  11. }
复制代码
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-9-24 17:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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