未名空间十大: bloomberg和Google面经发包子攒人品

Sunday, June 8, 2014

bloomberg和Google面经发包子攒人品

发信人: irisxiaoxue (小雪), 信区: JobHunting
标题: bloomberg和Google面经发包子攒人品
发信站: BBS 未名空间站 (Thu Apr 17 17:02:32 2014, 美东)

Google(summer intern)
1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
，矩形的4个角都是1.
leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
意。不知道有没有复杂度更少的算法。

2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
目。之后把队打乱，
跟据高度和比自己高的人的数目还原原来的队列。
我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
算法。

Bloomberg:
1. 给一个数组： 6， 3， 10， 5， 16， 8， 4， 2， 1
找出这个数组的顺序。写一个程序，input是数组里的一个数，Output是从这个数开始
的整个数组。
2. 实现一个BFS算法。
3. 一个数组，里面有成对出现的数，也有单个的数，把单个的数找出来（leetcode原
题）。
4. 一个公司有好多员工，员工之间的关系储存为（employee ID, manager ID) 这样的
pair。要求写一个数据结构，储存这些员工之前的关系。
基于这样的数据结构写出：
1)查找employee的manager.
2)给一个employee和一个manager,查找这个manger是不是这个员工的直接或简介
manager(manager的manager这样的）
3)打印出一个manager手下所有的直接或者间接员工。
4）向这个数组里增加新的(employee, manager)关系。
并给出复杂度分析。

最后推荐一个算法群229623621,里面牛人很多，群里还自己做了OJ，讨论氛围很活跃。

发一些包子攒人品，期待好消息

--
※ 修改:·irisxiaoxue 於 Apr 17 22:07:59 2014 修改本文·[FROM: 130.]
※ 来源:·WWW 未名空间站网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 129.]