热乎的Google面经

pyemma 发表于 2015-9-17 07:52
看题目不像是LRU，可能输入是个无限流

LRU不就是无限流吗？

pyemma 发表于 2015-9-17 07:52
看题目不像是LRU，可能输入是个无限流

LRU不就是无限流吗？

第一题地基（不知道问什么不直接说几楼，好像是7楼）说的是对的。给{-3,-2,-1,0,1} 输出{0,1,1,4,9}
第二题是有一些像LRU但比LRU简单些因为不需要从中间拿出来

edna 发表于 2015-9-17 06:48
第一题应该就是double pointer，比如说给你个array，{-5,-3,1,2}，最后的结果是{1, 4, 9, 25}.

做法可以 ...

感觉不用找第一个大于0的，两头比较abs大的，从后往前放就可以了

peach=。= 发表于 2015-9-17 12:46
感觉不用找第一个大于0的，两头比较abs大的，从后往前放就可以了

正解正解，我就这么整的

1. vector<double> get_sorted_square(vector<double> v) {
   
2.     if (v.size() == 0) return vector<double>();
   
3.     int l = 0, r = v.size();
   
4.     while (l+1<r) {
   
5.         int m = l+(r-l)/2;
   
6.         if (v[m] > 0.0) r = m;
   
7.         else l = m;
   
8.     }
   
9.     vector<double> square;
   
10.     while (l>=0 || r<v.size()) {
    
11.         if (l>=0 && r<v.size()) {
    
12.             if (v[l]*v[l] < v[r]*v[r])
    
13.                 square.push_back(v[l]*v[l--]);
    
14.             else
    
15.                 square.push_back(v[r]*v[r++]);
    
16.         }
    
17.         else if (l>=0)
    
18.             square.push_back(v[l]*v[l--]);
    
19.         else
    
20.             square.push_back(v[r]*v[r++]);
    
21.     }
    
22.     return square;
    
23. }
    

复制代码

第一题，先二分找最接近0的负数，然后merge。

craiglin1992 发表于 2015-9-17 10:46
第一题地基（不知道问什么不直接说几楼，好像是7楼）说的是对的。给{-3,-2,-1,0,1} 输出{0,1,1,4,9}
第二 ...

感谢楼主分享，第二题有什么具体要求？Time complexity?

douya 发表于 2015-9-21 02:36
感谢楼主分享，第二题有什么具体要求？Time complexity?

每次average应该需要O(1)吧

第二题可以用Deque做么？ 类似sliding window

craiglin1992 发表于 2015-9-22 00:10
每次average应该需要O(1)吧

可以用Queue做嘛？每次移出queue里最早的元素， 然后keep一个currSum,每次移出元素和加入新元素都更新下currSum？不知道有没有理解对题目的意思。