Snapchat一月电面面经

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

去年11月份海投得, 记得效率还挺快, 一周给的电面, Google Hangout

第一轮是一个妹子, 好像是某硬件组的, 具体不记得了, 就记得妹子长得还不错lol
我记得开始就问了下我背景和做过什麽, 看起来很有兴趣的样子。然后做题, 先是建一个event, 里面有start time和end time

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

太大兴趣。中间沉默了一段, 完全没给提示。
如果大家有想法欢迎讨论！！！我记得最后好像是说可以用一个nlogn的方法解决。提示了一下pigeon hole principal, 但是我还是没想到他想要的点

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

RANGE是1到N
先把RANGE分成 1到 N/2 和 N/2到 N
检查全部ARRAY里面有多少个数是 1到 N/2这个RANGE里的。
如果有多余 N/2个就说明这个RANGE里面有重叠，反之则是N/2 到N有重叠。
就这样RECURESE直到RANGE只有一个值，
然后返回这个值。
复杂度是nlogn.

suonan 发表于 2015-4-15 04:17
如果只要求返回任意的重复元素，double for loop O(n2)查找不就可以了么？constant space

嗯, 是可以, 但是要更快的~我当时有说这个, 他貌似要NlogN解法的~

houqingniao 发表于 2015-4-12 01:09
arr[1] 对应 位置1上面的3， 所以把他变负， arr【3】 对应数组位置3上面的3 所以把3变负，这样一直往下。 ...

这个方法点赞！感觉解决这一类题目都okay

index 进行标注~
再转换回去 这样子吧

houqingniao 发表于 2015-4-11 11:23
index 进行标注~
再转换回去 这样子吧

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

楼主你第二题这个例子对吗？range是1到N然后有N+1个数对吧，那例子应该是[1,1,3,2] 而不是[1,1,3,5]吧

1到N的和是(1+n)*n /2，所以全部加起来再减去前面（1+n)*n/2就可以了吧。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

liao24hoho 发表于 2015-4-11 11:59
1到N的和是(1+n)*n /2，所以全部加起来再减去前面（1+n)*n/2就可以了吧。

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

那好像确实不好做。。

出现过的把对应位置变成负数，在查到对应位置，如果是负数，说明出现过，就输出这个数。
最后把负数再转换回去

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies