Bloomberg 11.30 扭腰 onsite

2两轮coding + HR 闲聊 + Hiring Manger Background 闲聊

除了HR，今天面的全是三哥/姐，咖喱国莫名的缘分。。。

第一轮：一个三姐，两道题

第一题：
给一个有序数列如【17， 11， 8， 21， 15，31】对于每个数，请找出它之后第一个比它大的数（如果存在的话，没有就算了）。
样例输出为（17，21），（11，21），（8，21），（21，31），（15，31），输出顺序不限

我的做法：
1. 最暴力的两个for，O (N^2) 时间解决
2. BST存一下

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ring length。这么用的话复杂度不是linear的。
2. inerval 数量太多，memory存不下怎么办？interval 都是non-negative integer，用线段树存磁盘里，深度最深不超过32，是个常数，可以证明在线性时间内解决。占用空间就有点大了, 而且线段树操作的话，磁盘io才是瓶颈。我没想出别的方法，面试官表示接受没追问。

祝楼主好运先~
想请教一下第二轮最后一道题
其实感觉主要就是merge intervals，这个怎么能在O（M）时间内？排序不就已经是O（MlogM）了吗？
然后follow up是有特别多的interval，我感觉是不是有点分治的思想，就是先merge一部分，再读下一批intervals到内存来merge，然后最后再一起merge？

czcbangkai 发表于 2017-12-2 04:10
LZ第一题意思就是 17 11 8 打入栈中, 然后碰到21把栈里的内容打出来和21一起输出, 然后再把21打进去后面以 ...

應該是的 就是存比自己小的值到遇到比自己大的

白菜3383 发表于 2017-12-2 03:47
cong楼主，题目做的棒，聊四轮就稳了！  我周三面的，今天接到HR电话offer了

恭喜lz 沾沾光
hr是直接打電話還是會先寄信跟你約時間呢！

cong楼主，题目做的棒，聊四轮就稳了！  我周三面的，今天接到HR电话offer了

四轮稳啊LZ, 要恭喜offer了

白菜3383 发表于 2017-12-2 03:47
cong楼主，题目做的棒，聊四轮就稳了！  我周三面的，今天接到HR电话offer了

同学，联系你的HR是katie吗？

楼主基本功很扎实，肯定稳了

LZ第一题意思就是 17 11 8 打入栈中, 然后碰到21把栈里的内容打出来和21一起输出, 然后再把21打进去后面以此类推, 每个元素最多被操作2次, 对吗?

楼主收到offer了么，我也是昨天面了四轮

第一题可以用heap吧

cin13 发表于 2017-12-2 04:01
同学，联系你的HR是katie吗？

嗯嗯是的

白菜3383 发表于 2017-12-2 04:44
嗯嗯是的

唉……我是katie面的。刚刚收到据信……