一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2105|回复: 31
收起左侧

Bloomberg 8/3 onsite

[复制链接] |试试Instant~ |关注本帖
runrain 发表于 2016-8-4 12:11:53 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Bloomberg - 内推 - Onsite |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

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

第一轮. 1point 3acres 璁哄潧
1. 一个模拟题 分清楚就一点难度都没有了 秒解 纯粹是看一下我这个读生物的人的编程能力.鏈枃鍘熷垱鑷1point3acres璁哄潧
2. 看两个listnode是否聚合到一点. from: 1point3acres.com/bbs
. visit 1point3acres.com for more.
第二轮
1. H index的变型 让我output max subset 注意是subset!
就是在这题我没忍住,第一个方法sort这个都毫无疑问, 第二个解法 就是用counting sort, 因为是subset, 我就压缩进一个nums的array里,which means the nums array represent the count of index in the set.
res 是存结果的set
  1. for (int i = nums.length-1; i>=0; i--) {
  2.     for (int j=0; j<nums[j] && cnt<i; j++){
  3.           res.add(i);
  4.           cnt++;
  5.      }
  6. }
复制代码
最后一边count 一边reverse 在这里 套了两重循环, 老外一把抓住 这是O(n^2)不是O(n),因为两重loop,结果国人大哥也说是呀。
我瞬间无语了, 解释了一遍,不行 还坚持己见,然后我说跑个case 你看看好了,他们说不用,再解释第三遍,国人大哥很鄙视的时候说 1+3 难道你要for loop弄四遍吗?返回4吗
我最后说 如果 你要 出现 4个1 我只能回答是, 你要我返回subset 又不是大小。 他们还是不同意,我最后说 你们C++可能可以 但是java很遗憾并不行
(最后我需要5分钟来calm down,有一种 世人笑我太疯癫,我笑世人看不穿的感觉). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2. reverse string . 1point 3acres 璁哄潧
小哥提示,我其实不想让他提示, 可能他觉得能缓和气氛
3. 国人大哥 出了tree next node 的题目
不是完整的树 处理有点麻烦 由于剩下15分钟,说 时间不够了 要我写伪代码, 好的, 写过5分钟写完, 让我写完整的code。最后写完

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

评分

3

查看全部评分

 楼主| runrain 发表于 2016-8-5 22:50:25 | 显示全部楼层
  1. public class Solution {
  2.         public ArrayList<Integer> hIndex(int[] sets) {
  3.                 ArrayList<Integer> res = new ArrayList();
    . From 1point 3acres bbs
  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. . From 1point 3acres bbs
  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.                         }. 1point 3acres 璁哄潧
  23.                 }
  24.                 return res;
  25.         }
  26. }
复制代码
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-8-6 03:11:33 | 显示全部楼层
runrain 发表于 2016-8-5 11:49
准确是看average case。 但是这一题worst case 就是 2*n 所以还是O(n)  我没有算错了吧?
.1point3acres缃
不知道原题是啥,看代码,num一共被统计了n次,两层for loop受到num的限制,最多n次,所以应该是O(n)。不过这题的best、worst、average都是O(n),不适合举例说明,直接归纳更好一些。.1point3acres缃
. 1point 3acres 璁哄潧
具体考察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更重要。
. more info on 1point3acres.com
补充内容 (2016-8-6 03:12):
LZ可能是太急了有点激动,可能别人没听明白吧
回复 支持 反对

使用道具 举报

whitesunday 发表于 2016-8-5 00:25:52 | 显示全部楼层
lz能解释一下为啥这个是ON么,我也想不通。。
直接用标准的HINDEX解法,维护一个array of arraylist应该就能JAVA ON解决了吧
回复 支持 反对

使用道具 举报

 楼主| runrain 发表于 2016-8-5 03:44:49 来自手机 | 显示全部楼层
whitesunday 发表于 2016-8-5 00:25
lz能解释一下为啥这个是ON么,我也想不通。。
直接用标准的HINDEX解法,维护一个array of arraylist应该就 ...

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

使用道具 举报

whitesunday 发表于 2016-8-5 11:29:17 | 显示全部楼层
runrain 发表于 2016-8-5 03:44
是的 原本的hindex并不需要求出最大size的数组 可以不用两个loop 一个正确的衡量big O的方法 是要查看最 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
嘛 毕竟有些时候复杂度就是看worst case的
回复 支持 反对

使用道具 举报

 楼主| runrain 发表于 2016-8-5 11:49:16 | 显示全部楼层
whitesunday 发表于 2016-8-5 11:29
嘛 毕竟有些时候复杂度就是看worst case的

准确是看average case。 但是这一题worst case 就是 2*n 所以还是O(n)  我没有算错了吧?
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-8-5 12:42:01 | 显示全部楼层
tree next node 是Binary tree 么? 和完整树有什么关系?
回复 支持 反对

使用道具 举报

 楼主| runrain 发表于 2016-8-5 12:43:38 来自手机 | 显示全部楼层
blackrose 发表于 2016-8-5 12:42.1point3acres缃
tree next node 是Binary tree 么? 和完整树有什么关系?

是bs 没有关系 处理复杂一点而已
回复 支持 反对

使用道具 举报

Hualiang 发表于 2016-8-5 15:39:26 | 显示全部楼层
我也不明白,是不是太笨了。。。
回复 支持 反对

使用道具 举报

 楼主| runrain 发表于 2016-8-5 22:20:14 | 显示全部楼层
Hualiang 发表于 2016-8-5 15:39
我也不明白,是不是太笨了。。。

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

使用道具 举报

 楼主| runrain 发表于 2016-8-6 03:15:06 | 显示全部楼层
sheepmiemies 发表于 2016-8-6 03:11
不知道原题是啥,看代码,num一共被统计了n次,两层for loop受到num的限制,最多n次,所以应该是O(n)。不 ...
-google 1point3acres
你这个真能引申呀 不过你说的非常对 真是不想说那两位大哥的水平 最后还拒了我
你是不是最近准备BB呀 我换了一个号出来了 以前真名发的 心里太慌
回复 支持 反对

使用道具 举报

whitesunday 发表于 2016-8-6 03:26:10 | 显示全部楼层

你这代码跑不过吧。首先你第二个forloop里面nums越界了,其次你result里面到底放的是sets还是i啊?
回复 支持 反对

使用道具 举报

 楼主| runrain 发表于 2016-8-6 03:29:13 | 显示全部楼层
whitesunday 发表于 2016-8-6 03:26
你这代码跑不过吧。首先你第二个forloop里面nums越界了,其次你result里面到底放的是sets还是i啊?

第一个越界了 没注意 你明白大意就好 放的就是i 如果放的是sets 就是错的
回复 支持 反对

使用道具 举报

 楼主| runrain 发表于 2016-8-6 03:31:21 | 显示全部楼层
sheepmiemies 发表于 2016-8-6 03:11. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
不知道原题是啥,看代码,num一共被统计了n次,两层for loop受到num的限制,最多n次,所以应该是O(n)。不 ...

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

使用道具 举报

whitesunday 发表于 2016-8-6 03:36:18 | 显示全部楼层
runrain 发表于 2016-8-6 03:29
第一个越界了 没注意 你明白大意就好 放的就是i 如果放的是sets 就是错的

因为你代码里面既有res.add(sets),也有res.add(i)所以看不太懂。。
anyway 后面的面试加油吧!-google 1point3acres

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

使用道具 举报

 楼主| runrain 发表于 2016-8-6 03:38:44 | 显示全部楼层
whitesunday 发表于 2016-8-6 03:36
因为你代码里面既有res.add(sets),也有res.add(i)所以看不太懂。。
anyway 后面的面试加油吧!

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

使用道具 举报

whitesunday 发表于 2016-8-6 03:59:55 | 显示全部楼层
runrain 发表于 2016-8-6 03:38.鐣欏璁哄潧-涓浜-涓夊垎鍦
因为前面是用处理大于的 后面就是用来回复被压缩数组的 我已经接了Snapchat的offer了 本来是想说妹子在纽 ...

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

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

使用道具 举报

 楼主| runrain 发表于 2016-8-6 04:05:33 | 显示全部楼层
whitesunday 发表于 2016-8-6 03:59
异地多麻烦啊。。snapchat NYC有办公室么. 1point 3acres 璁哄潧

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

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

使用道具 举报

hxtang 发表于 2016-8-6 04:31:30 | 显示全部楼层
其实这个O(n)挺容易看出来的。你的code内层for loop每次都把cnt++,而cnt是max subset的大小,subset的大小不可能超过set size的大小。

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

也可能是这俩人没看懂你在干什么,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就好了。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 18:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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