一亩三分地论坛

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

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

Facebook 面经

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

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

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

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

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}. 鍥磋鎴戜滑@1point 3 acres
如果对这些数组进行lexical order 的排序,我们可以得到
suffix[0] < suffix[1] < suffix[3] < suffix[2]
问题是:
    input: int[] text
. more info on 1point3acres.com    output: int[] suffix_array_order
e.g.
input: int[] text = {10, 20, 30, 25}
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.
.鏈枃鍘熷垱鑷1point3acres璁哄潧(做法是binary search)


二面:
第一题
    Given an integer array which has the property that all the elements having same value are adjacent to each other.. more info on 1point3acres.com
    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.


第二题 leetcode原题 decode ways

评分

3

查看全部评分

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]比哪个大?谢谢。
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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

使用道具 举报

deephunter 发表于 2015-3-22 12:30:05 | 显示全部楼层
lwt1104 发表于 2015-3-21 22:04. 1point 3acres 璁哄潧
是按照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. more info on 1point3acres.com
这个不好说吧,你问这个有用处吗?

没啥用,我问的是白人还是印度人面的?. From 1point 3acres bbs
感觉这题目理解题意比较困难。。。面试时候很难答上了。。。
回复 支持 反对

使用道具 举报

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

就是在sorted的suffix arrays里面找某个数组的prefix, 使其等于target subtext。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
bi-search subtext的第一个element, 得到一些suffix array, 然后在他们中间找subtext的第二个element,直到找到整个subtext。. visit 1point3acres.com for more.

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

使用道具 举报

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

这个意思啊,我以为你要问面试官的名字呢。是一个白人面的。其实他蛮nice的,这个题确实不算特别简单,不过冷静下来看应该还是能做出来的。

其实我当时就只要给我面一个题目的,是我怕他想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
你可以看下这个:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
http://www.geeksforgeeks.org/suffix-array-set-1-introduction/

哦,原来如此呀,多谢楼主发链接。
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-3-30 02:18:22 | 显示全部楼层
请问LZ如何sort suffix array啊?G4G里面是string 的 suffix array. 1point3acres.com/bbs
这题是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面明显比一面简单好多
. from: 1point3acres.com/bbs
LZ最后斩获offer了么
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-4-5 03:02:08 | 显示全部楼层
sanguine 发表于 2015-3-30 03:33
为什么感觉2面明显比一面简单好多
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
LZ最后斩获offer了么

Same feedling. I get an offer finally.
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-4-5 03:04:17 | 显示全部楼层
shawlin 发表于 2015-3-30 02:18
请问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{
    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
恭喜楼主!贺喜楼主。

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-23 14:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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