當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

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

Snapchat一月电面面经

[复制链接] |试试Instant~ |关注本帖
Guardians 发表于 2015-4-11 10:59:20 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类General 本科 全职@Snapchat - 网上海投 - 技术电面  | Fail | fresh grad应届毕业生

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

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

x
刚来地里赚点米, 写一个一月份Snapchat的面经吧
. more info on 1point3acres
去年11月份海投得, 记得效率还挺快, 一周给的电面, Google Hangout

第一轮是一个妹子, 好像是某硬件组的, 具体不记得了, 就记得妹子长得还不错lol
我记得开始就问了下我背景和做过什麽, 看起来很有兴趣的样子。然后做题, 先是建一个event, 里面有start time和end time, 然后check这两个event有没有conflict, 各种if else, 然后升级, 给一个list of events, 直接sort他们。再升级, 建一个schedule, 给几个office, 问怎么样的solution才是optimal的。

第一轮还聊得挺开心, 时间最后超了15分钟

因为中途圣诞假期, 第二轮约到一月中旬. 1point 3acres 论坛
. 1point 3acres 论坛
第二轮是个ABC, 后来查了下貌似是个Engineering lead。。。.本文原创自1point3acres论坛

一开始Google Hangout出了问题, 晚了20分钟才连上。 一上来简单问了两句,面试官说下面就是typical的一些interview question
首先, 一个array的range是1-N,这个array里有1+N个数, 找出这个array里的duplicate。(ex. [1, 1, 3, 5])   HashMap 解决
然后条件升级, 问不能用extra space。                                                                                                想了一下, 先sort, 再找
再升级, 不能改变array, 不能有extra space。
这个真的想了很久, 一直到现在都没有想出来有好的方法, 当时面试官好像刚刚睡醒的感觉, 也没太大兴趣。中间沉默了一段, 完全没给提示。
如果大家有想法欢迎讨论!!!我记得最后好像是说可以用一个nlogn的方法解决。提示了一下pigeon hole principal, 但是我还是没想到他想要的点

算是为下面的面试攒rp吧!如果大家对这个题有想法欢迎讨论!!!

评分

3

查看全部评分

liao24hoho 发表于 2015-4-16 10:31:31 | 显示全部楼层
RANGE是1到N
先把RANGE分成 1到 N/2 和 N/2到 N
检查全部ARRAY里面有多少个数是 1到 N/2这个RANGE里的。
如果有多余 N/2个就说明这个RANGE里面有重叠,反之则是N/2 到N有重叠。
就这样RECURESE直到RANGE只有一个值,
然后返回这个值。
复杂度是nlogn.
回复 支持 3 反对 0

使用道具 举报

houqingniao 发表于 2015-4-11 13:42:42 | 显示全部楼层
Guardians 发表于 2015-4-11 13:33
所以你还是要用一个hashtable或者array来记录对应位置咯?...但是要求不能用extra space...而且也不能改变 ...
. 1point3acres
不用hashtable,就用本身这个数组就成,只是把数字变负。. From 1point 3acres bbs
比如
【1,1,1,3】. 1point 3acres 论坛
查第一个1 对应数组第一位就变复数,【1,-1,1,3】
第二个1也对应数组第一位 因为已经是负数,所以就重复了。。。如此往下扫。。
回复 支持 1 反对 0

使用道具 举报

enicloom 发表于 2015-4-12 02:44:11 | 显示全部楼层
houqingniao 发表于 2015-4-12 01:09
arr[1] 对应 位置1上面的3, 所以把他变负, arr【3】 对应数组位置3上面的3 所以把3变负,这样一直往下。 ...

这个方法点赞!感觉解决这一类题目都okay
回复 支持 0 反对 1

使用道具 举报

 楼主| Guardians 发表于 2015-4-15 04:42:51 | 显示全部楼层
suonan 发表于 2015-4-15 04:17
如果只要求返回任意的重复元素,double for loop O(n2)查找不就可以了么?constant space

嗯, 是可以, 但是要更快的~我当时有说这个, 他貌似要NlogN解法的~
回复 支持 1 反对 0

使用道具 举报

houqingniao 发表于 2015-4-11 11:23:05 | 显示全部楼层
index 进行标注~
再转换回去 这样子吧
回复 支持 反对

使用道具 举报

 楼主| Guardians 发表于 2015-4-11 11:28:36 | 显示全部楼层
houqingniao 发表于 2015-4-11 11:23. more info on 1point3acres
index 进行标注~. 牛人云集,一亩三分地
再转换回去 这样子吧

hmmm, 不好意思没太看懂? 类似hashtable麽? 但是不能有extra space诶, 而且array是immutable的...
回复 支持 反对

使用道具 举报

flslamdunk 发表于 2015-4-11 11:55:48 | 显示全部楼层
楼主你第二题这个例子对吗?range是1到N然后有N+1个数对吧,那例子应该是[1,1,3,2] 而不是[1,1,3,5]吧
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

liao24hoho 发表于 2015-4-11 11:59:32 | 显示全部楼层
1到N的和是(1+n)*n /2,所以全部加起来再减去前面(1+n)*n/2就可以了吧。
回复 支持 反对

使用道具 举报

 楼主| Guardians 发表于 2015-4-11 12:00:10 | 显示全部楼层
flslamdunk 发表于 2015-4-11 11:55
楼主你第二题这个例子对吗?range是1到N然后有N+1个数对吧,那例子应该是[1,1,3,2] 而不是[1,1,3,5]吧

啊, 对的, 谢谢提醒!没太注意, 主要是想举一个不是所有1-N都在array里的例子。[1, 1, 1, 3] 也是可以的~
回复 支持 反对

使用道具 举报

 楼主| Guardians 发表于 2015-4-11 12:01:44 | 显示全部楼层
liao24hoho 发表于 2015-4-11 11:59
1到N的和是(1+n)*n /2,所以全部加起来再减去前面(1+n)*n/2就可以了吧。

不一定只有一个重复, 而且1-N中不一定每个都有~记得我当时就反复跟他double check这个lol
回复 支持 反对

使用道具 举报

liao24hoho 发表于 2015-4-11 12:05:16 | 显示全部楼层
那好像确实不好做。。
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-4-11 13:29:18 | 显示全部楼层
出现过的把对应位置变成负数,在查到对应位置,如果是负数,说明出现过,就输出这个数。
最后把负数再转换回去
回复 支持 反对

使用道具 举报

 楼主| Guardians 发表于 2015-4-11 13:33:44 | 显示全部楼层
houqingniao 发表于 2015-4-11 13:29
出现过的把对应位置变成负数,在查到对应位置,如果是负数,说明出现过,就输出这个数。
最后把负数再转换 ...

所以你还是要用一个hashtable或者array来记录对应位置咯?...但是要求不能用extra space...而且也不能改变这个原来的array额....
回复 支持 反对

使用道具 举报

 楼主| Guardians 发表于 2015-4-11 13:52:53 | 显示全部楼层
houqingniao 发表于 2015-4-11 13:42
不用hashtable,就用本身这个数组就成,只是把数字变负。
比如
【1,1,1,3】

当时原话说的是the array is immutable. 不知道能不能直接改这个数组诶, 没法考证了lol
你说的这个例子, 如果我的顺序是[1, 3, 2, 3]的话呢? ... 所以[1, 3, 2, 3]会变成 [1, -1, 2, 3]麽?
可能我忘记补充了, 可以是乱序的~
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-4-11 13:58:32 | 显示全部楼层
immutable 这个就不知道怎么搞了 来源一亩.三分地论坛.
【1,3,2,3】---》【1, -3,2,3】--》【1,-3,2,-3】出现重复了 输出,继续往后
回复 支持 反对

使用道具 举报

 楼主| Guardians 发表于 2015-4-11 14:06:43 | 显示全部楼层
houqingniao 发表于 2015-4-11 13:58
immutable 这个就不知道怎么搞了. from: 1point3acres
【1,3,2,3】---》【1, -3,2,3】--》【1,-3,2,-3】出现重复了 输 ...

嗯, 我之前网上也查了好久, 有说用quicksort linkedlist方法解的, 没太看懂。
啊, 不好意思啊, 我有点slow, 还是没太看懂
因为我想的你说的是出现过的, 然后把对应的变成负数
那么[1, 3, 2, 3] -> 第一个出现的是1吧? 对应的arr[1] = -1? 所以应该是[1, -1. 2, 3]?
想指教下, 这个[1, 3, 2, 3] -> [1, -3, 2, 3] -> [1, -3, 2, -3]是怎麽跳过1和2的呢?
谢谢啦!!
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-4-12 01:09:38 | 显示全部楼层
arr[1] 对应 位置1上面的3, 所以把他变负, arr【3】 对应数组位置3上面的3 所以把3变负,这样一直往下。。
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2015-4-12 02:36:03 | 显示全部楼层
请问楼主,
再升级, 建一个schedule, 给几个office, 问怎么样的solution才是optimal的. Waral 博客有更多文章,
这个是什么意思。
回复 支持 反对

使用道具 举报

 楼主| Guardians 发表于 2015-4-12 02:41:52 | 显示全部楼层
sunnyroom 发表于 2015-4-12 02:36
请问楼主,
再升级, 建一个schedule, 给几个office, 问怎么样的solution才是optimal的
这个是什么意思。

就是给一堆event, 然后之间可能会有conflict的。但是可以分到不同office里。
问怎麽排才能排出最佳的schedule。比较典型的greedy
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2015-4-12 02:44:50 | 显示全部楼层
Guardians 发表于 2015-4-12 02:41
就是给一堆event, 然后之间可能会有conflict的。但是可以分到不同office里。. Waral 博客有更多文章,
问怎麽排才能排出最佳的sch ...
. 一亩-三分-地,独家发布
谢谢楼主
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2015-4-12 03:13:40 | 显示全部楼层
Guardians 发表于 2015-4-12 02:41
就是给一堆event, 然后之间可能会有conflict的。但是可以分到不同office里。
问怎麽排才能排出最佳的sch ...

能讲讲思路吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-20 18:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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