推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 5451|回复: 49
收起左侧

facebook 2面 面经

[复制链接] |试试Instant~ |关注本帖
plich 发表于 2015-10-20 07:57:32 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Other其他

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

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

x
一个俄国人,是个老员工,听不太清楚他的英语
先自我介绍,单刀直入:有哪些project和software engineering有关……然而以我的背景,只能说有关,抖搂了点带coding的项目,他不置可否


第一题,find intersection of two sorted arrays,找共同元素
two pointer迅速写了一发, O(m+n). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
follow up:如果数组一个长一个短怎么办。答:用二分搜索, mlog(n)
再follow up: 如果两个数组一样长,且一会儿sparse一会dense怎么办。这一步超级被动,基本哼哼哈哈跟随他的引导。-google 1point3acres
针对这个,他又说你可以在two pointer的扫描中内置一个切换二分搜索的机制,条件应该是什么……我继续被动……好像还把问题弄得over complex了……哭……
. from: 1point3acres.com/bbs
第二题,已知一个很大的dictionary,里面都是名字,格式是“w1 w2 w3 ... wk” 每个w都是一个string,数据结构由我设计
用户会输入 “p1 p2 ... pm”进行查询,只要查询的是某个名字的subsequence,就算match。否则不match
我用一个Trie来保存所有名字,然后设计一个map把所有w映射到trie中的节点。代码没写,问了一下复杂度,时间就到了.1point3acres缃

感觉心慌慌啊……求过求祝福啊……
ps,他跟我说这周以内recruiter会告诉我接下来的事情,这是利好面儿大么?还是要秒黑啊……

评分

4

查看全部评分

水逼一枚 发表于 2015-10-27 07:25:06 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
plich 发表于 2015-10-20 09:45. visit 1point3acres.com for more.
第一题的follow up大概意思就是:(他的例子)
v1: 1,100,200,201,...,300
v2: 1,2,...,100,300,301,.. ...

请问一下楼主,针对第一题的第二个follow up, 你要如何知道比如你当前v2处于一个dense的状态,然后v1此时是sparse的状态,然后在v2里利用二分查找找到离v1当前最近的那个元素在继续开始two pointers遍历呢?看前后元素的差值还是?
回复 支持 1 反对 0

使用道具 举报

 楼主| plich 发表于 2015-10-20 09:45:52 | 显示全部楼层
关注一亩三分地微博:
Warald
nuanuan1208 发表于 2015-10-20 09:12
楼长能不能说下第一题follow up。。。sorted array怎么一会儿sparse (0 or null的意思吗?)一会儿dense? ...

第一题的follow up大概意思就是:(他的例子)
v1: 1,100,200,201,...,300
v2: 1,2,...,100,300,301,...,500;
那么在移动v2的指针时,是不是应该在移动一会儿的时候就反过味儿来直接用二分搜索去locate 100的位置呢?

第二题是这样的,比如有个名字是
暖奻煖湪餪

输入 奻 match
输入 奻煖湪 match
输入 奻暖 不match 因为 奻的下一个不是暖(所谓顺序错了)
输入 煖餪 不match 因为 煖的下一个不是餪 (所谓漏项)
回复 支持 0 反对 1

使用道具 举报

gamespeed 发表于 2015-10-27 11:08:16 | 显示全部楼层
plich 发表于 2015-10-27 10:25. more info on 1point3acres.com
非排序怎么二分搜索……

如果两个list一个100个数据,一个有1M个数据,那么二分就会快一些

我觉得我之前脑子一直没有完全清楚……

如果是每次从较小数组M取一个元素,在大数组N中二分差找,那每次操作为O(log N),总体复杂度是O(M log N)?
回复 支持 1 反对 0

使用道具 举报

akluffy 发表于 2015-10-20 08:13:20 | 显示全部楼层
俄国人。。。不好说哦
回复 支持 反对

使用道具 举报

nuanuan1208 发表于 2015-10-20 08:56:35 | 显示全部楼层
bless楼长拿到offer!实习二面结束,“接下来的事”。。。应该就是offer?
回复 支持 反对

使用道具 举报

nuanuan1208 发表于 2015-10-20 09:02:25 | 显示全部楼层
看了下楼长第一次电面。。。印度人+俄国人。。。
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-10-20 09:09:18 | 显示全部楼层
只要查询的是某个名字的subsequence,就算match。

subsequence的定义是啥呀?

比方说w是LebronJames. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那用户输入LJ算不算subsequence呢?还是必须要substring?
回复 支持 反对

使用道具 举报

nuanuan1208 发表于 2015-10-20 09:12:55 | 显示全部楼层
楼长能不能说下第一题follow up。。。sorted array怎么一会儿sparse (0 or null的意思吗?)一会儿dense?
第二题更不知道了,还是subsequence,能不能稍微说一下?

楼长大牛啊,要是我碰到这套题就跪了。。。。。
回复 支持 反对

使用道具 举报

nuanuan1208 发表于 2015-10-20 09:59:01 | 显示全部楼层
谢谢lz,第一题有让你写码吗?还是说说思路就行?. From 1point 3acres bbs

第二题是找 p_i 有没有对应的 w_j的substring吧?
第二题假设字典size是N,每个名字的长度是n,query长度是m,按照你的算法复杂度是O(N(n+m))吧?.鐣欏璁哄潧-涓浜-涓夊垎鍦

楼长不拿到offer天理不容。。。
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-10-20 10:01:22 | 显示全部楼层
plich 发表于 2015-10-20 09:45
第一题的follow up大概意思就是:(他的例子)
v1: 1,100,200,201,...,300
v2: 1,2,...,100,300,301,.. ...

lz有个小小的疑问哈,如果是subsequence,你给的例子应该是match得。如果根据题意确实不match,那感觉应该是substring match不是subsequence
回复 支持 反对

使用道具 举报

 楼主| plich 发表于 2015-10-20 10:07:30 | 显示全部楼层
sonicgu 发表于 2015-10-20 10:01
lz有个小小的疑问哈,如果是subsequence,你给的例子应该是match得。如果根据题意确实不match,那感觉应 ...
. 1point3acres.com/bbs
subsequence这个词也是他举完这么多例子之后说的……就跟个subsequence差不多
以例子为准咯
回复 支持 反对

使用道具 举报

 楼主| plich 发表于 2015-10-20 10:13:48 | 显示全部楼层
nuanuan1208 发表于 2015-10-20 09:59. Waral 鍗氬鏈夋洿澶氭枃绔,
谢谢lz,第一题有让你写码吗?还是说说思路就行?

第二题是找 p_i 有没有对应的 w_j的substring吧?

follow up是说思路就行……或者说他本来期待我有码的……

可能我中文例子举得不好,"tom marvolo riddle":w1 是 tom w2是 marvolo w3是riddle
查询的东西能match这一个词组的话得是 w1; w2 ;w3; w1w2; w2w3; w1w2w3 这六种之一

其实枚举做成一个unordered_set也可以,就是空间看着好恐怖……
查询一个词组是复杂度是O(ml) m是第一节字串在trie里面的出现次数, l是 词组的单词数
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-10-22 06:55:16 | 显示全部楼层
楼主有回信了吗
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-10-22 06:56:47 | 显示全部楼层
再弱弱的问一下,关于数组一会稀疏一会儿dense,有没有写代码还是说就是讨论了一下思路呢?
回复 支持 反对

使用道具 举报

 楼主| plich 发表于 2015-10-22 07:47:56 | 显示全部楼层
JamesJi 发表于 2015-10-22 06:56
再弱弱的问一下,关于数组一会稀疏一会儿dense,有没有写代码还是说就是讨论了一下思路呢?

讨论了一下思路……他想让我写……. 1point3acres.com/bbs
我起了点儿头,他就nonono……然后就只好继续讨论思路了……

第二天就有反馈……加了一轮……
回复 支持 反对

使用道具 举报

nuanuan1208 发表于 2015-10-22 07:55:17 | 显示全部楼层
楼长这么强竟然被加面了,看了心慌慌啊。。。
回复 支持 反对

使用道具 举报

哭泣的北燕 发表于 2015-10-22 08:13:46 | 显示全部楼层
内推3天之后就被拒,连个面试机会都没有的飘过。。。
回复 支持 反对

使用道具 举报

gamespeed 发表于 2015-10-26 23:48:35 | 显示全部楼层
第一题我觉得可以用set来做,把短的array放入set,然后遍历长的array,每次检查元素是否在set中。好奇为啥没人提到这个。. 1point3acres.com/bbs

第二题的Trie要保存的不光是每个W,还有他们的所有substring
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-10-27 00:20:18 | 显示全部楼层
plich 发表于 2015-10-20 10:13
follow up是说思路就行……或者说他本来期待我有码的……

可能我中文例子举得不好,"tom marvolo ridd ...

现在的实习面试已经这么难了啊。
请问楼主,第二题的话,应该在LC Add and Search Word的基础上做啥改进呢?

补充内容 (2015-10-27 00:25):
感觉每一个word,需要存其所有的substring啊,
回复 支持 反对

使用道具 举报

 楼主| plich 发表于 2015-10-27 00:22:24 | 显示全部楼层
gamespeed 发表于 2015-10-26 23:48
第一题我觉得可以用set来做,把短的array放入set,然后遍历长的array,每次检查元素是否在set中。好奇为啥 ...

那样的话你的空间是O(m) 时间是O(n). Waral 鍗氬鏈夋洿澶氭枃绔,
真的有短array的话可以直接二分搜,空间是O(1) 时间是O(mlog(n)) 如果m远小于n的话直接二分多合适
回复 支持 反对

使用道具 举报

 楼主| plich 发表于 2015-10-27 00:23:13 | 显示全部楼层
小A要当码农 发表于 2015-10-27 00:20
现在的实习面试已经这么难了啊。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
请问楼主,第二题的话,应该在LC Add and Search Word的基础上做啥改进 ...

跟LC上面的题不是一个意思……
这个题不考虑往字典里面添加新的人名的环节,而且search的方法也不一样
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-17 01:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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