《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 9225|回复: 42
收起左侧

Facebook 面经

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

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

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

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

x
一面:. 1point 3acres 璁哄潧
    首先定义了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]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
问题是:. Waral 鍗氬鏈夋洿澶氭枃绔,
    input: int[] text
    output: int[] suffix_array_order
e.g.. Waral 鍗氬鏈夋洿澶氭枃绔,
input: int[] text = {10, 20, 30, 25}
output: int[] suffix_array_order = {0, 1, 3, 2}
第二题: input:  int[] text, int[] subText
              output: boolean isExist;.1point3acres缃
检查text数组中有没有一个subarray 是subText。要求时间小于O(N^2), N == text.length;
这里假设我们有了第一题的 suffix_array_order.
(做法是binary search)


二面:
第一题
    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

评分

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 ...

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

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

使用道具 举报

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

就是在sorted的suffix arrays里面找某个数组的prefix, 使其等于target subtext。. Waral 鍗氬鏈夋洿澶氭枃绔,
bi-search subtext的第一个element, 得到一些suffix array, 然后在他们中间找subtext的第二个element,直到找到整个subtext。. 鍥磋鎴戜滑@1point 3 acres

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

使用道具 举报

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

这个意思啊,我以为你要问面试官的名字呢。是一个白人面的。其实他蛮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. 1point 3acres 璁哄潧
回复 支持 反对

使用道具 举报

smallsimple 发表于 2015-3-24 10:35:46 | 显示全部楼层
lwt1104 发表于 2015-3-24 08:23
你可以看下这个:
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这个题怎么解?

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

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

使用道具 举报

sanguine 发表于 2015-3-30 03:33:30 | 显示全部楼层
为什么感觉2面明显比一面简单好多
. 1point 3acres 璁哄潧
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这个题怎么解?

我能想到的是先得到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:-google 1point3acres
Class Index{.鏈枃鍘熷垱鑷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
恭喜楼主!贺喜楼主。

.鐣欏璁哄潧-涓浜-涓夊垎鍦谢谢哈,也祝你好运。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-19 09:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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