聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 10444|回复: 43
收起左侧

Facebook 面经

[复制链接] |试试Instant~ |关注本帖
lwt1104 发表于 2015-3-20 23:19:54 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类General 博士 实习@Facebook - 内推 - 技术电面  | Pass |

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

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

x
一面:
    首先定义了suffix string 或者说suffix arrary
    如果有个数组是 int[] text = {10, 20, 30, 25}
   那么 suffix[0] = {10, 20, 30, 25}
           suffix[1] = {20, 30, 25}
           suffix[2] = {30, 25}
           suffix[3] = {25}. more info on 1point3acres
如果对这些数组进行lexical order 的排序,我们可以得到
suffix[0] < suffix[1] < suffix[3] < suffix[2]
问题是:
    input: int[] text
    output: int[] suffix_array_order
e.g.
input: int[] text = {10, 20, 30, 25}. 1point3acres
output: int[] suffix_array_order = {0, 1, 3, 2}
第二题: input:  int[] text, int[] subText
              output: boolean isExist;
检查text数组中有没有一个subarray 是subText。要求时间小于O(N^2), N == text.length;
这里假设我们有了第一题的 suffix_array_order.. 牛人云集,一亩三分地
(做法是binary search).本文原创自1point3acres论坛


二面:
第一题
    Given an integer array which has the property that all the elements having same value are adjacent to each other.
. 1point 3acres 论坛    e,g,  {2, 2, 2, 1, 5, 6, 6, ,7, ,7}
    Output: Remove duplicate element in place and output the length of the new array. Do it in place and we don't care the elements outside the new length of the array.
   e.g. return 5 and  the input array will become {2, 1, 5, 6, 7, x, x, x, x} "x" means we don't care its value.
.本文原创自1point3acres论坛

第二题 leetcode原题 decode ways. visit 1point3acres for more.
. 1point 3acres 论坛

评分

4

查看全部评分

royalheart 发表于 2015-3-21 03:46:27 | 显示全部楼层
第一题不太明白意思,就是考sorting么?subtext是什么样的,是就一个数,还是{20,30} 这样的
回复 支持 反对

使用道具 举报

wcy1984123 发表于 2015-3-21 04:35:47 | 显示全部楼层
请问楼主 第一题的input array里面有duplicate么? 如果有的话lexi order怎么排?
比如 [20,20,20]是input,那么[20,20] 和 [20]比哪个大?谢谢。
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-3-21 22:04:13 | 显示全部楼层
wcy1984123 发表于 2015-3-21 04:35
请问楼主 第一题的input array里面有duplicate么? 如果有的话lexi order怎么排?
比如 [20,20,20]是input ...
. more info on 1point3acres
是按照lexi order 排,[20] < [20, 20]
回复 支持 反对

使用道具 举报

deephunter 发表于 2015-3-22 12:30:05 | 显示全部楼层
lwt1104 发表于 2015-3-21 22:04
是按照lexi order 排,[20] < [20, 20]

楼主是谁面的?
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-3-23 21:50:07 | 显示全部楼层

这个不好说吧,你问这个有用处吗?
回复 支持 反对

使用道具 举报

smallsimple 发表于 2015-3-23 22:49:21 | 显示全部楼层
一面的第二题如何用binary search呀。。完全没思路。
回复 支持 反对

使用道具 举报

deephunter 发表于 2015-3-24 04:26:51 | 显示全部楼层
lwt1104 发表于 2015-3-23 21:50
这个不好说吧,你问这个有用处吗?
. visit 1point3acres for more.
没啥用,我问的是白人还是印度人面的?
感觉这题目理解题意比较困难。。。面试时候很难答上了。。。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

zengm321 发表于 2015-3-24 05:00:12 | 显示全部楼层
smallsimple 发表于 2015-3-23 22:49. From 1point 3acres bbs
一面的第二题如何用binary search呀。。完全没思路。

就是在sorted的suffix arrays里面找某个数组的prefix, 使其等于target subtext。
bi-search subtext的第一个element, 得到一些suffix array, 然后在他们中间找subtext的第二个element,直到找到整个subtext。

店面考这个有点难了
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-3-24 08:21:24 | 显示全部楼层
deephunter 发表于 2015-3-24 04:26
没啥用,我问的是白人还是印度人面的?.本文原创自1point3acres论坛
感觉这题目理解题意比较困难。。。面试时候很难答上了。。。

这个意思啊,我以为你要问面试官的名字呢。是一个白人面的。其实他蛮nice的,这个题确实不算特别简单,不过冷静下来看应该还是能做出来的。
.本文原创自1point3acres论坛
其实我当时就只要给我面一个题目的,是我怕他想fail我,主动要求他再加一题的。我当时做的也是非常吃力。
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-3-24 08:23:10 | 显示全部楼层
smallsimple 发表于 2015-3-23 22:49
一面的第二题如何用binary search呀。。完全没思路。

你可以看下这个:
http://www.geeksforgeeks.org/suffix-array-set-1-introduction/

就是相当于把所有的substring 排序,然后binary search
回复 支持 反对

使用道具 举报

smallsimple 发表于 2015-3-24 10:35:46 | 显示全部楼层
lwt1104 发表于 2015-3-24 08:23. 1point 3acres 论坛
你可以看下这个:
http://www.geeksforgeeks.org/suffix-array-set-1-introduction/
. 围观我们@1point 3 acres
哦,原来如此呀,多谢楼主发链接。
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-3-30 02:18:22 | 显示全部楼层
请问LZ如何sort suffix array啊?G4G里面是string 的 suffix array.本文原创自1point3acres论坛
这题是array的suffix, 重写一个comparator? 一个一个元素比较, 如果都相同,短的那个小?
回复 支持 反对

使用道具 举报

sanguine 发表于 2015-3-30 03:16:39 | 显示全部楼层
LZ suffix arrary这个题怎么解?

我能想到的是先得到List<List>>然后重写comparator依次比较,但是时间复杂度很高啊,应该是O(n^2logn)?

有啥优化的地方吗
回复 支持 反对

使用道具 举报

sanguine 发表于 2015-3-30 03:33:30 | 显示全部楼层
为什么感觉2面明显比一面简单好多

LZ最后斩获offer了么
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-4-5 03:02:08 | 显示全部楼层
sanguine 发表于 2015-3-30 03:33
为什么感觉2面明显比一面简单好多. Waral 博客有更多文章,
. From 1point 3acres bbs
LZ最后斩获offer了么
.本文原创自1point3acres论坛
Same feedling. I get an offer finally.
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-4-5 03:04:17 | 显示全部楼层
shawlin 发表于 2015-3-30 02:18
. from: 1point3acres 请问LZ如何sort suffix array啊?G4G里面是string 的 suffix array
这题是array的suffix, 重写一个compar ...

You are right. Override the interface "Comparator<T>" as you said. Sorry for cannot type Chinese now.
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-4-5 03:07:25 | 显示全部楼层
sanguine 发表于 2015-3-30 03:16
LZ suffix arrary这个题怎么解?

我能想到的是先得到List>然后重写comparator依次比较,但是时间复杂度 ...

You don't need to create an LIst<List> for all the suffix arrays since that will take extra space and time to create. What I did is to create an wrapper class:
Class Index{. more info on 1point3acres
    public int index;. 留学申请论坛-一亩三分地
    public int[] array;
}
Just pass the reference of whole input array to the wrapper class object.

Sorry for cannot type Chinese now.

回复 支持 反对

使用道具 举报

yilina 发表于 2015-4-5 03:20:57 | 显示全部楼层
lwt1104 发表于 2015-4-5 03:02
Same feedling. I get an offer finally.

恭喜楼主!贺喜楼主。
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-4-5 08:55:30 | 显示全部楼层
yilina 发表于 2015-4-5 03:20
恭喜楼主!贺喜楼主。

谢谢哈,也祝你好运。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-22 09:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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