一亩三分地论坛

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

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

Facebook onsite面经

[复制链接] |试试Instant~ |关注本帖
mc422 发表于 2015-7-26 03:32:37 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
朋友帮忙推荐给recruiter的,两轮电面之后拿到onsite。
第一轮: 老印,上来一道题,讲了半天我才弄明白。类似手机按键,比如手机按键上2对应‘abc’, 然后根据‘abc’的顺序,打出a要按一下键,b要按两下键,c要按三下键。给你两个数组: keySize[] 每个element代表能存放的最多character,frequency[]每个element代表每个character出现的频率。要算出最少的按键次数。 Follow up 1: 怎么能提高效率。 Follup up 2: 如果要求character放在按键上的顺序是order的,类似于手机shang的字母按键,这样最少按键次数是多少。

第二轮:还是个烙印: 第一题:rotated sorted array search. 让后要求cut branch。 第二题: sort an array contains only 3 element,类似leetcode的sort colors。 follow up: what if there are N element? 没想出来, hint是可以使用extra memery

第三轮: 简历问题为主,问了一道code: check the first bad version.

结果还是跪了。问题应该出在第一轮面试上,code写了好久才写出来,follow up也没答上。其实题目也不算很难,大家好运吧。. from: 1point3acres.com/bbs


补充内容 (2015-7-28 05:16):
好吧,可能是我表达不好,第一题不画个图真不大好说。-google 1point3acres

例子就是我们的手机,几乎每个键都对应字母: key2 -> 'abc', key3 -> 'def', key4 -> 'ghi'....老式的手机打字的原理是,如果你要打出a,你需要按1下key2....

评分

3

查看全部评分

本帖被以下淘专辑推荐:

 楼主| mc422 发表于 2015-7-28 05:17:15 | 显示全部楼层
好吧,可能是我表达不好,第一题不画个图真不大好说。

例子就是我们的手机,几乎每个键都对应字母: key2 -> 'abc', key3 -> 'def', key4 -> 'ghi'....老式的手机打字的原理是,如果你要打出a,你需要按1下key2. 如果要打出b,你需要按2下key2, 打出c就要按3下key2,因为c排在key2的第三位。

所以题目是给出,keySize[] 每个element代表能存放的最多character, 比如上面的例子就是[3,3,3],因为每个key都能最多放3个字母; 还有frequency[],每个element代表每个character出现的频率。要求把character排入key中,通过上面的方法打出所有frequency数组中的character,最少的按键次数。
. 1point3acres.com/bbs
下面给个例子,比如我们的keysize是 [3,1,2],我们的character的frequency是 [3,3, 3, 2,1,1]。 如果把frequency中头三个字母index0 - index2放入key1, index3放入key2,index4-index5放入key3,这样的按键次数就是 3*1 + 3*2 + 3*3 + 2*1 + 1*1 + 1*2。character可以daluan随意放,只要不超过keySize的limit。

follow up的要求就是character必须要找 frequency的order来,index2必能放在index1之前。

希望大家能看明白。
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2015-7-26 03:41:23 | 显示全部楼层
第二题: sort an array contains only 3 element,类似leetcode的sort colors。 follow up: what if there are N element? 没想出来, hint是可以使用extra memery  <----这个就变成counting sort了吧. 如果n是constant
回复 支持 反对

使用道具 举报

354886 发表于 2015-7-26 04:29:04 | 显示全部楼层
第一轮是不是可以用Trie? keysize就是每一个节点有多少字母。
回复 支持 反对

使用道具 举报

ccgogo123 发表于 2015-7-26 05:53:41 | 显示全部楼层
楼主,能够针对第一题举个例子吗?
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-7-26 07:42:56 | 显示全部楼层
楼主说说第一题。
回复 支持 反对

使用道具 举报

tonyjiang 发表于 2015-7-26 08:38:52 | 显示全部楼层
```给你两个数组: keySize[] 每个element代表能存放的最多character,frequency[]每个element代表每个character出现的频率。```
能够针对第一题举个例子吗?能说的再详细点吗?
回复 支持 反对

使用道具 举报

beyond 发表于 2015-7-27 23:22:57 | 显示全部楼层
第二轮第一题 cut branch什么意思?
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-28 00:20:38 | 显示全部楼层
beyond 发表于 2015-7-27 23:22
第二轮第一题 cut branch什么意思?

莫非是pruning,剪枝?
回复 支持 反对

使用道具 举报

Esail 发表于 2015-7-28 02:23:04 | 显示全部楼层
sort color 那题应该是counting sort如果element 为n的话
回复 支持 反对

使用道具 举报

xnature 发表于 2015-7-28 03:23:24 | 显示全部楼层
第一道是不是这样的。

有N个key,第i个key可以容纳keysize[i]多个character。对于每个key,key size[i]个character必须是依次排列。比如key是1,容纳3个character,a,b,c。你可以排成cab, bac, ..... 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

再给你frequency数组大小M,问你如何把M个character排列到N个key上去,使得总的按character的期望频率最小吧。。。。
回复 支持 反对

使用道具 举报

 楼主| mc422 发表于 2015-7-28 05:19:23 | 显示全部楼层
xnature 发表于 2015-7-28 03:23
第一道是不是这样的。. 1point 3acres 璁哄潧

有N个key,第i个key可以容纳keysize多个character。对于每个key,key size个chara ...

对,基本就是这个意思,比如你其中一个key容纳‘abc’,那你打出a要按1次键,打出b要按2次,c要按3次。
让后给你所有character需要打出的次数,求最少的按键次数
回复 支持 反对

使用道具 举报

 楼主| mc422 发表于 2015-7-28 05:20:21 | 显示全部楼层
beyond 发表于 2015-7-27 23:22
第二轮第一题 cut branch什么意思?

就是简化code,把不必要的case去掉
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-7-28 05:52:10 | 显示全部楼层
Followup 2应该是动态规划。  
http://www.acmerblog.com/POJ-1404-I-Keyboard-blog-387.html
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-7-28 05:53:17 | 显示全部楼层
http://poj.org/problem?id=1404

另外,欢迎找我内推Google. 여러분..
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-28 07:00:24 | 显示全部楼层
第二轮,可以用extra memory的话,那就太简单了啊。。。。。。
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-28 07:08:42 | 显示全部楼层
mc422 发表于 2015-7-28 05:17
好吧,可能是我表达不好,第一题不画个图真不大好说。

例子就是我们的手机,几乎每个键都对应字母: key ...

follow up的要求就是character必须要找 frequency的order来,index2必能放在index1之前。
楼主,这句话,说白了就是必须按照字母表顺序来呗?是这样的嘛?谢谢
回复 支持 反对

使用道具 举报

JohnnyHuo 发表于 2015-7-28 07:37:21 | 显示全部楼层
lz onsite 只有三轮呀?
回复 支持 反对

使用道具 举报

xnature 发表于 2015-7-28 08:24:32 | 显示全部楼层
Linzertorte 发表于 2015-7-28 05:52. visit 1point3acres.com for more.
Followup 2应该是动态规划。  
http://www.acmerblog.com/POJ-1404-I-Keyboard-blog-387.html

我还以为greedy就够了。。。。囧
回复 支持 反对

使用道具 举报

emmarong 发表于 2015-7-31 02:45:25 | 显示全部楼层
mc422 发表于 2015-7-28 05:19. Waral 鍗氬鏈夋洿澶氭枃绔,
对,基本就是这个意思,比如你其中一个key容纳‘abc’,那你打出a要按1次键,打出b要按2次,c要按3次。
...

请问楼主,character可不可跳着放?比如,
Key1: AC
Key2:   B
这样对于每个key上的character来说,order是没有被打乱的,不过不是完全连续的排列。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 16:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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