一亩三分地论坛

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

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

Bloomberg面经

[复制链接] |试试Instant~ |关注本帖
billyli8866 发表于 2016-2-17 03:51:03 | 显示全部楼层 |阅读模式

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

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

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

x
去年11月就越好电面,被面试官放鸽子后一直被HR拖到今年1月才电面,二月初onsite,悲剧地两轮游。

电面:给一个DAG和一个起点,返回所有的路径。follow up是如果这个图有cycle怎么办。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

onsite:
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 第一轮
算n的k次方,leetcode原题
写一个hashmap加上double linkedlist的数据结构
把bst flatten成linked list

第二轮. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
monte carlo 算一堆圆面积那道题。一道题写了快一个小时,两个面试官都不怎么懂java,我也不怎么懂c++。我觉得这道题很简单也不太想写,他们俩杂七杂八地问了好多问题,不知不觉时间就过去了。大概因为只做了一道题,过了一会HR过来把我请了出去。感觉这两个面试官不太喜欢我,心里很郁闷。


评分

2

查看全部评分

pengds 发表于 2016-2-17 11:30:49 | 显示全部楼层
楼主能麻烦详细讲下算面积那道题吗?
回复 支持 反对

使用道具 举报

 楼主| billyli8866 发表于 2016-2-19 12:58:37 | 显示全部楼层
pengds 发表于 2016-2-17 11:30
楼主能麻烦详细讲下算面积那道题吗?

就是一张纸上有好多的圆,各个圆之间可以重叠,问这些圆组成的图形的面积
回复 支持 反对

使用道具 举报

pengds 发表于 2016-2-20 02:34:18 | 显示全部楼层
billyli8866 发表于 2016-2-19 12:58
就是一张纸上有好多的圆,各个圆之间可以重叠,问这些圆组成的图形的面积

我想的解法是找一个长方形包含所有圆,在里面产生随机数,通过和圆心距离来判断是否在圆内,再根据落在圆内和圆外的比例计算面积,是这样吗
回复 支持 反对

使用道具 举报

loveonts 发表于 2016-2-20 03:22:13 | 显示全部楼层
我和你一样的题目 第二轮太差了 我拿到圆面积的题 写了15分钟 就做完了 这道题不是Monte Carlo

补充内容 (2016-2-20 03:22):
这个不是Monte Carlo 是数值仿真
回复 支持 反对

使用道具 举报

pengds 发表于 2016-2-20 03:59:30 | 显示全部楼层
loveonts 发表于 2016-2-20 03:22
我和你一样的题目 第二轮太差了 我拿到圆面积的题 写了15分钟 就做完了 这道题不是Monte Carlo

补充内容 ( ...

不用monte carlo做吗? 那能详细说下怎么解吗
回复 支持 反对

使用道具 举报

loveonts 发表于 2016-2-20 04:27:39 | 显示全部楼层
pengds 发表于 2016-2-20 03:59
不用monte carlo做吗? 那能详细说下怎么解吗
-google 1point3acres
先算出 整个平面 圆所覆盖的矩形边界 即对角线两个点的坐标 然后 一个个pixel去查是否属于某个圆 if so 加一个count 最后 算一下 属于圆的pixel的比例 比上总面积即可
回复 支持 反对

使用道具 举报

pengds 发表于 2016-2-20 06:05:17 | 显示全部楼层
loveonts 发表于 2016-2-20 04:27
先算出 整个平面 圆所覆盖的矩形边界 即对角线两个点的坐标 然后 一个个pixel去查是否属于某个圆 if so  ...

谢谢。。。问下你面经里getrandom 如何保证O(1) 我的想法和你一样 建立一个数组存放已经插入的数 再get一个random index来得到random object. 但是如果有删除的话 在数组里删除object 时间是O(n)  就达不到O(1) 了 如果用双链表存 那么 getrandom 就不能保证O(1) 了
回复 支持 反对

使用道具 举报

loveonts 发表于 2016-2-20 06:24:45 | 显示全部楼层
pengds 发表于 2016-2-20 06:05
谢谢。。。问下你面经里getrandom 如何保证O(1) 我的想法和你一样 建立一个数组存放已经插入的数 再get一 ...

我设想过 但最后和面试官讨论下来发现 总会有一点短板 所以 最后面试官首肯了 稍微差一点的算法
回复 支持 反对

使用道具 举报

pengds 发表于 2016-2-20 06:27:30 | 显示全部楼层
loveonts 发表于 2016-2-20 06:24. from: 1point3acres.com/bbs
我设想过 但最后和面试官讨论下来发现 总会有一点短板 所以 最后面试官首肯了 稍微差一点的算法

好的 谢谢 祝你拿到offer!
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-2-20 11:13:44 | 显示全部楼层
loveonts 发表于 2016-2-20 04:27
先算出 整个平面 圆所覆盖的矩形边界 即对角线两个点的坐标 然后 一个个pixel去查是否属于某个圆 if so  ...
. visit 1point3acres.com for more.
问下,怎么根据一堆圆,算出那两个对交线的坐标呢?多谢!
回复 支持 反对

使用道具 举报

yuqi2 发表于 2016-2-20 17:02:45 | 显示全部楼层
楼主 能详细说下 写一个hashmap加上double linkedlist的数据结构 这道题么? 谢谢啦
回复 支持 反对

使用道具 举报

 楼主| billyli8866 发表于 2016-2-21 01:31:20 | 显示全部楼层
loveonts 发表于 2016-2-20 03:22
我和你一样的题目 第二轮太差了 我拿到圆面积的题 写了15分钟 就做完了 这道题不是Monte Carlo

补充内容 ( ...

其中一个面试官说这就是Monte Carlo,难道他是在考我期待我说不是。。。

主要他俩一直在问问题,比如generate多少个点可以得到0.001的精度,variance的公式是什么。遍历所有圆的时候怎样可以快一些break,我说根据圆的半径从大到小sort一下。另一个面试官不满意,让我用kd tree找到最近的k个圆,然后问我average的running time是多少。我也不知道怎么算average的time,因为就算找到最近的圆也要看圆的半径是多少啊,耽误了好久的时间最后他说那所有圆的半径一样好了。。。

还有我定义一个list的时候写 List<Integer> list = new ArrayList<>(),他问我为什么前面用List而不用ArrayList,我说方便以后觉得ArrayList不好的时候改成其他种类的List,他一副你这是放屁的表情,然后说如果你不知道的话就说不知道。我就很尴尬,也不知道该说我知道还是说我不知道。

不知道他们是不是也问了你这么多问题
回复 支持 反对

使用道具 举报

 楼主| billyli8866 发表于 2016-2-21 01:33:24 | 显示全部楼层
yuqi2 发表于 2016-2-20 17:02.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主 能详细说下 写一个hashmap加上double linkedlist的数据结构 这道题么? 谢谢啦

搞懂LRU那道题就行了,这个要简单多了
回复 支持 反对

使用道具 举报

loveonts 发表于 2016-2-21 03:44:09 | 显示全部楼层
billyli8866 发表于 2016-2-21 01:31. from: 1point3acres.com/bbs
其中一个面试官说这就是Monte Carlo,难道他是在考我期待我说不是。。。

主要他俩一直在问问题,比如g ...
. visit 1point3acres.com for more.
Monte Carlo 我那个倒是没睡

你那个精确到0.001我也问了 我就是 pixel精度 也精确到0.001 他就没多问

至于break这一点 我并木有排序 我的做法就是 扫描过程中 只要这个pixel发现在任何一个圆内就break掉 进入下一个pixel点 面试官 也没提出异议 可能你的面试官 比较坑吧
回复 支持 反对

使用道具 举报

loveonts 发表于 2016-2-21 03:45:28 | 显示全部楼层
billyli8866 发表于 2016-2-21 01:31
其中一个面试官说这就是Monte Carlo,难道他是在考我期待我说不是。。。.1point3acres缃
-google 1point3acres
主要他俩一直在问问题,比如g ...
. 1point3acres.com/bbs
时间复杂度上 我的面试官 完全没有纠结 真本来就不是考时间复杂度的题 任何的优化 都没有啥意义 都是O(N^3) 我那一轮 后两道 一道是栈实现队列 是考到时间复杂度了 另一道是bit的题目
回复 支持 反对

使用道具 举报

pengds 发表于 2016-2-21 05:24:54 | 显示全部楼层
billyli8866 发表于 2016-2-21 01:31. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
其中一个面试官说这就是Monte Carlo,难道他是在考我期待我说不是。。。

主要他俩一直在问问题,比如g ...

List<Integer> list = new ArrayList<>() 我觉得楼主这个回答很好啊 定义变量最好就是从highest class 来定义啊
如果以后要改 比如 list = new LinkedList<>() 也是可以通过的 为什么面试官不同意
回复 支持 反对

使用道具 举报

pengds 发表于 2016-2-21 08:58:49 | 显示全部楼层
billyli8866 发表于 2016-2-21 01:31
其中一个面试官说这就是Monte Carlo,难道他是在考我期待我说不是。。。

主要他俩一直在问问题,比如g ...

另外楼主你的精度和variance是怎么回答的
回复 支持 反对

使用道具 举报

 楼主| billyli8866 发表于 2016-2-21 09:11:00 | 显示全部楼层
pengds 发表于 2016-2-21 05:24. 1point 3acres 璁哄潧
List list = new ArrayList() 我觉得楼主这个回答很好啊 定义变量最好就是从highest class 来定义啊
如 ...

我当时不确定,回来查了下应该就是这个programming to interface什么的,不知道他想要什么答案。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

variance那个我完全没有头绪,问是不是normal distribution,他们好像默认了,然后告诉我variance是1/根号下n
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 15:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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