m*********p
发帖数: 26 | 1 之前在网上投的简历，约了时间，今天刚刚面的。面我是个三哥，口音不重，人也还好
，问题的难度比较公道，自己算正常发挥。
先过了下简历，这个主要我在说，然后他按照他理解的复述了一遍，气氛还算轻松。
然后就是技术问题了：
一个array里面存了大量的股票价格，然后问怎么找出top-k, lowest-k.
这个出现得很多，用min/max- heap就可以了。
又问怎么找出某段时间里的某个公司股票价格的范围。我对这个问题的理解是怎么样能
够快速access任意时刻的价格。我说用array. 他说这个data随着时间的不断的grow。
我就说用linked list好了. 他问可以更快吗？最后就说用hashmap，他说这可以work.
也不知道有没有更好的。求版上牛人指点。
然后就来了个简单的brain teaser, 100 doors那个题，秒掉。
接下来问了个reverse an integer. 这个也不难，说了下思路。忘记了负数的情况，经
过他提醒，稍微调整了下。
最后他让我问他问题，我就问Bloomberg现在在解决那些technical challenge. 然后就
听他扯了几分钟大数据，high frequency trading中要求的快速算法什么的。
总的来说问的问题比较基础，这个三哥也没有故意为难的意思。
今年的第一个电面就结束了，希望至少能move on到高大上的扭腰onsite走一遭。 |
z****0
发帖数: 4413 | 2 bless
.
【在 m*********p 的大作中提到】
: 之前在网上投的简历，约了时间，今天刚刚面的。面我是个三哥，口音不重，人也还好
: ，问题的难度比较公道，自己算正常发挥。
: 先过了下简历，这个主要我在说，然后他按照他理解的复述了一遍，气氛还算轻松。
: 然后就是技术问题了：
: 一个array里面存了大量的股票价格，然后问怎么找出top-k, lowest-k.
: 这个出现得很多，用min/max- heap就可以了。
: 又问怎么找出某段时间里的某个公司股票价格的范围。我对这个问题的理解是怎么样能
: 够快速access任意时刻的价格。我说用array. 他说这个data随着时间的不断的grow。
: 我就说用linked list好了. 他问可以更快吗？最后就说用hashmap，他说这可以work.
: 也不知道有没有更好的。求版上牛人指点。
|
k*****m
发帖数: 14 | 3 1. top-k, lowest-k
可以用selection ranking，O(n)
2. stock
感觉可以用segment tree，查询，插入都是O(lgn) |
m*********p
发帖数: 26 | 4 大牛！thanks for sharing. 赶紧补补课。
【在 k*****m 的大作中提到】
: 1. top-k, lowest-k
: 可以用selection ranking，O(n)
: 2. stock
: 感觉可以用segment tree，查询，插入都是O(lgn)
|
m*********p
发帖数: 26 | 5 selection ranking 貌似只能找到kth largest或者kth lowest， 而对于找到全部top
k个或者lowest k个元素不能在O(n)找到。还是有其他的tweak可以搞定？
【在 k*****m 的大作中提到】
: 1. top-k, lowest-k
: 可以用selection ranking，O(n)
: 2. stock
: 感觉可以用segment tree，查询，插入都是O(lgn)
|
