Bloomberg 8/3 onsite

runrain 发表于 2016-8-5 11:49
准确是看average case。 但是这一题worst case 就是 2*n 所以还是O（n）  我没有算错了吧？

不知道原题是啥，看代码，num一共被统计了n次，两层for loop受到num的限制，最多n次，所以应该是O(n)。不过这题的best、worst、average都是O(n)，不适合举例说明，直接归纳更好一些。

具体考察worst case还是average case要根据实际情况(面试官要求)来才对。比如检测网页response time，有两种情况: (1) 5%的情况是5秒，95%情况是0.0001秒，average是0.25左右；(2) 0.01%情况5秒， 99.99%情况是0.5秒，average是0.5秒左右。这里后者average是前者的2倍，但是对于前者来说，会有5%的用户，居然要等待5秒网页才有相应，这时候的体验就比较差，所以worst case更重要。

补充内容 (2016-8-6 03:12):
LZ可能是太急了有点激动，可能别人没听明白吧

sheepmiemies 发表于 2016-8-6 03:11
不知道原题是啥，看代码，num一共被统计了n次，两层for loop受到num的限制，最多n次，所以应该是O(n)。不 ...

你这个真能引申呀 不过你说的非常对 真是不想说那两位大哥的水平 最后还拒了我
你是不是最近准备BB呀 我换了一个号出来了 以前真名发的 心里太慌

runrain 发表于 2016-8-5 22:50

你这代码跑不过吧。首先你第二个forloop里面nums[i]越界了，其次你result里面到底放的是sets[i]还是i啊？

whitesunday 发表于 2016-8-6 03:26
你这代码跑不过吧。首先你第二个forloop里面nums越界了，其次你result里面到底放的是sets还是i啊？

第一个越界了 没注意 你明白大意就好 放的就是i 如果放的是sets 就是错的

sheepmiemies 发表于 2016-8-6 03:11
不知道原题是啥，看代码，num一共被统计了n次，两层for loop受到num的限制，最多n次，所以应该是O(n)。不 ...

那个国人大哥鄙视的眼神 让我很无语 自己看不懂就算了 还要鄙视

runrain 发表于 2016-8-6 03:29
第一个越界了 没注意 你明白大意就好 放的就是i 如果放的是sets 就是错的

因为你代码里面既有res.add(sets[i])，也有res.add(i)所以看不太懂。。
anyway 后面的面试加油吧！

补充内容 (2016-8-6 03:36):
这论坛不让我打方括号i方括号什么鬼。。还要我用escape么

whitesunday 发表于 2016-8-6 03:36
因为你代码里面既有res.add(sets)，也有res.add(i)所以看不太懂。。
anyway 后面的面试加油吧！

因为前面是用处理大于的 后面就是用来回复被压缩数组的 我已经接了Snapchat的offer了 本来是想说妹子在纽约给他一个惊喜的

runrain 发表于 2016-8-6 03:38
因为前面是用处理大于的 后面就是用来回复被压缩数组的 我已经接了Snapchat的offer了 本来是想说妹子在纽 ...

异地多麻烦啊。。snapchat NYC有办公室么

补充内容 (2016-8-6 04:03):
但是snapchat offer甩bb的几条街呢 所以无所谓啦

whitesunday 发表于 2016-8-6 03:59
异地多麻烦啊。。snapchat NYC有办公室么

补充内容 (2016-8-6 04:03):

你们家base高一点124500 她在纽约 我要去LA 之前面的就是LA的办公室 所以没有的选择

其实这个O(n)挺容易看出来的。你的code内层for loop每次都把cnt++，而cnt是max subset的大小，subset的大小不可能超过set size的大小。

这两个面试的人可能是忽略了后面这个for loop是在nums上做的, 而nums的和才是n，然后一起钻牛角尖了。这个牛角尖是钻的挺傻的，尤其是还两个人一起。

也可能是这俩人没看懂你在干什么，frustrated了就一起故意挑毛病。
你看看这样写是不是好懂些

1. 
   
2. for (int freq = nums.length-1; freq >= res.length; --freq) //freq: minimal value of max set
   
3.     for (int j = 0; j < nums[freq]; ++j) res.add(freq); //add all elements of value freq to result
   

复制代码

这样你只要一直强调res每个内循环长1，但是因为外循环的终止条件所以不会长于freq <= nums.length-1就好了。