Snapchat一月电面面经

sunnyroom 发表于 2015-4-12 03:13
能讲讲思路吗

http://en.wikipedia.org/wiki/Interval_scheduling

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

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

Guardians 发表于 2015-4-11 12:00
啊, 对的, 谢谢提醒！没太注意, 主要是想举一个不是所有1-N都在array里的例子。[1, 1, 1, 3] 也是可以的~

如果只要求返回任意的重复元素，double for loop O(n2)查找不就可以了么？constant space

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

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

楼主我被问到这道了。。。亏我还在这里回了帖....在他的提示下做出来了。应该是个ABC人也好像没睡醒。但是人很NICE。。
直接最后说you will be invited to come onsite.

liao24hoho 发表于 2015-4-16 05:42
楼主我被问到这道了。。。亏我还在这里回了帖....在他的提示下做出来了。应该是个ABC人也好像没睡醒。但是 ...

啊恭喜恭喜！！！
所以答案应该是怎样的呢???

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

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

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

houqingniao 发表于 2015-4-11 13:42
不用hashtable，就用本身这个数组就成，只是把数字变负。
比如
【1，1，1，3】

当A[0] = 1>0为什么不是把A[0]设为负呢？变成【-1，1，1，3】
因为如果数组是【1，3，3】没办法把A[3]设为负啊，溢出了。。。

O(N)也可以做到,用异或运算就好,一行代码就搞定

(xor (accumulate xor 0 (enumerate 1 N)) (accumulate xor 0 inputList))