Google电面，面经

地里的同志帮忙给的内推，在这里谢谢了, @

电面的是中国同胞，上来介绍完就开始做题。

第一问，totalpass of an element x in array A is defined as the number of elements which is

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

估计是要跪了。祝大家好运。



补充内容 (2015-10-5 00:51):
结果竟然拿到onsite了，可能是面试小哥手下留情了。总之大家加油，地里朋友祝我好运啊。

第二题可以用两个priority_queue(就是堆)，第一个大根堆存储比当前数小的数字，第二个小根堆存比当前数大的数字
然后每次move next 就看数变大还是变小了，然后从一个堆pop()到另一个堆

1. #include <vector>
   
2. #include <stdio.h>
   
3. #include <algorithm>
   
4. #include <utility>
   
5. 
   
6. using namespace std;
   
7. 
   
8. 
   
9. //left pass
   
10. void merge_sort(vector<pair<int,int>> &vp, vector<int> &sp) {
    
11.     if (vp.size() < 2) return;
    
12.     int m = vp.size()/2;
    
13.     vector<pair<int,int>> va(vp.begin(), vp.begin()+m),
    
14.         vb(vp.begin()+m, vp.end());
    
15.     merge_sort(va, sp);
    
16.     merge_sort(vb, sp);
    
17.     for (int i=0,j=0,k=0; i<va.size()||j<vb.size();) {
    
18.         if (i<va.size() && j<vb.size()) {
    
19.             if (va[i].first > vb[j].first)
    
20.                 vp[k++] = va[i++];
    
21.             else {
    
22.                 int id = vb[j].second;
    
23.                 sp[id] += i;
    
24.                 vp[k++] = vb[j++];
    
25.             }
    
26.         }
    
27.         else if (i<va.size())
    
28.             vp[k++] = va[i++];
    
29.         else {
    
30.             int id = vb[j].second;
    
31.             sp[id] += i;
    
32.             vp[k++] = vb[j++];
    
33.         }
    
34.     }
    
35. }
    
36. int left_pass(vector<int> v) {
    
37.     int len = v.size();
    
38.     vector<int> sp(len, 0);
    
39.     vector<pair<int,int>> vp;
    
40.     for (int i=0; i<v.size(); i++)
    
41.         vp.push_back(make_pair(v[i], i));
    
42.     merge_sort(vp, sp);
    
43.     int ans = 0;
    
44.     for (auto x:sp)
    
45.         ans = max(ans, x);
    
46.     return ans;
    
47. }
    
48. 
    
49. int left_pass_brute_force(vector<int> v) {
    
50.     int ans = 0;
    
51.     for (int i=1; i<v.size(); i++) {
    
52.         int cnt = 0;
    
53.         for (int j=i-1; j>=0; j--)
    
54.             if (v[i] < v[j]) cnt++;
    
55.         ans = max(ans, cnt);
    
56.     }
    
57.     return ans;
    
58. }
    
59. 
    
60. void test_left_pass(int ncase) {
    
61.     int npass = 0;
    
62.     for (int i=0; i<ncase; i++) {
    
63.         int size = rand()%1007;
    
64.         vector<int> v(size);
    
65.         for (int j=0; j<size; j++)
    
66.             v[j] = rand()%17;
    
67.         if (left_pass(v) == left_pass_brute_force(v))
    
68.             npass ++;
    
69.     }
    
70.     printf("%d/%d\n", npass, ncase);
    
71. }
    
72. 
    
73. int main()
    
74. {   
    
75.     test_left_pass(1007);
    
76.     return 0;
    
77. }
    

复制代码

第二题：

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]];

智商堪忧啊我擦

第一题的题意不太懂，maximum totalpass感觉就是len-1啊，因为数组中最小值的totalpass最大，因为其他的len-1个数都大于它。如果理解错了，还希望楼主稍微再说明下题目，多谢啦。

这题看着怎么像segmenttree。。。第二问

mileschen2008 发表于 2015-9-30 05:44
第一题的题意不太懂，maximum totalpass感觉就是len-1啊，因为数组中最小值的totalpass最大，因为其他的len ...

[1,1,1]是什么

BST估计是每一个点记录右子🌲点得数量

Linzertorte 发表于 2015-9-30 06:04
[1,1,1]是什么

嗯，是的，要考虑duplicates，但是这道题目也就是找min value，然后找比他大的就行。如果array已经sort，就O(logn)，没sort O(n).

mileschen2008 发表于 2015-9-30 06:42
嗯，是的，要考虑duplicates，但是这道题目也就是找min value，然后找比他大的就行。如果array已经sort， ...

没sort的话可以O(n)解这题？ 就算用BST也要O(nlogn)吧?

kelvinzhong 发表于 2015-9-30 06:53
没sort的话可以O(n)解这题？ 就算用BST也要O(nlogn)吧?

我说的第一问哈。第二问BST当然得O(nlogn)啦。

第一问像是Leetcode上的h-index问题
大概看了一下geeks for geeks 上关于第二问的解答，好长。。。确定是要在面试中全部写出来么？ 感觉这一道题就可以用掉45分钟了。。PS: 没见过AVL的不就惨了？

感觉这道题的第二问好像可以用Stack来解决啊，还是需要先排序，从大到小排，然后还要用hash表存储好所有重复项的个数，接着向栈里面逐个压进去每一项，如果入栈的项的下标比栈顶的大，那么开始pop，直到栈顶的元素的下标比入栈项的小，这中间没pop出一个都可以计算出该项的leftpass值。说的有点儿晦涩，但是感觉确实可以用排序+栈来做！