Google电面，面经

gp89757 发表于 2015-9-30 15:48
第二问就是求surpass吧，一般是用BIT或者merge sort吧 都是nlogn的 BST应该是类似的思路

merge sort好顶赞

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. }
    

复制代码

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

请问如何用tree set 呢？如果是自己写AVL or Red-black tree, 在insert 每个node时候，可以count有多少个数比当前的大， 但是用tree set 的 add(node)函数，直接就插入树里，how to count number of elements larger than the current node?

第一题求测试，sorted array, O(logn)

int totalPass(int * num, int size) {
       
        int start = 0;
        int end = size - 1;
        int min_value = 0;
        while(start <= end) {

                int mid = (start + end) / 2;
                if(start != mid) {

                        /*num[start] either less than or \
                        equal to num[mid] after sort*/
                        if(num[start] < num[mid]) {
                                min_value += (end - mid + 1);
                                end = mid - 1;
                        }
                        else if(num[start] == num[mid]) {
                                start = mid + 1;
                        }

                }
                else {

                        /*start overlaps with mid, \
                        either start != end, or \
                        start == end*/
                        if(num[start] < num[end]) {
                                min_value += 1;
                        }
                        break;

                }

        }

        return min_value;

}

guzi 发表于 2015-9-30 21:26
请问如何用tree set 呢？如果是自己写AVL or Red-black tree, 在insert 每个node时候，可以count有多少个 ...

用TreeMap统计重复，用tailMap找到比当前key大的
static int leftPass(List<Integer> nums) {
        TreeMap<Integer, Integer> prevElements = new TreeMap<>();
        int maxLeftPass = 0;
        for (int n : nums) {
            maxLeftPass = Math.max(maxLeftPass, prevElements.tailMap(n, false).values().stream().mapToInt(i -> i).sum());
            prevElements.put(n, prevElements.getOrDefault(n, 0) + 1);
        }
        return maxLeftPass;
    }

newlxnewlx 发表于 2015-10-1 03:59
用TreeMap统计重复，用tailMap找到比当前key大的
static int leftPass(List nums) {
        TreeMap p ...

你这个复杂度应该是O(n^2)了吧？

第二题是Segment Tree？ LintCode 上面有

mileschen2008 发表于 2015-10-1 04:16
你这个复杂度应该是O(n^2)了吧？

你是对的  如果有重复元素的话要把所有count加起来，内层需要时间O(n).
如果不含重复元素可以直接返回tailMap(n, false).size().  获得这个tailMap的复杂度本身没有官方说明，但肯定不是O(n)

第二问是不是可以用C++的STL中的multiset，每插入一个，可以算出来前面的个数，是nlogn的。当然也可以用线段树。BST的话类似线段树的思想了，加入一个数，更新左子树数目，右子树数目。

请问楼主拿到onsite后约到什么什么on site呢