一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 6374|回复: 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}
如果对这些数组进行lexical order 的排序,我们可以得到
suffix[0] < suffix[1] < suffix[3] < suffix[2]
问题是:.鏈枃鍘熷垱鑷1point3acres璁哄潧
    input: int[] text
    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.
(做法是binary search). from: 1point3acres.com/bbs


二面:
第一题
    Given an integer array which has the property that all the elements having same value are adjacent to each other.
    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]比哪个大?谢谢。
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-3-21 22:04:13 | 显示全部楼层
wcy1984123 发表于 2015-3-21 04:35
请问楼主 第一题的input array里面有duplicate么? 如果有的话lexi order怎么排? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
比如 [20,20,20]是input ...
. 鍥磋鎴戜滑@1point 3 acres
是按照lexi order 排,[20] < [20, 20]
回复 支持 反对

使用道具 举报

deephunter 发表于 2015-3-22 12:30:05 | 显示全部楼层
lwt1104 发表于 2015-3-21 22:04
是按照lexi order 排,[20] < [20, 20]
. From 1point 3acres bbs
楼主是谁面的?
回复 支持 反对

使用道具 举报

 楼主| 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
这个不好说吧,你问这个有用处吗?

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

使用道具 举报

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。

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

使用道具 举报

 楼主| lwt1104 发表于 2015-3-24 08:21:24 | 显示全部楼层
deephunter 发表于 2015-3-24 04:26.鏈枃鍘熷垱鑷1point3acres璁哄潧
没啥用,我问的是白人还是印度人面的?.鏈枃鍘熷垱鑷1point3acres璁哄潧
感觉这题目理解题意比较困难。。。面试时候很难答上了。。。
-google 1point3acres
这个意思啊,我以为你要问面试官的名字呢。是一个白人面的。其实他蛮nice的,这个题确实不算特别简单,不过冷静下来看应该还是能做出来的。

其实我当时就只要给我面一个题目的,是我怕他想fail我,主动要求他再加一题的。我当时做的也是非常吃力。
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-3-24 08:23:10 | 显示全部楼层
smallsimple 发表于 2015-3-23 22:49. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
一面的第二题如何用binary search呀。。完全没思路。

. more info on 1point3acres.com你可以看下这个:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
http://www.geeksforgeeks.org/suffix-array-set-1-introduction/-google 1point3acres

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

使用道具 举报

smallsimple 发表于 2015-3-24 10:35:46 | 显示全部楼层
lwt1104 发表于 2015-3-24 08:23
你可以看下这个:. visit 1point3acres.com for more.
http://www.geeksforgeeks.org/suffix-array-set-1-introduction/

哦,原来如此呀,多谢楼主发链接。
回复 支持 反对

使用道具 举报

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

使用道具 举报

sanguine 发表于 2015-3-30 03:16:39 | 显示全部楼层
LZ suffix arrary这个题怎么解?
.1point3acres缃
我能想到的是先得到List<List>>然后重写comparator依次比较,但是时间复杂度很高啊,应该是O(n^2logn)?. 1point3acres.com/bbs

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

使用道具 举报

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

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

使用道具 举报

 楼主| 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这个题怎么解?-google 1point3acres

我能想到的是先得到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.. visit 1point3acres.com for more.

. From 1point 3acres bbsSorry 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.
.1point3acres缃
恭喜楼主!贺喜楼主。
回复 支持 反对

使用道具 举报

 楼主| lwt1104 发表于 2015-4-5 08:55:30 | 显示全部楼层
yilina 发表于 2015-4-5 03:20. Waral 鍗氬鏈夋洿澶氭枃绔,
恭喜楼主!贺喜楼主。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
谢谢哈,也祝你好运。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 06:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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