传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 5932|回复: 34
收起左侧

Snapchat一月电面面经

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

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

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

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

x
刚来地里赚点米, 写一个一月份Snapchat的面经吧.鐣欏璁哄潧-涓浜-涓夊垎鍦
.1point3acres缃
去年11月份海投得, 记得效率还挺快, 一周给的电面, Google Hangout

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

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

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

第二轮是个ABC, 后来查了下貌似是个Engineering lead。。。

一开始Google Hangout出了问题, 晚了20分钟才连上。 一上来简单问了两句,面试官说下面就是typical的一些interview question.鏈枃鍘熷垱鑷1point3acres璁哄潧
首先, 一个array的range是1-N,这个array里有1+N个数, 找出这个array里的duplicate。(ex. [1, 1, 3, 5])   HashMap 解决
然后条件升级, 问不能用extra space。                                                                                                想了一下, 先sort, 再找
再升级, 不能改变array, 不能有extra space。. visit 1point3acres.com for more.
这个真的想了很久, 一直到现在都没有想出来有好的方法, 当时面试官好像刚刚睡醒的感觉, 也没太大兴趣。中间沉默了一段, 完全没给提示。. more info on 1point3acres.com
如果大家有想法欢迎讨论!!!我记得最后好像是说可以用一个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 进行标注~.鏈枃鍘熷垱鑷1point3acres璁哄潧
再转换回去 这样子吧
回复 支持 反对

使用道具 举报

 楼主| Guardians 发表于 2015-4-11 11:28:36 | 显示全部楼层
houqingniao 发表于 2015-4-11 11:23
index 进行标注~. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
再转换回去 这样子吧
. from: 1point3acres.com/bbs
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就可以了吧。

不一定只有一个重复, 而且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】
. from: 1point3acres.com/bbs
当时原话说的是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]?
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 想指教下, 这个[1, 3, 2, 3] -> [1, -3, 2, 3] -> [1, -3, 2, -3]是怎麽跳过1和2的呢? -google 1point3acres
谢谢啦!!
回复 支持 反对

使用道具 举报

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
请问楼主,
再升级, 建一个schedule, 给几个office, 问怎么样的solution才是optimal的.1point3acres缃
这个是什么意思。

就是给一堆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 ...

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-22 20:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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