Bloomberg 8/3 onsite

无奈不能换名字 只能重新开号

今天面试面了两轮 应该跪了 感觉不太适合自己 甚至在面试的时候因为一直解释不了 差点没控制住脾气 最后要了五分钟来calm down

第一轮
1. 一个模拟题 分清楚就一点难度都没有了 秒解 纯粹是看一下我这个读生物的人的编程能力
2. 看两个listnode是否聚合到一点

第二轮
1. H index的变型 让

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

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

出了tree next node 的题目
不是完整的树 处理有点麻烦 由于剩下15分钟，说 时间不够了 要我写伪代码， 好的， 写过5分钟写完， 让我写完整的code。最后写完

我真心是很难交流 很无语 也算是作 如果是跪 我也觉得没什么必要去的吧

1. public class Solution {
   
2.         public ArrayList<Integer> hIndex(int[] sets) {
   
3.                 ArrayList<Integer> res = new ArrayList();
   
4.                 int[] nums = new int[sets.length];
   
5.                 int cnt = 0;
   
6.                 for (int i =0; i<sets.length;i++) {
   
7.                         if (sets[i]<=0) sets[i]=0;
   
8.                         if (sets[i]>=sets.length) {
   
9.                                 res.add(sets[i]);
   
10.                                 sets[i]=0;
    
11.                                 cnt++;
    
12.                         }
    
13.                         nums[sets[i]]++;
    
14.                 }
    
15. 
    
16.                 for (int i = sets.length;i>=0;i--) {
    
17.                         if (cnt<=i) {
    
18.                                 for (int j=0; j<nums[i] && cnt<i;j++) {
    
19.                                         res.add(i);
    
20.                                         cnt++;
    
21.                                 }  
    
22.                         }
    
23.                 }
    
24.                 return res;
    
25.         }
    
26. }

复制代码

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可能是太急了有点激动，可能别人没听明白吧

其实这个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就好了。

lz能解释一下为啥这个是ON么，我也想不通。。
直接用标准的HINDEX解法，维护一个array of arraylist应该就能JAVA ON解决了吧

whitesunday 发表于 2016-8-5 00:25
lz能解释一下为啥这个是ON么，我也想不通。。
直接用标准的HINDEX解法，维护一个array of arraylist应该就 ...

是的 原本的hindex并不需要求出最大size的数组 可以不用两个loop 一个正确的衡量big O的方法 是要查看最差运行次数 而不能简单粗暴的看有几个loop

runrain 发表于 2016-8-5 03:44
是的 原本的hindex并不需要求出最大size的数组 可以不用两个loop 一个正确的衡量big O的方法 是要查看最 ...

嘛 毕竟有些时候复杂度就是看worst case的

whitesunday 发表于 2016-8-5 11:29
嘛 毕竟有些时候复杂度就是看worst case的

准确是看average case。 但是这一题worst case 就是 2*n 所以还是O（n）  我没有算错了吧？

tree next node 是Binary tree 么？ 和完整树有什么关系？

blackrose 发表于 2016-8-5 12:42
tree next node 是Binary tree 么？ 和完整树有什么关系？

是bs 没有关系 处理复杂一点而已

我也不明白，是不是太笨了。。。

Hualiang 发表于 2016-8-5 15:39
我也不明白，是不是太笨了。。。

用鸽笼问题理解  最坏的情况下 就是 最后一个nums 塞得是整个数组，n. 而之前都是0， 所以实际遍历 就是 n-1+n = 2*n 举个例子就会非常明白