一亩三分地论坛

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

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

facebook 2面 面经

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

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

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

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

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

第一题,find intersection of two sorted arrays,找共同元素. Waral 鍗氬鏈夋洿澶氭枃绔,
two pointer迅速写了一发, O(m+n)
follow up:如果数组一个长一个短怎么办。答:用二分搜索, mlog(n)
再follow up: 如果两个数组一样长,且一会儿sparse一会dense怎么办。这一步超级被动,基本哼哼哈哈跟随他的引导。
针对这个,他又说你可以在two pointer的扫描中内置一个切换二分搜索的机制,条件应该是什么……我继续被动……好像还把问题弄得over complex了……哭……

第二题,已知一个很大的dictionary,里面都是名字,格式是“w1 w2 w3 ... wk” 每个w都是一个string,数据结构由我设计
用户会输入 “p1 p2 ... pm”进行查询,只要查询的是某个名字的subsequence,就算match。否则不match
我用一个Trie来保存所有名字,然后设计一个map把所有w映射到trie中的节点。代码没写,问了一下复杂度,时间就到了. From 1point 3acres bbs

感觉心慌慌啊……求过求祝福啊……. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
ps,他跟我说这周以内recruiter会告诉我接下来的事情,这是利好面儿大么?还是要秒黑啊……

评分

4

查看全部评分

水逼一枚 发表于 2015-10-27 07:25:06 | 显示全部楼层
plich 发表于 2015-10-20 09:45
第一题的follow up大概意思就是:(他的例子)
v1: 1,100,200,201,...,300. From 1point 3acres bbs
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 | 显示全部楼层
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的位置呢?. 鍥磋鎴戜滑@1point 3 acres
. 鍥磋鎴戜滑@1point 3 acres
第二题是这样的,比如有个名字是. 1point 3acres 璁哄潧
暖奻煖湪餪

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

使用道具 举报

gamespeed 发表于 2015-10-27 11:08:16 | 显示全部楼层
plich 发表于 2015-10-27 10:25
非排序怎么二分搜索……. 鍥磋鎴戜滑@1point 3 acres

如果两个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,第一题有让你写码吗?还是说说思路就行?
. 1point 3acres 璁哄潧
第二题是找 p_i 有没有对应的 w_j的substring吧?.1point3acres缃
第二题假设字典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,那感觉应 ...

subsequence这个词也是他举完这么多例子之后说的……就跟个subsequence差不多. From 1point 3acres bbs
以例子为准咯
回复 支持 反对

使用道具 举报

 楼主| plich 发表于 2015-10-20 10:13:48 | 显示全部楼层
nuanuan1208 发表于 2015-10-20 09:59
谢谢lz,第一题有让你写码吗?还是说说思路就行?

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

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

可能我中文例子举得不好,"tom marvolo riddle":w1 是 tom w2是 marvolo w3是riddle.1point3acres缃
查询的东西能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,有没有写代码还是说就是讨论了一下思路呢?

讨论了一下思路……他想让我写……
我起了点儿头,他就nonono……然后就只好继续讨论思路了……. Waral 鍗氬鏈夋洿澶氭枃绔,

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

使用道具 举报

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中。好奇为啥没人提到这个。

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

使用道具 举报

小A要当码农 发表于 2015-10-27 00:20:18 | 显示全部楼层
plich 发表于 2015-10-20 10:13
follow up是说思路就行……或者说他本来期待我有码的……
. 1point3acres.com/bbs
可能我中文例子举得不好,"tom marvolo ridd ...

现在的实习面试已经这么难了啊。
请问楼主,第二题的话,应该在LC Add and Search Word的基础上做啥改进呢?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2015-10-27 00:25):. 鍥磋鎴戜滑@1point 3 acres
感觉每一个word,需要存其所有的substring啊,
回复 支持 反对

使用道具 举报

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

那样的话你的空间是O(m) 时间是O(n)
真的有短array的话可以直接二分搜,空间是O(1) 时间是O(mlog(n)) 如果m远小于n的话直接二分多合适
回复 支持 反对

使用道具 举报

 楼主| plich 发表于 2015-10-27 00:23:13 | 显示全部楼层
小A要当码农 发表于 2015-10-27 00:20. 1point 3acres 璁哄潧
现在的实习面试已经这么难了啊。
请问楼主,第二题的话,应该在LC Add and Search Word的基础上做啥改进 ...

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 15:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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