一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 5524|回复: 31
收起左侧

Bloomberg 8/3 onsite

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

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

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

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

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

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

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

第二轮
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.. visit 1point3acres.com for more.
res 是存结果的set
  1. for (int i = nums.length-1; i>=0; i--) {
  2.     for (int j=0; j<nums[j] && cnt<i; j++){. 鍥磋鎴戜滑@1point 3 acres
  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 . Waral 鍗氬鏈夋洿澶氭枃绔,
小哥提示,我其实不想让他提示, 可能他觉得能缓和气氛
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();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4.                 int[] nums = new int[sets.length];. more info on 1point3acres.com
  5.                 int cnt = 0;. From 1point 3acres bbs
  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.                 }. more info on 1point3acres.com

  15.                 for (int i = sets.length;i>=0;i--) {
  16.                         if (cnt<=i) {. 1point 3acres 璁哄潧
  17.                                 for (int j=0; j<nums[i] && cnt<i;j++) {
  18.                                         res.add(i);. Waral 鍗氬鏈夋洿澶氭枃绔,
  19.                                         cnt++;
  20.                                 }  
  21.                         }
  22.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  23.                 return res;
  24.         }
  25. }
复制代码
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-8-6 03:11:33 | 显示全部楼层
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可能是太急了有点激动,可能别人没听明白吧
回复 支持 反对

使用道具 举报

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-google 1point3acres
嘛 毕竟有些时候复杂度就是看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
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)。不 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
你这个真能引申呀 不过你说的非常对 真是不想说那两位大哥的水平 最后还拒了我
你是不是最近准备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 就是错的
. From 1point 3acres bbs
因为你代码里面既有res.add(sets),也有res.add(i)所以看不太懂。。
anyway 后面的面试加油吧!

补充内容 (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了 本来是想说妹子在纽 ...
. From 1point 3acres bbs
异地多麻烦啊。。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有办公室么

补充内容 (2016-8-6 04:03):
. 1point3acres.com/bbs
你们家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,然后一起钻牛角尖了。这个牛角尖是钻的挺傻的,尤其是还两个人一起。

也可能是这俩人没看懂你在干什么,frustrated了就一起故意挑毛病。
你看看这样写是不是好懂些
  1. . visit 1point3acres.com for more.
  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就好了。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-1-17 04:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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