一亩三分地论坛

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

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

Bloomberg 电面面经

[复制链接] |试试Instant~ |关注本帖
nibuxing 发表于 2015-3-28 03:23:39 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Bloomberg - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面完的BB,是个美国小哥面的,人很好。
1. Why BB?
2. 简历的project
3. OO programming的特点和优点
4. create一个object后,为什么不直接用object的field操作,比如date class, 有year, month, day,为什么不直接day.year = 2015, 而要day.setyear(2015); 这一题没答得好。
5. 算法题,有一个站台,有n个卖票窗口,每个卖票窗口有a[i]张票,a是一个array,然后每张票的价格和这个窗口剩余票数的数量相等,比如第一个站台有5张票,那么这个站台第一张卖出去的票就是5刀,第二张卖出去的票就是4刀。如果我想卖m张票,求卖出的最大价格。
6. 让你提问

答下来感觉还不错,算法题磕磕绊绊不过最后bug free了,做完跟他一起go through一个example。准备了我一个礼拜,两天看面经从早看到晚啊。。。希望能拿到onsite

评分

3

查看全部评分

 楼主| nibuxing 发表于 2015-3-28 11:52:20 | 显示全部楼层
liudongxue1991 发表于 2015-3-28 05:41
楼主是怎样解决的 就是每次查找都遍历一遍数组找最大值 直到数组的最大值为0吗?
还是维护一个max heap  ...

我第一反应是一次次找最大值,但觉得这个方法太naive了,然后就想到用max heap,但我不会写。。。立马绞尽脑汁想了第三种方法:
先将array排序,变成[5, 4, 3, 2, 1], 然后用一个pointer来记录当前位置。int p = 0;
第一张肯定是p[0] = 5, 然后减去1,变成[4, 4, 3, 2, 1]。
随后写一个while loop:
检查左边是不是大于等于当前的值,如果是,p往左移,直到移到左边比当前小。
检查右边是不是比当前大,如果是,p往右移一格。
然后当前的位置的票价就是要卖的价格,result += a[p], a[p]--;
这个例子中,[4, 4, 3, 2, 1],p = 0,检查左边是没东西,检查右边并不比当前大,就变成[3, 4, 3, 2, 1],p = 0,检查左边是没东西,检查右边比自己大,移动到右边,减去1,变成[3, 3, 3, 2, 1], p = 1,检查左边等于当前值,往左移,p = 0,检查右边并不比当前大,当前位置减去1,变成[2, 3, 3, 2, 1]。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
具体实现的时候会有一个地方比较tricky,可以自己写一下看看。
排序是nlogn,后面移来移去应该是O(n),所以总复杂度应该是nlogn吧。。。
回复 支持 1 反对 0

使用道具 举报

liudongxue1991 发表于 2015-3-28 05:07:26 | 显示全部楼层
楼主讲的好详细。

想请问下 算法题是怎样解决的? 我只能推出来 题目等价于 n个数字的和为m 求 n个数字平方和的最大值...
回复 支持 反对

使用道具 举报

 楼主| nibuxing 发表于 2015-3-28 05:13:59 | 显示全部楼层
liudongxue1991 发表于 2015-3-28 05:07.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主讲的好详细。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
想请问下 算法题是怎样解决的? 我只能推出来 题目等价于 n个数字的和为m 求 n个数字 ...

我题目可能没表达清楚,我给你举个例子:. 1point 3acres 璁哄潧
比如有5个窗口,[4, 3, 2, 5, 1],代表第一个窗口有4张票,第二个窗口3张...当m = 4时,代表我想卖3张票子,怎么卖这四张票可以得到最大的profit呢。
第一张票应该是第四个窗口卖,5刀,然后array就变成[4, 3, 2, 4, 1],因为第四个窗口卖掉了一张。. 1point 3acres 璁哄潧
第二张票应该在第一个或者第四个窗口卖,因为它们都是四刀票,我们就在第一个窗口卖,array就变成[3, 3, 2, 4, 1]。
第三张票应该在第四个窗口卖,卖四刀,卖完后array就变成[3, 3, 2, 3, 1]
第四张票应该在第一个第二个或者第四个窗口卖,卖3刀,假设我们在第一个窗口卖,买完后array变成[2, 3, 2, 3, 1
返回的总profit就是5 + 4 + 4 + 3 = 16

补充内容 (2015-3-28 05:14):
写错了,当m = 4时,代表我想卖4张票
回复 支持 反对

使用道具 举报

miraclebingo 发表于 2015-3-28 05:25:27 | 显示全部楼层
没太理解lz说的第五题什么意思,是要把m张票分配给n个窗口去买获得最大收益吗?这难道不是把所有票放到同一个窗口卖赚最多吗. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2015-3-28 05:26):
刚看到楼主的回复。。
回复 支持 反对

使用道具 举报

liudongxue1991 发表于 2015-3-28 05:41:03 | 显示全部楼层
nibuxing 发表于 2015-3-28 05:13. 鍥磋鎴戜滑@1point 3 acres
我题目可能没表达清楚,我给你举个例子:
比如有5个窗口,[4, 3, 2, 5, 1],代表第一个窗口有4张票,第 ...

楼主是怎样解决的 就是每次查找都遍历一遍数组找最大值 直到数组的最大值为0吗?
还是维护一个max heap 每次 拿出root, 把root的值-1, 如果root.val-1不为0的话就重新插入heap  一直这样直到 heap为空呢?
回复 支持 反对

使用道具 举报

miraclebingo 发表于 2015-3-28 06:04:45 | 显示全部楼层
我能想到的算法是这样的,不知道lz的是不是更好。。
就是先用大小为m的min heap找出array里最大的m个数,然后做这样一个循环,就是从最大开始,减去第二大的值(他们的差表示一次性可以在该窗口买几张),乘以自己的order数(最大乘以1,第二大乘以2),直到sum大于等于m,这样就知道了在最大窗口买几张,第二大买几张,复杂度是O(nlogm+m)。。
估计这样写出来会bug一堆。。
回复 支持 反对

使用道具 举报

liudongxue1991 发表于 2015-3-28 06:07:44 | 显示全部楼层
miraclebingo 发表于 2015-3-28 06:04. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我能想到的算法是这样的,不知道lz的是不是更好。。
就是先用大小为m的min heap找出array里最大的m个数, ...

嗯 heap应该就是比较好的解法了吧 nlogm的 直接用数组的话应该就nm了
回复 支持 反对

使用道具 举报

 楼主| nibuxing 发表于 2015-3-28 11:52:43 | 显示全部楼层
miraclebingo 发表于 2015-3-28 06:04
我能想到的算法是这样的,不知道lz的是不是更好。。
就是先用大小为m的min heap找出array里最大的m个数, ...

我的解法已经回复啦,可以参考一下哦
回复 支持 反对

使用道具 举报

miraclebingo 发表于 2015-3-28 14:45:55 | 显示全部楼层
nibuxing 发表于 2015-3-28 11:52
我的解法已经回复啦,可以参考一下哦

我觉得lz后面移来移去的方法挺好!amortize之后是O(m),我估计我面试的时候一紧张就想不出来了。。
话说在hackerrank上只用写方法吗还是main函数和include那些东西都要写,然后run code?
回复 支持 反对

使用道具 举报

 楼主| nibuxing 发表于 2015-3-28 21:17:54 | 显示全部楼层
miraclebingo 发表于 2015-3-28 14:45.鐣欏璁哄潧-涓浜-涓夊垎鍦
我觉得lz后面移来移去的方法挺好!amortize之后是O(m),我估计我面试的时候一紧张就想不出来了。。
话 ...

我一开始想对70%吧,后面是和考官慢慢探讨然后全想出来的。
每个公司不一样,BB家面试用hackerrank是相当于一个有自动补全的白板。像leetcode上一样,你只要把这个method给写了就可以了,他也没run code。
回复 支持 反对

使用道具 举报

miraclebingo 发表于 2015-3-29 04:08:10 | 显示全部楼层
nibuxing 发表于 2015-3-28 21:17
我一开始想对70%吧,后面是和考官慢慢探讨然后全想出来的。
每个公司不一样,BB家面试用hackerrank是相 ...

感觉bb家的考官还挺nice的,祝lz好运
回复 支持 反对

使用道具 举报

 楼主| nibuxing 发表于 2015-3-29 04:44:12 | 显示全部楼层
miraclebingo 发表于 2015-3-29 04:08
感觉bb家的考官还挺nice的,祝lz好运

恩,谢谢!
回复 支持 反对

使用道具 举报

Jeremian1990 发表于 2015-3-30 04:38:02 | 显示全部楼层
请问楼主,BB是怎么投的?什么时候啊?
回复 支持 反对

使用道具 举报

 楼主| nibuxing 发表于 2015-3-30 04:56:53 | 显示全部楼层
Jeremian1990 发表于 2015-3-30 04:38
请问楼主,BB是怎么投的?什么时候啊?

我海投的,四周前投的。
回复 支持 反对

使用道具 举报

zn88358800 发表于 2015-10-8 11:13:25 | 显示全部楼层
如果 m大于sum(a[i]) 的时候 那这个题的结果就是定值了吧?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 21:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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