Google电面，面经

第一题：

1. nums = map(int, raw_input().split())
   
2. mini = min(nums)
   
3. print len(filter(lambda x: x > mini, nums))

复制代码

第二题：

1. #include <cstdio>
   
2. #include <cstdlib>
   
3. #include <cstring>
   
4. #include <iostream>
   
5. #include <algorithm>
   
6. #include <vector>
   
7. #include <map>
   
8. 
   
9. using namespace std;
   
10. 
    
11. #define print(x) cout << x << endl
    
12. #define input(x) cin >> x
    
13. 
    
14. class BITree {
    
15. public:
    
16.     void init(int size) {
    
17.         _tree.resize(size + 1);
    
18.         fill(_tree.begin(), _tree.end(), 0);
    
19.     }
    
20. 
    
21.     void add(int pos, int value) {
    
22.         while (pos < _tree.size()) {
    
23.             _tree[pos] += value;
    
24.             pos += lowbit(pos);
    
25.         }
    
26.     }
    
27. 
    
28.     int sum(int pos) {
    
29.         int res = 0;
    
30.         while (pos > 0) {
    
31.             res += _tree[pos];
    
32.             pos -= lowbit(pos);
    
33.         }
    
34.         return res;
    
35.     }
    
36. private:
    
37.     inline int lowbit(int x) { return x & (-x); }
    
38. 
    
39. private:
    
40.     vector<int> _tree;
    
41. };
    
42. 
    
43. int main() {
    
44.     freopen("input.txt", "r", stdin);
    
45.     int n;
    
46.     vector<int> nums;
    
47.     map<int, int> mp;
    
48. 
    
49.     input(n);
    
50.     nums.resize(n);
    
51.     for (int i = 0; i < n; i++) {
    
52.         input(nums[i]);
    
53.         mp[nums[i]] = -1;
    
54.     }
    
55. 
    
56.     int idx = 0;
    
57.     for (auto& p: mp) {
    
58.         p.second = ++idx;
    
59.     }
    
60. 
    
61.     BITree bitree;
    
62.     bitree.init(n + 1);
    
63. 
    
64.     int ans = 0;
    
65.     for (int i = 0; i < n; i++) {
    
66.         int u = nums[i];
    
67.         ans = max(ans, bitree.sum(u));
    
68.         bitree.add(u, 1);
    
69.     }
    
70.     print(ans);
    
71.     return 0;
    
72. }
    

复制代码

补充内容 (2015-9-30 09:41):
代码没测过，仅供参考。轻拍。

要是足够牛逼的话，可以手写一个AVL/SBT。用平衡树的性质做。（争取吓尿面试官（并不能

补充内容 (2015-9-30 09:51):
果然写错了
67行应该是： ans = max(ans, bitree.sum(u - 1));

楼下的兄弟：
如果treeset对应的是std::set的话，那就是不行的。迭代器之间的距离需要O(N)的时间。

我一小时只能发两帖，不能跟帖回复了，抱歉。

补充内容 (2015-9-30 10:53):
66行改成：int u = mp[nums[i]];

智商堪忧啊我擦

Wizmann 发表于 2015-9-30 09:39
第二题：

补充内容 (2015-9-30 09:41):

第二题不能用treeset么

readman 发表于 2015-9-30 09:45
第二题不能用treeset么

我觉得第二题可以用Java 的 TreeSet，TreeSet是Red-black bst。但是呢，有个限制条件是数组必须没有duplicates.

mileschen2008 发表于 2015-9-30 10:15
我觉得第二题可以用Java 的 TreeSet，TreeSet是Red-black bst。但是呢，有个限制条件是数组必须没有dupli ...

有dup也可以, 弄个counter 最后减一下

readman 发表于 2015-9-30 10:34
有dup也可以, 弄个counter 最后减一下

那这样的话，你得遍历每一个大于它的数了，这好像跟brute-force无异了。不知道我理解的对不对，你能不能稍微写个代码出来看看？

http://www.lintcode.com/en/probl ... mber-before-itself/
第二题是不是这个

65岁退休 发表于 2015-9-30 11:49
http://www.lintcode.com/en/problem/count-of-smaller-number-before-itself/
第二题是不是这个

面试要写个segment tree也是醉了。

mileschen2008 发表于 2015-9-30 12:02
面试要写个segment tree也是醉了。

蛤蛤

也可以写块状链表，不过也不会更简单。

第二问就是求surpass吧，一般是用BIT或者merge sort吧 都是nlogn的 BST应该是类似的思路