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)
|