Bloomberg onsite

原帖地址:一亩三分地

去了bloomberg onsite。整个面下来,感觉问的挺基本的。但是我面的题目,都不是直接给你算法题。基本都是应用题。给你一个生活中的例子,让你解决,然后需要你自己抽象出算法题。我下面有的是是直接分享算法,有的还是应用题。有的时候需要跟他们讨论一下,input和output。每个问题结束,都会有follow up,以及时间空间复杂度分析。
第一轮:两个美国小哥:分享了一个学校经历
1 check duplicates: 一个数组,只有一个是重复的,找出这个重复的数。
解法:说了一下bruth force, 然后用hashset优化。

2 valid parenthesis: 一个string, 里面有各种各样的括号,判断这些空号是合法的,其他的符号就忽略。
解法:stack, leetcode有原题。

3 best time to buy and sell stock: 只交易一次,计算最大利润,以及买入和卖出价格。
解法:leetcode有原题

4 股票交易情况下,有很多的上市公司。你需要求得上市公司是哪一年上市的。已经设计好了一个api的function, 但是他返回的年份有一定的规则。然后时间复杂度是o(n). 你要利用已经给你的api, 去求得某一个股票的上市时间,并且时间复杂度要缩短。 如下:

//假设apple实际上市是1995年
public int getYear(int startTime, int endTime, String name) {
//1. 输入: 开始时间1990,结束时间1993,苹果; 输出:1990
//2. 输入: 开始时间1996, 结束时间1998,苹果; 输出0
//3. 输入: 开始时间1992, 结束时间1996,苹果;输出1995
}

解法binary search O(log n)

第二轮:一个美国人一个印度人:分享了一个学校经历
1 设计一个音乐播放器,设计class, 以及各种存储歌曲和playlist的方式。 然后完成shuffle的算法;
解法我是用hashmap动态存playlist,然后用arraylist存所有的歌(因为查找方便,randomly access),然后用设计纸牌的shuffle 算法做的music shuffle。

2 美国人打开chrome,说主页上会显示最长访问的8个网址,你如何实现这个功能。
解法:min heap + hashmap

3 我有一个function: doSomething(); 这个function有一个限制十秒内只能被call10次,如果十秒内多于10次,系统会报错。如何设计一个报错的功能。
解法:size 10的queue. 没超过10的size, enqueue new call, else dequeue 第一个call. 并比较当前call和第一个call的时间,超过10秒,输出warning。

4 印度人说,我现在心里有一个数,你可以说任意的一个数,我可以回答你大了还是小了。你要用什么的算法思想来猜数。
解法我说了两个,他没有说范围的时候, left window and right window –> right window以(2^n)的速度递增,而left window覆盖上一次的right window,确定了两个window,做binary search。
他说了范围直接用binary search。两个解法都是log(n)时间复杂度。

第三轮 一个美国人的manager:问了一下你喜欢的公司是什么样子的?
1 题目有点不记得了,貌似说了一下对象存在哪儿?我说heap. 然后他问了些关于garbage collection的东西和finalize()的东西。

2 不用乘法运算符,计算两个数的乘法
解法:用了位运算。经理人很好啊。因为我位运算做的不是那么熟练。一开始给了一个对的方向,告诉了位移法的步骤,然后他说那样不好写代码,然后提示了我一下,我就换了一个思考方式。最后做出来了。

3 开放题 你现在是一个风投顾问,帮很多有钱的人投资。你觉得什么样的情况会使得有些人赚更多钱,而有的人赚不到钱。
4 演示terminal, 聊天,开玩笑,聊天,继续开玩笑,结束

第四轮 美女manager
问了一下现在找工作的情况,和一些常规的hr问题:比如你选择工作的标准是什么,你最喜欢什么样的工作环境。然后聊天,然后让我赶紧去机场,别错过灰机了。

7月21日面的。现在还没有消息。心情很烦躁。发面经给马上要面的人。准备准备。有啥题,需要讨论的,留言就好。保佑保佑~~~ 好人一生平安