传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 3627|回复: 19
收起左侧

Bloomberg面经

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

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

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

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

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. visit 1point3acres.com for more.
就是一张纸上有好多的圆,各个圆之间可以重叠,问这些圆组成的图形的面积

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

使用道具 举报

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
. 鍥磋鎴戜滑@1point 3 acres
补充内容 ( ...

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

使用道具 举报

loveonts 发表于 2016-2-20 04:27:39 | 显示全部楼层
pengds 发表于 2016-2-20 03:59
不用monte carlo做吗? 那能详细说下怎么解吗
. Waral 鍗氬鏈夋洿澶氭枃绔,
先算出 整个平面 圆所覆盖的矩形边界 即对角线两个点的坐标 然后 一个个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
我设想过 但最后和面试官讨论下来发现 总会有一点短板 所以 最后面试官首肯了 稍微差一点的算法

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

使用道具 举报

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

问下,怎么根据一堆圆,算出那两个对交线的坐标呢?多谢!
回复 支持 反对

使用道具 举报

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.鏈枃鍘熷垱鑷1point3acres璁哄潧
其中一个面试官说这就是Monte Carlo,难道他是在考我期待我说不是。。。

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

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,难道他是在考我期待我说不是。。。

主要他俩一直在问问题,比如g ...
. 1point 3acres 璁哄潧
时间复杂度上 我的面试官 完全没有纠结 真本来就不是考时间复杂度的题 任何的优化 都没有啥意义 都是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
List list = new ArrayList() 我觉得楼主这个回答很好啊 定义变量最好就是从highest class 来定义啊. 1point3acres.com/bbs
如 ...

我当时不确定,回来查了下应该就是这个programming to interface什么的,不知道他想要什么答案。

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

使用道具 举报

yingying 发表于 2016-12-22 10:11:45 | 显示全部楼层
lz,为什么还会考到monte carlo。。。。是你说了自己有数学背景吗
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-26 22:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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