一亩三分地论坛

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

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

Snapchat一月电面面经

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

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

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

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

x
刚来地里赚点米, 写一个一月份Snapchat的面经吧

去年11月份海投得, 记得效率还挺快, 一周给的电面, Google Hangout
. from: 1point3acres.com/bbs
第一轮是一个妹子, 好像是某硬件组的, 具体不记得了, 就记得妹子长得还不错lol
我记得开始就问了下我背景和做过什麽, 看起来很有兴趣的样子。然后做题, 先是建一个event, 里面有start time和end time, 然后check这两个event有没有conflict, 各种if else, 然后升级, 给一个list of events, 直接sort他们。再升级, 建一个schedule, 给几个office, 问怎么样的solution才是optimal的。

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

因为中途圣诞假期, 第二轮约到一月中旬

第二轮是个ABC, 后来查了下貌似是个Engineering lead。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
一开始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...而且也不能改变 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不用hashtable,就用本身这个数组就成,只是把数字变负。.鐣欏璁哄潧-涓浜-涓夊垎鍦
比如
【1,1,1,3】
查第一个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
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]吧
回复 支持 反对

使用道具 举报

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就可以了吧。
. 鍥磋鎴戜滑@1point 3 acres
不一定只有一个重复, 而且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,就用本身这个数组就成,只是把数字变负。.1point3acres缃
比如
【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 这个就不知道怎么搞了
【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]?. visit 1point3acres.com for more.
想指教下, 这个[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的
这个是什么意思。
回复 支持 反对

使用道具 举报

 楼主| Guardians 发表于 2015-4-12 02:41:52 | 显示全部楼层
sunnyroom 发表于 2015-4-12 02:36
请问楼主,. visit 1point3acres.com for more.
再升级, 建一个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里。
问怎麽排才能排出最佳的sch ...

谢谢楼主
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 04:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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