nyc bloomberg onsite 跪经

请问楼主  第二题就是move zeros嘛？~  有要求 while maintaining the relative order of the non-zero elements.吗？~ 如果不要求的话 index一左一右应该是最优的吧~ 因为这样能有最少的swap  比如012345  不过还是很感谢楼主分享！ 希望您后面有更好的offer!!!!加油~

freesam 发表于 2016-9-14 04:56
我用一个元数为10的数列存最大的10个元数从小到大，每次二分插入不是log(n)输出不是log(n)，heap也是一样 ...

应该用一个容量为10的heap。。有可能bb面试很看重交流？

heap 其实有一个大问题。
现在知道 heap里面装着 top 10, 我现在要把他们retrieve出来放到ranking中去，
就需要poll() 10 次。

接着data stream 有新元素进来， 我还要重新简历之前的heap.
这题目最好的办法是BST. 大家都是习惯思维用heap, 但是忘了从heap里取数才能建立top 10 list.

xiaofeng 发表于 2016-9-22 04:48
heap 其实有一个大问题。
现在知道 heap里面装着 top 10, 我现在要把他们retrieve出来放到ranking中去，
...

可以用一个map连着heap里面的node 就不用poll出来 也知道heap里面有哪些啦

BB的onsite只有2轮技术面吗？不是说还有manager和HR面？

第一题：应该是保持一个最大长度为10的priority_queue吧，每次插入新值是log(10)而起，也就是常数时间。第一轮一道题不行就没有下文了吗？

第二轮：是用hash map: key -> value存多项式 其中key = exponent, value = coefficient吧？

我记得第一题也是 priority queue ，维护size 为10 的优先队列，最大堆， 写个comparator 每次进来一个数自动剔除最小的。
PriorityQueue<Integer> maxheap = new PriorityQueue<Integer>(10, new Comparator<Integer>(){
            public int compare(Integer arg0, Integer arg1) {
                return arg1 - arg0;
            }
        });

"给你一串数，要求每时每刻输出top10 largest number"
这个看意思应该是设计一个类，可以随时加入数据和随时询问当前最大的K个值

1. class TrackTopK {
   
2.   private: unsigned int _k; // _k is 10 in this problem
   
3.   priority_queue<int, vector<int>, greater<int>> _topK;
   
4.   
   
5.   public:
   
6.   TrackTopK(unsigned int k):_k(k) {}
   
7.   
   
8.   void addData(int x) {
   
9.     if (_topK.size() < _k) _topK.push(x);
   
10.     else if (_topK.top() < x) {
    
11.       _topK.pop(); _topK.push(x);   
    
12.     }
    
13.   }
    
14.   
    
15.   vector<int> getTopK() {
    
16.     // note that priority_queue does not allow iterator for traversal, so make a copy
    
17.     priority_queue<int, vector<int>, greater<int>> copy(_topK);
    
18.     vector<int> res;
    
19.     while (!copy.empty()) {
    
20.       res.push_back(copy.top()); copy.pop();   
    
21.     }
    
22.     return res;
    
23.   }
    
24. };

复制代码

请问lz多久收到的回复啊