一亩三分地论坛

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

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

FB店面面经

[复制链接] |试试Instant~ |关注本帖
zhuhai_ZFC 发表于 2016-8-20 03:19:11 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
FB店面,杯具了。。。。发个面经,攒攒以后的人品。
1. 字符串匹配,最原始的那种:一个s,一个p,在s里面找p,返回第一个匹配字串的开头下标。如没有返回-1。忘了KMP怎么写的了,只能brute-force。。。。。
follow up:不用写代码,大概描述一下:不是找p,而是找p的permutation。比如s="aabacddccab", p="dadc",返回3。因为acdd是dadc的permutation。

2. 找到一个二叉树里面的离根最近的叶子节点,返回其深度。

3.read4,单次那种,非多次的。只不过不是4 bytes,而是4KB。.1point3acres缃
. visit 1point3acres.com for more.
面完了,整个人都不好了。还是基本功太差啊。

评分

1

查看全部评分

edyyy 发表于 2016-8-20 04:41:07 | 显示全部楼层
楼主打回去好好刷题!
回复 支持 1 反对 0

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-8-20 05:54:10 | 显示全部楼层
zyoppy008 发表于 2016-8-20 05:12. Waral 鍗氬鏈夋洿澶氭枃绔,
找出所有你的朋友的朋友,但不是你的朋友,按你们共同好友的数量排序

能不能用BFS做?只找到第二层就停止,并且对于每个第二层的节点,在BFS的过程中就记录有多少个第一层的节点能够到达它。这样就能排序了。BFS的时间复杂度是O(n),排序的时间复杂度是O(nlogn)。总共是O(nlogn)
回复 支持 1 反对 0

使用道具 举报

sooorrr 发表于 2016-8-20 04:23:45 | 显示全部楼层
店面这么多题还不过?这个面试官在想啥?
回复 支持 反对

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-8-20 04:26:07 | 显示全部楼层
sooorrr 发表于 2016-8-20 04:23
店面这么多题还不过?这个面试官在想啥?
. more info on 1point3acres.com
但都不是难题。。。。而且我答的不太好,尤其是最后一题,虽然以前写过一次,但是没参考过答案,可能代码不够简洁,还有漏洞。
回复 支持 反对

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-8-20 04:33:25 | 显示全部楼层
第一题的follow up我觉得可以用哈希表记录pattern里每个字符的出现次数,然后在string里维持一个pattern大小的窗口,窗口不断后移,如果遇到一个pattern里的字符就把他的频次-1,移除一个字符就+1。同时维持一个变量记录频次为0的字符的个数。这个值一开始等于pattern里的不同的字符的数量。在移动窗口的时候,一旦有字符的频次被减为0,则将这个变量的值减一。当该变量在某个时候变为0的时候,则找到了一个permutation。
回复 支持 反对

使用道具 举报

edyyy 发表于 2016-8-20 04:36:47 | 显示全部楼层
第一题是implement strstr
回复 支持 反对

使用道具 举报

edyyy 发表于 2016-8-20 04:40:20 | 显示全部楼层
第一题是implement strstr.
第二题是Minimum Depth of Binary Tree,
第三题是read4k.   Given API: int Read4096(char* buf);  It reads data from a file and records the position so that the next time when it is called it read the next 4k chars (or the rest of the file, whichever is smaller) from the file. The return is the number of chars read.   Todo: Use above API to Implement API  "int Read(char* buf, int n)" which reads any number of chars from the file.
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-8-20 04:52:20 | 显示全部楼层
都是原题,人品不错啦。。我昨天才面的,都是见到没见过的,连面经都没有的题,还是傻逼烙印给我面的,也挂了。 不过你好歹面了3个题,竟然也挂你?
回复 支持 反对

使用道具 举报

edyyy 发表于 2016-8-20 04:57:26 | 显示全部楼层
zyoppy008 发表于 2016-8-20 04:52
都是原题,人品不错啦。。我昨天才面的,都是见到没见过的,连面经都没有的题,还是傻逼烙印给我面的,也挂 ...

你烤了啥题?
等你有了工作也去黑烙印啊
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-8-20 05:02:18 | 显示全部楼层
zyoppy008 发表于 2016-8-20 04:52.1point3acres缃
都是原题,人品不错啦。。我昨天才面的,都是见到没见过的,连面经都没有的题,还是傻逼烙印给我面的,也挂 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
同问啥题目
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-8-20 05:12:04 | 显示全部楼层
edyyy 发表于 2016-8-20 04:57. 1point 3acres 璁哄潧
你烤了啥题?
等你有了工作也去黑烙印啊

找出所有你的朋友的朋友,但不是你的朋友,按你们共同好友的数量排序
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-8-20 05:12:19 | 显示全部楼层
edyyy 发表于 2016-8-20 04:40
第一题是implement strstr.
第二题是Minimum Depth of Binary Tree,
第三题是read4k.   Given API: int ...

strStr那题不需要KMP吧?就最基础那种方法
回复 支持 反对

使用道具 举报

edyyy 发表于 2016-8-20 05:33:48 | 显示全部楼层
zyoppy008 发表于 2016-8-20 05:12
找出所有你的朋友的朋友,但不是你的朋友,按你们共同好友的数量排序

靠图?six degrees?. more info on 1point3acres.com

补充内容 (2016-8-20 05:34):
https://segmentfault.com/q/1010000000094713

这种吗?很难啊

补充内容 (2016-8-20 05:35):
二度好友?
http://www.datalab.sinaapp.com/?p=192
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-8-20 05:43:06 | 显示全部楼层
edyyy 发表于 2016-8-20 05:33.鏈枃鍘熷垱鑷1point3acres璁哄潧
靠图?six degrees?

补充内容 (2016-8-20 05:34):

对啊,类似吧。其实不难,我也写出来了,用dfs写的,但后来一想因为是二度好友,不用写这么复杂,不需要dfs,排序的话用map 记录数量
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-8-20 07:17:09 | 显示全部楼层
zhuhai_ZFC 发表于 2016-8-20 05:54
能不能用BFS做?只找到第二层就停止,并且对于每个第二层的节点,在BFS的过程中就记录有多少个第一层的节 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我就是用dfs做的,bfs dfs比较类似吧,其实没必要,直接一个map就出来了 很简单的,不要想复杂了
回复 支持 反对

使用道具 举报

sniffsky 发表于 2016-8-20 07:25:28 | 显示全部楼层
应该不会要求你用KMP吧,况且还是第一题,最基础的匹配算法就行啦
回复 支持 反对

使用道具 举报

haoshenxiong 发表于 2016-8-25 13:25:18 | 显示全部楼层
第三题挺难写的啊,感觉店面写个1 3两题就应该完全够了
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-8-26 10:04:15 | 显示全部楼层
lz面了多久知道的结果呀
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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